2.堆:
1.堆的概念:
二叉树不同于常规的数组,它仅仅是把数据插入进去或者删除出去,这便没意思了,那我用顺序表不是更好?这里我便要介绍堆的概念:
对于一个完全二叉树,倘若它的父亲节点与子节点都有固定大小关系(但兄弟节点之间的大小关系无所谓),则称这个完全二叉树为堆。
注意我强调的两点:
1.这一定是一棵完全二叉树
2.父亲节点与子节点的关系必须固定,但兄弟之间无所谓
2.堆的类型:
根据父亲和子节点的关系:堆分为大堆和小堆
1.大堆:所有的父亲节点都大于子节点的堆
2.小堆:所有的父亲节点都小于子节点的堆
如图:
所以这引发一个思考,二叉树的顺序结构本质上不就是堆么,没错,完全二叉树最有意义的便是实现堆。
3.二叉树顺序结构的插入和删除(堆的插入和删除):
由于堆本质就是二叉树的顺序结构,故接下来我则使用顺序结构进行堆的一系列操作。
1.堆的插入:
void HeapPush(HP* php, HPDataType x)//尾插二叉树堆 { assert(php); //判断扩容 if (php->size == php->capacity) { int newCapacity = php->capacity==0 ? 4 : php->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType)); if (tmp == NULL) { perror("realloc failed"); exit(-1); } php->a = tmp; php->capacity = newCapacity; } php->a[php->size] = x; php->size++; Adjustup(php->a, php->size - 1); }
首先常规的一个顺序表的扩容,这里不多说了,然后就把我们想插入的数据放入了数组,同时对记录数组长度的数据加一,但仅仅如此是不够的,这里我们以小堆为例子,既然我们想排小堆,则对于新插入的数据,我们要让其自动上升到相应的位置去,这就是向上调整的过程
向上调整的过程如下:
void Adjustup(HPDataType*a,int child)//向上调整 注意,向上调整的传入的是下标,且这个下标应该对应的最后一个插入的孩子节点的下标,这样才方便向上调整 { int parent = (child - 1) / 2; while (child>0) { if (a[child] < a[parent]) { Swap(&a[child],&a[parent]);//注意,这里要传指针,这样才能真正改变指针对应的数据 child = parent; parent = (parent - 1) / 2; } else { break;//倘若不符合规律了,则循环直接停止即可 } } }
!!!!注意强调的,这里都是传的参数都是下标,千万别搞错。!!!
对于向上调整,我们一定传的子节点,故首先我们要自己创建一个父亲节点方便交换,然后进入循环,倘若遇到符合条件就直接放入当前位置break跳出循环。循环中止条件一定要求是child,倘若是parent会有遗漏的情况,根节点比不到了就。
由此,堆插入就完成了。
2.堆的删除:
对于堆来说,倘若仅仅删除它的尾部数据,那样就不如使用顺序表尾删,故这里我们所说的删除,其实是针对的是根节点的删除
void HeapPop(HP* php)//删除根数据,根子节点交换然后删除,之后向下调整,向下调整的前提:左右子树是大堆或者小堆 { assert(php); assert(php->size > 0); Swap(&(php->a[0]),&(php->a[php->size - 1])); php->size--; Adjustdown(php->a, php->size,0);//注意,别忘了传的是下标,而不是元素内容 }
根删除简单啊!只要直接把头数据删掉然后后面的向前移动就好。
但这样是严重的错误,运气好的话,确实可以直接组成下一个堆,但假如这样之后不符合条件,整个的堆就全乱了,故我们这里采用这样的思路:
首先交换头和尾的数据,然后对size–,也是就删除尾部的数据,此时,根节点就被删除了,然后我们再处理根的新数据,这时候,我们只需要对根数据进行向下调整,这样的话,原先的根节点的子节点就会顶上来成为新的根节点,而我们的尾部数据也会自己回到尾部的位置,这样就不会出现关系混乱的情况,完美实现了删除根数据。
向下调整的函数如下:
void Adjustdown(HPDataType*a,int n,int parent)//向下调整 { int child = parent * 2 + 1;//这里的做法类似于求最大值的假设法。 while(child<n) { //找出小孩子 if (child+1<n&&a[child + 1] < a[child])//注意,加上这个child+1<n的目的是防止越界,因为假设child<n进入循环,而child恰好是最后一个元素,则child+1则越界了,所以我们不仅要保证child不越界,child+1也要不越界,这样就可以处理只有一个子节点的情况了 { child++;//首先找到两个子节点中更大或者更小的那个节点,作为接下来向下调整的子节点 } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
向下调整的大体思路同向上差不多,我们传入的是父亲节点,所以要创建子节点,但值得注意的是,向下调整需要判断一下哪个子节点更符合条件,故需要比较一下,但注意比较的条件,因为我们会遇到恰好左子节点已经在数组边界的情况,此时访问右节点就越界了,故我们加上child+1<n这样一条,倘若越界了就直接拿着左节点比较就可以了。
由此,堆删除就完成了。
4.基于堆能实现的两个功能:
1.堆排序
2.TopK问题
1.堆排序:
我们大多数人最早接触的第一种排序应该是冒泡排序,但冒泡排序的速度应付小数据还好,一旦应付大规模的数据排序(比如上万上千万级别的数据)冒泡排序的依次遍历的方式就相形见绌了,所以今天我们利用堆区实现一个新的排序方法,堆排序。
现在我们要排列一系列数据使其变为升序,我们可以这样排,首先利用堆排序将其排为大堆(这里为什么排大堆,之后你就明白了,不要着急),这样我们的根数据即为最大的数据,尾数据即为最小的数据,然后参考堆删除的思路,我们交换首和尾的数据,然后对size–,然后,我们对剩下的数据重复再进行一次首尾交换,然后size–,这样,大数据就自然而然的放在了尾部,并且后面的数据依次排列。有人说排成小堆不是更好,但问题是堆不在乎兄弟节点,只在乎父子关系,所以你没法控制兄弟之间的大小,而我才用建大堆的这种方式可以避免这个问题。代码如下:
int i = 0; for (i = 1; i < n; i++)//注意,**这里i等于1即可,因为在parent函数中,parent为(child-1)/2,从0开始就会出现负数,数组的访问就越界了,所以i=1开始即可访问所有数据。** { Adjustup(a, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]);//首尾元素交换,然后将访问权限减一,把除去最后一个元素的其他元素想成一个堆去向下调整,找到第二大的,依次进行即可。 Adjustdown(a, end, 0); end--; }
但建立堆只能用向上调整法么?
并不是,向上调整法比较好想,但其实速度太慢,用向下调整法也可以进行建堆,但与向上不同,我们不能从根节点出发,而是从第一个非叶子节点开始(最后一层就没必要向下调整了),这是由于,向下调整的前提是左右子树要已经是堆,这也是为什么我们倒着排的原因。通过倒着排,上面要排的堆的下面的节点已经是堆了,就可以向下调整了,而第一个非叶节点的寻找方法即利用我们上面说到的关系去处理:i=(sz-1-1)/2即为第一个非叶节点。
故向下调整的方式如下:
int i = 0; for (i = (n - 1 - 1) / 2; i >= 0 ; i--)//注意,这里采用了更为快捷的向下调整建堆法,其思路在于找到第一个非叶子节点,也就是最后一个节点的父亲节点,然后进行依次减一操作直到i>=0,其目的在于,先构建一个部分堆以保证上面的节点可以进行向下调整 { Adjustdown(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]);//首尾元素交换,然后将访问权限减一,把除去最后一个元素的其他元素想成一个堆去向下调整,找到第二大的,依次进行即可。 Adjustdown(a, end, 0); end--; }
那向上排序和向下排序谁更快呢?
向下排序更快,因为向上排序需要审查最后一层数据,而最后一层数据在整个二叉树中大约占据百分之50,而向下调整就不需要审查,故查找的次数上向上调整的次数太多了,故今后的堆排序选择向下调整法速度会更加快。(这是一种大约估摸的算法,想要知道真正的速度差别,需要进行真正的运算,在这里我不多介绍了,但向下调整大约是N-log(N+1),向上调整大约是N*logN-N)
2.TopK问题:
当你打开美团外卖,搜索某一种小吃,你会在屏幕上看到几百家的同类饭店,并且美团会为你自动排好他们的顺序并给你推荐其相应的前几名。这种排列的依据可能是好评度,可能是月销量,也有可能是综合的数值评判,但美团的后台大概是怎样进行几千家相同类型的商家的排序的呢?这便使用了TopK问题的解决方式。
TopK问题如下:
假设10000个数据,随机出现,找出其最大的前K个。
我们TopK问题的解决思路就是:
首先将前100个数据建立一个小堆,然后依次读取剩下的数据,与堆顶的最小的数据比较,倘若大于它就进入堆并向下排序找到合适的位置,这样一直持续到读取结束,堆中的数据即为排列好的前100大的数据
时间复杂度为O(N*logK)
空间复杂度为O(K)
我们一般对于这种问题配合文件操作实现,代码如下:
void PrintfTopk(const char*filename,int k)//这个函数是topk算法的函数,操作文件的 { FILE* fout = fopen(filename, "r");//打开文件,操作是读取"r" if (fout == NULL) { perror("fopen fail"); return; } int i = 0; int* minheap = (int*)malloc(sizeof(int) * k); if (minheap == NULL) { perror("malloc fail"); return; } for (i = 0; i < k; i++)//将文件打开后,将其从文件输入到内存中fscanf,用minheap数组来接收数据 { fscanf(fout, "%d", &minheap[i]);//注意,fscanf是不用加换行的,默认间隔 } //向下调整建堆 for (int i = (k - 1 - 1) / 2; i >= 0; i--) { Adjustdown(minheap,k,i); }//对前k个建堆 int end = k - 1; while (end > 0) { Swap(&minheap[0], &minheap[end]); Adjustdown(minheap, end, 0); end--; } int x = 0; while (fscanf(fout,"%d",&x) != EOF)//fscanf将文件里的数据放入到x中,此时文件的数据自动已经进行到k+1了,所以令其传给x,x去与minheap[0]比较,这就满足了数据赋值后进行向下调整,从而完成了,topk问题。 { //如果比你大,就替换你进堆 if (x > minheap[0]) { minheap[0] = x; Adjustdown(minheap, k, 0); } } for (i = 0; i < k; i++) { printf("%d ", minheap[i]); } printf("\n"); fclose(fout); } void CreateNDate()//这里是创造随机数进文件的函数 { int n = 10000; srand(time(NULL));//注意首先要有一个时间戳,作为种子,让其time的参数为NULL或者0也可以,这样time就会返回一个时间戳而不会把这个返回值放在一个timer指向的内存中带回去。 const char* file = "data.txt"; FILE* fin = fopen(file, "w");//打开文件,操作是写"w" if (fin == NULL) { perror("fopen fail"); return; } for (int i = 0; i < n; i++) { int x = rand() % 10000;//控制范围在10000以内生成随机数 fprintf(fin, "%d\n", x);//往文件里面写东西最方便的是:fprintf是写,fscanf是读取,这里是从内存往文件里写,所以相当于输出用fprintf } fclose(fin);//注意文件操作和动态开辟内存一样,最后一定要关闭,别忘了 }
以上便是二叉树顺序结构的全部内容了,但我要补充一点:
对于任意一棵二叉树(注意,我强调的是二叉树,其他树不行),如果叶子节点的个数为N0,则度为2的节点的个数就为N0-1,也就是说他们两个永远差一个,这是由于从根开始他们就差一,之后他们的增幅速度是完全相同的,故即使到了最后他们也差一。
4.二叉树链式存储结构
在正式进行链式结构开始前,让我们重复一遍二叉树的定义:
二叉树是:
- 空树
- 非空:根节点,根节点的左子树、根节点的右子树组成的。
根 左树 右树 …反复记忆这个过程,这就是我们链式二叉树的最基本的递归思路,我们要把所有的问题全部归结到根 左树 右树上来,而不同的代码的本质就是在这个基础上进行调整,但本质是不变的。
再重申一遍,先考察本体,然后考察左右树(当然有的问题例如中序和后序不是先从根开始)。
1.二叉树的遍历:
二叉树的遍历分为四种:
1.前序遍历
2.中序遍历
3.后序遍历
4.层序遍历
1.前序遍历:根 左 右
我们要使用递归的思想:故如图:
把每一块问题都变成根 左 右这样的三个部分去思考,
故我们可以这样写:
void PrevOrder(BTNode* root)//前序遍历法,基本的思路就是递归 { if (root == NULL) { printf("NULL->"); return; } printf("%d->", root->val); PrevOrder(root->left); PrevOrder(root->right); }
程序递归图如下:
2.中序遍历: 左 根 右
void InOrder(BTNode* root)//中序遍历法,递归 { if (root == NULL) { printf("NULL->"); return; } InOrder(root->left); printf("%d->", root->val); InOrder(root->right); }
3.后序遍历: 左 右 根
void PostOrder(BTNode* root)//后序遍历法,递归 { if (root == NULL) { printf("NULL->"); return; } PostOrder(root->left); PostOrder(root->right); printf("%d->", root->val); }
由于跟前序遍历道理差不多,故在这里我不多赘述中序和后序遍历的过程了,直接上代码了
4.层序遍历:父亲带儿子一起来
层序遍历和前三个遍历的方式不同,其风格有点类似我们前面提到的左孩子右兄弟访问法,先说说基本思路,我访问一层,就把这一层遍历,然后进行下一层,但问题在于,我如何做到一层访问完再去访问下一层呢?
这里我们可以借助队列来实现,其基本的思路就是父亲带儿子的思想,每找到一个父亲就把他的儿子也带在他后边,用队列解释就是,每访问一个节点,就连同把它的子节点也放入队列,然后删除父节点,继续访问下一个队列的头元素,持续访问队列直到队列为空为止,这样就保证了层序可以不断的一层一层去访问,代码实现为:
void LevelOrder(BTNode* root)//二叉树层序遍历,利用队列处理即可 { Que q; QueueInit(&q); if (root) { QueuePush(&q, root);//首先把根节点放在队列的最开始 } while (!QueueEmpty(&q))//如果队列不为空 { BTNode*front=QueueFront(&q);//找到队列最开头的节点 printf("%d ", front->val); if (front->left)//将最开头节点的左右子树的节点放进去,然后重复这个操作 { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } QueuePop(&q);//将最开头的节点出队列 } QueueDestroy(&q);//别忘了最后要销毁队列 printf("\n"); }
层序遍历引申问题:判断是否为完全二叉树:
代码如下:
int TreeComplete(BTNode* root)//判断是否为完全二叉树 { Que q; QueueInit(&q); if (root) { QueuePush(&q, root);//首先把根节点放在队列的最开始 } while (!QueueEmpty(&q))//如果队列不为空 { BTNode* front = QueueFront(&q);//找到队列最开头的节点 if (front == NULL) { break;//首先找到空节点,倘如为空就跳出循环,执行下一条 } QueuePush(&q, front->left); QueuePush(&q, front->right);//空也要进,非空也要进,其目的就是找出空 QueuePop(&q);//将最开头的节点出队列 } while (!QueueEmpty(&q)) { BTNode*front= QueueFront(&q);//进入这个循环,队列依次寻找是否有非空节点,有就为非完全,否则就为完全二叉树 QueuePop(&q);//出队列 if (front != NULL)//注意这里释放的是q,是队列的结构体,不会影响树的节点,对于二叉树本身的结构体是不删除的,原来的树的结构体仍在 { QueueDestroy(&q); return false; } } QueueDestroy(&q); //别忘了最后要销毁队列 return true; }
其基本的思路就是:也利用队列层序遍历,不论左右子树是否为空都仿放入队列,遇到空就跳出第一个循环进入第二个,如果为完全二叉树,后序的遍历直到队列为空,是不可能会有节点的,应该全为空,所以只要遇到非空节点,则不是完全二叉树,倘若直到队列为空都是NULL,则证明是完全二叉树。
2.二叉树的销毁:
讲完遍历,我们再来说说销毁,销毁的难点在于,可能存在指针丢失而无法全删除的问题,故我们采取后序遍历的思路,先删分支最后删主干,代码实现为:
void TreeDestroy(BTNode* root)//销毁二叉树,利用后序去处理,这样防止free掉后野指针了,利用后序,首先销毁左右子树,倘若先销毁根节点,则左右子树访问不到就没法销毁了 { if (root == NULL) { return; } TreeDestroy(root->left); TreeDestroy(root->right); free(root); //free之后不用置空,因为我传的不是指针,置空也不改变实参,只有传二级指针的时候置空,比如链表那里就要置空 }
这便是二叉树链式结构的基本问题,后面还有几个问题不一一讲解了,看代码即可:
3.其他问题代码解析:
1.求节点个数:(基本递归思路的考察,根 左 右)
int TreeSize(BTNode* root)//树的节点个数, 递归最优解法 { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right)+1;//注意,最后一个节点根节点要加上不要忘了,我们只需要知道当前的节点是否存在即可。故只要它不是空,我们就执行三目操作符的第二个条件,也可以理解为左右子树遍历完了之后,还要加上根节点,对于总树如此,对于每一个子树也是如此 }
2.叶节点个数:(同理,遇到一个节点先判断空,再看左右节点是不是空来看是不是叶节点,不是就继续向下访问)
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); }
3.第K层节点个数:(同理,引入高度的量,看传入的高度是不是要查询的高度即可)
int TreeKLevel(BTNode* root, int level)//第K层节点个数 { assert(level > 0); if (root == NULL) { return 0; } if (level == 1) { return 1; } return TreeKLevel(root->left, level - 1) + TreeKLevel(root->right, level - 1); }
4.二叉树特定节点的查找(注意如何在递归过程中把X节点对应的位置保留回来返回,这里使用利用一个指针存下来的办法)
BTNode* TreeFind(BTNode* root, int x)//二叉树查找值为x的节点,方便后续的修改 { if (root == NULL) { return NULL; } if (root->val == x) { return root; } BTNode* ret = NULL; ret= TreeFind(root->left, x); if (ret) { return ret; } ret= TreeFind(root->right, x); if (ret) { return ret; } return NULL; }
5.求树的高度(同样利用左右节点整型存下来对应的树的高度,进行比较后返回较大的即可)
int TreeHigh(BTNode* root)//求树的高度 { if (root == NULL) { return 0; } int leftHeight = TreeHigh(root->left); int rightHeight = TreeHigh(root->right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;//注意。这里先存储一次数据,这样就不用重复递归计算了,计算一次记录一次,最后加1即可 //或者使用fmax函数 //return fmax(TreeHigh(root->left), TreeHigh(root->right)) + 1;//fmax取最大值的函数,需要头文件<tgmath.h> }
总结:
以上便是二叉树基本问题的总结,二叉树还有很多变种题目以及形式,故希望各位可以不断持续刷题或者深入学习,二叉树后期还会为红黑树,B树等更加复杂的结构打基础,也是C加加的基础知识,所以希望各位能进一步强化这部分内容。