文章目录

二叉树
堆
二叉树的链式结构
- 二叉树的遍历

二叉树

树

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。

在这里插入图片描述

需要注意的是：子树之间不能有交集，否则就不是树形结构

树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为3
叶节点或终端节点：度为0的节点称为叶节点；如上图：E、F、G、H、I 节点为叶节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为3
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
树的高度或深度：树中节点的最大层次；如上图：树的高度为3
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林

树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间
的关系我们这里就简单的了解其中最常用的孩子兄弟表示法

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};

二叉树

概念

二叉树是一种不存在度大于2的节点，并且二叉树的子树是由左右之分的，次序不能颠倒，所以二叉树也是一种有序树

在这里插入图片描述

特殊的二叉树

满二叉树：如果一个二叉树的层数为K，且结点总数是2^k-1，则它就是满二叉树

在这里插入图片描述

完全二叉树：对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

在这里插入图片描述

二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是**2^(h-1).
对任何一棵二叉树, 如果度为0其叶结点个数为** n0 ,度为2的分支结点个数为n2,则有 n0＝n2＋1
. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log(n+1)
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对
于序号为i的结点有:若i > 0,i位置的父节点为：(i - 1)/2 ，i==0时，i为根节点，没有父节点；若2i+1 < n时，左孩子的序号：2i + 1；若2i+2 < n时，右孩子的序号：2i+2

堆

堆的概念

堆中的某个节点不能大于或者小于它的父节点的值，堆是一颗完全二叉树

某个节点不大于其父节点的值的堆叫做大根堆

在这里插入图片描述

某个节点不小于其父节点的值的堆叫做小根堆

在这里插入图片描述

堆的实现

堆的定义

堆是一种顺序存储的结构，所以我们以数组的形式存储，可以先定义一个堆结构

typedef int HPDataTypedef;
typedef struct HPNode
{
	HPDataTypedef* a;
	int size;//堆的元素个数
	int capacity;//数组的空间容量
}HP;

堆的初始化

初始化堆比较简单，和之前的顺序表初始化一样

