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加加的基础知识，所以希望各位能进一步强化这部分内容。