//堆的初始化
void HeapInit(HP* hp) {
	assert(hp);

	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

堆的销毁

//堆的销毁
void HeapDestroy(HP* hp) {
	assert(hp);

	hp->size = hp->capacity = 0;
	free(hp->a);
	hp->a = NULL;
}

堆的插入

向上调整法

堆的插入数据是在数组的尾插入的，但是这里需要注意的问题是插入数据后会破坏堆的结构，就不再是一个堆的。所以需要我们堆插入的数据进行调整，因为数据是在尾部插入，所以可以根据原本堆的性质进行往上的调整。

在这里插入图片描述

以大堆插入数据为例

//两数交换
void Swap(HPDataTypedef* a, HPDataTypedef* b) {
	HPDataTypedef tmp = *a;
	*a = *b;
	*b = tmp;
}

//向上调整法
void Adjustup(HPDataTypedef* a, int child) {
    //算出父节点的下标
	int parent = (child - 1) / 2;
	while (child > 0) {
        //如果父节点小于子节点，两数交换
		if (a[parent] < a[child]) {
			Swap(&a[parent], &a[child]);
            //交换完后父节点和子节点需要更新
			child = parent;
			parent = (child - 1) / 2;
		}
        //调整好后推出循环
		else
			break;
	}
}

//堆的插入
void HeapPush(HP* hp, HPDataTypedef x){
	assert(hp);
	
    //判断容量是否充足，不够的话需要增容
	if (hp->size == hp->capacity) {
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataTypedef* tmp = (HPDataTypedef*)realloc(hp->a, sizeof(HPDataTypedef) * newcapacity);
		if (tmp == NULL) {
			perror("malloc fail");
			return;
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
    //将值赋给最后一个节点
	hp->a[hp->size++] = x;
	
    //进行向上调整
	Adjustup(hp->a, hp->size - 1);
}

堆的删除

删除堆是删除堆顶的数据，也就是根的数据。由于堆是以数组的结构存储的，所以只需要把第一个元素(根节点元素)和最后一个元素交换，然后元素个数整体减1就可以删除掉。但是有一个问题就是，互换元素之后会导致堆的性质改变，根节点元素就不符合堆的性质，所以这里就需要往下去做调整，就要用到向下调整法

向下调整法

在这里插入图片描述

以大堆删除为例

//向下调整法
void Adjustdown(HPDataTypedef* a, int n, int parent){
    //求出左孩子下标，但不知道左孩子和右孩子哪个更大，所以在下面需要比较
	int child = parent * 2 + 1;
	while (child < n) {
		//找出大的那个子节点
		if (child + 1 < n && a[child] < a[child + 1])
			child++;
		
        //如果父节点比子节点小，交换两个数
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
            //更新父节点和子节点
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

//堆顶数据删除
void HeapPop(HP* hp) {
	assert(hp);

	//交换堆顶和堆底数据
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

    //进行向下调整
	Adjustdown(hp->a, hp->size, 0);
}

整体堆实现各接口

typedef int HPDataTypedef;
typedef struct HPNode
{
	HPDataTypedef* a;
	int size;//堆的元素个数
	int capacity;//数组的空间容量
}HP;

//堆的初始化
void HeapInit(HP* hp) {
	assert(hp);

	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

//堆的打印
void HeapPrint(HP* hp) {
	assert(hp);
	
	for (int i = 0; i < hp->size; i++)
		printf("%d ", hp->a[i]);

	printf("\n");
}

//堆的销毁
void HeapDestroy(HP* hp) {
	assert(hp);

	hp->size = hp->capacity = 0;
	free(hp->a);
	hp->a = NULL;
}

void Swap(HPDataTypedef* a, HPDataTypedef* b) {
	HPDataTypedef tmp = *a;
	*a = *b;
	*b = tmp;
}

//向上调整法
void Adjustup(HPDataTypedef* a, int child) {
	//算出父节点的下标
	int parent = (child - 1) / 2;
	while (child > 0) {
		//如果父节点小于子节点，两数交换
		if (a[parent] < a[child]) {
			Swap(&a[parent], &a[child]);
			//交换完后父节点和子节点需要更新
			child = parent;
			parent = (child - 1) / 2;
		}
		//调整好后推出循环
		else
			break;
	}
}

//向下调整法
void Adjustdown(HPDataTypedef* a, int n, int parent){
	//求出左孩子下标，但不知道左孩子和右孩子哪个更大，所以在下面需要比较
	int child = parent * 2 + 1;
	while (child < n) {
		//找出大的那个子节点
		if (child + 1 < n && a[child] < a[child + 1])
			child++;

		//如果父节点比子节点小，交换两个数
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			//更新父节点和子节点
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

//堆的插入
void HeapPush(HP* hp, HPDataTypedef x){
	assert(hp);

	//判断容量是否充足，不够的话需要增容
	if (hp->size == hp->capacity) {
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataTypedef* tmp = (HPDataTypedef*)realloc(hp->a, sizeof(HPDataTypedef) * newcapacity);
		if (tmp == NULL) {
			perror("malloc fail");
			return;
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	//将值赋给最后一个节点
	hp->a[hp->size++] = x;

	//进行向上调整
	Adjustup(hp->a, hp->size - 1);
}

//堆顶数据删除
void HeapPop(HP* hp) {
	assert(hp);

	//交换堆顶和堆底数据
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

	//进行向下调整
	Adjustdown(hp->a, hp->size, 0);
}

//取堆顶的数据
HPDataTypedef HeapTop(HP* hp) {
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->a[0];
}

//堆的数据个数
int HeapSize(HP* hp) {
	assert(hp);

	return hp->size;
}

//堆的判空
bool HeapEmpty(HP* hp) {
	assert(hp);

	return hp->size == 0;
}

堆排序

向上调整法的时间复杂度

在这里插入图片描述

则需要移动的节点总步数为：T(n)=2^0 * 0 + 2^1 * 1 + 2^2 * 2 + … + 2^(h-1) * (h-1)

2T(n)=2^1 * 0 + 2^2 * 1 + 2^2 * 2 + … + 2^h * (h-1)

错位相减后得：2 + 2^h + 2^h * h - 2^h

h * 2^h - 2

n = 2^h - 1 h = log(n+1)

所以向上调整法的时间复杂度为O(N * logN)

向下调整法复杂度

在这里插入图片描述

则需要移动的节点总步数为：T(n)=2^0(h-1) + 2^1(h-2) + 2^2(h-3) + … + 2^(h-1)*1

2T(n)=2^1(h-1) + 2^2(h-2) + 2^3(h-3) + … + 2^(h-1)*1

错位相减后得：1-h + 2^1 + 2^2 + 2^(h-1)

2^h - 1 - h

n = 2^h - 1 h = log(n+1)

所以T(n)约等于n

所以向下调整法的时间复杂度为O(N)

建堆

综上所诉在选择建堆的过程，利用向下调整法的效率会更高

但是向下调整法有个前提条件就是需要左右子树都为小堆或者大堆的情况

所以再使用向下调整法建堆的过程中需要先从最后一个叶节点的父节点开始依次调整，这样调整完后才能满足条件

排序

建好堆后不一样就有序了，所以还要对堆进行堆排序。

这里有一个需要注意的地方是，如果我们需要升序，那建大堆进行排序效率会更高，相反降序的话就需要建小堆

排序的步骤也很简单，以升序为例，当我们建好大堆之后，第一个节点就是最大的元素，只需要将它和最后一个节点交换，那么最大的数就到了最后的位置了。为了不破坏堆的结构除去最后一个节点后使用向下调整法调整好即可

以此类推依次进行该步骤直到第一个节点即可

void HeapSort(int* a, int n) {
	建堆 向上调整建堆 O(N * logN)
	//for (int i = 0; i < n; i++)
	//	Adjustup(a, i);
	 
	//向下调整建堆 O(N)
	//需要根的左子树和右子树是大堆或者小堆情况
	//先从最后一个节点的父节点开始调，调好之后就成立条件
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		Adjustdown(a, n, i);

	int i = 1;
    //循环n-1次
	while (i < n) {
        //每一次交换的最后一个元素都要往前推1
		Swap(&a[0], &a[n - i]);
        //交换完后向下调整
		Adjustdown(a, n - i, 0);
		i++;
	}
}

int main() {
	int a[] = { 15, 8, 19, 25, 2, 34, 5, 49, 27, 37 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
		printf("%d ", a[i]);
	return 0;
}

在这里插入图片描述

TopK问题

这个问题就是在一堆数据中选出前K个最大或最小的数

假设现在要要选出前K个最大的数，思路十分的简单

先建一个存放K个数的小根堆
将剩下的n-K和数依次和堆顶的数据比较，如果比堆顶大，堆顶就变成该数据，为了不破坏堆的结构，进行向下调整法
所有的数据比完后，堆里的数据就是前K个大的数

这里使用文件的方式来产生N个随机值

首先先创建文件，生成N个随机值

void createdatafile(const char* filename, int k) {
	assert(filename);

	FILE* fp = fopen(filename, "w");//以写的方式创建文件夹
	//判断是否打开成功
	if (fp == NULL){
		perror("fopen fail");
		return;
	}
	//创建数据
	srand((unsigned int)time(0));
	for (int i = 0; i < k; i++)
		fprintf(fp, "%d ", rand());
	//关闭文件
	fclose(fp);
	fp = NULL;
}

请添加图片描述

然后根据步骤，读取前k个数据建成小堆后，再依次对后N-k个数据比较进堆

void printtopk(const char* filename, int k) {
	assert(filename);

	FILE* pf = fopen(filename, "r");//以读的方式打开文件
	//判断是否打开成功
	if (pf == NULL)
	{
		perror("fopen fail");
		return;
	}

	//重建容量为K的小堆
	int* minHeap = (int*)malloc(sizeof(int) * k);//开辟K个空间的动态内存
	if (minHeap == NULL)
	{
		perror("malloc fail");
		exit(-1);//开辟失败，直接退出程序
	}
	//从文件中读取K个数字
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &minHeap[i]);
	}
	//向下调整建小堆
	for (int j = (k - 1 - 1) / 2; j >= 0; j--)
	{
		Adjustdown(minHeap, k, j);//向小调整
	}

	//读取后面的N-K个数与堆顶比较
	int val = 0;
	while (fscanf(pf, "%d", &val) != EOF)
	{
		//判断值是否比堆顶大
		if (val > minHeap[0])
		{
			minHeap[0] = val;//改变堆顶的值
			Adjustdown(minHeap, k, 0);//向下调整保持小堆结构
		}
	}

	//打印前K个数
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");

	//关闭文件
	fclose(pf);
	pf = NULL;
}

int main() {
	const char* filename = "heap.txt";
	int N = 10000;
	int k = 10;
	createdatafile(filename, N);
	printtopk(filename, k);
	return 0;
}

请添加图片描述

二叉树的链式结构

首先手动创建一个二叉树才能学习其相关操作

typedef int BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//创造树
BTNode* CreataTree() {
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	assert(n1);
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	assert(n2);
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	assert(n3);
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	assert(n4);
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	assert(n5);
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	assert(n6);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n2->right = NULL;
	n4->left = n5;
	n4->right = n6;
	n5->left = NULL;
	n6->left = NULL;
	n3->left = NULL;
	n3->right = NULL;
	n5->right = NULL;
	n6->right = NULL;

	return n1;
}

二叉树的遍历

遍历二叉树有三种方法，前序，后序，中序

前序遍历

先访问根节点，在访问左节点，然后右节点

在这里插入图片描述

像上面这颗树的遍历顺序是

A->B->C->G->NULL->NULL->NULL->D->NULL->NULL->D->E->NULL->NULL->F->NULL->NULL

这是一种递归思想，，先遍历根，再左节点，再把左节点看作父节点，访问它的左节点，以此类推直至遇到空后再访问最近的父节点的右节点

//前序
void PreOrder(BTNode* root) {
	if (root == NULL)
		return;

	printf("%d ", root->data);

	PreOrder(root->left);
	PreOrder(root->right);
}

中序

//中序
void InOrder(BTNode* root) {
	if (root == NULL)
		return;

	InOrder(root->left);

	printf("%d ", root->data);

	InOrder(root->right);
}

后序

//后序
void PostOrder(BTNode* root) {
	if (root == NULL)
		return;

	PostOrder(root->left);
	PostOrder(root->right);

	printf("%d ", root->data);
}

计算叶子节点的个数

叶节点的左右节点都为空，根据这个思想可以递归下去，如果父节点的左右节点都为空就返回1，不然返回0

//计算叶子节点个数
int TreeLeafSize(BTNode* root) {
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

计算树的高度

首先需要比较左子树和右子树的高度，取大值再加上根节点的一个高度

//计算树的高度
int TreeHeight(BTNode* root) {
	if (root == NULL)
		return 0;

	int i = TreeHeight(root->left) + 1;
	int n = TreeHeight(root->right) + 1;

	if (i > n)
		return i;
	else
		return n;
}

【数据结构】---“二叉树”--“堆”

文章目录

二叉树

树

树的相关概念

树的表示

二叉树

概念

特殊的二叉树

二叉树的性质

堆

堆的概念

堆的实现

堆的定义

堆的初始化

堆的销毁

堆的插入

向上调整法

堆的删除

向下调整法

整体堆实现各接口

堆排序

向上调整法的时间复杂度

向下调整法复杂度

建堆

排序

TopK问题

二叉树的链式结构

二叉树的遍历

前序遍历

中序

后序

计算叶子节点的个数

计算树的高度

网站公告

今日签到

热门文章

最新发布