数据结构——二叉树和堆(万字，最详细）

目录

1.树

1.1 树的概念与结构

1.2 树相关的术语

1.3 树的表示法

2.二叉树

2.1 概念与结构

2.2 特殊的二叉树

2.2.1 满二叉树

2.2.2 完全二叉树

2.3 二叉树存储结构

2.3.1 顺序结构

2.3.2 实现顺序结构二叉树

2.3.2.1  堆的概念与结构

2.3.2. 2 堆的插入与删除数据

2.3.2.3 堆排序

2.3.2.4 堆一些杂于实现

2.3.3 实现链式结构二叉树 

2.3.3.1 二叉树的遍历：

2.3.3.2 二叉树的几个操作

2.3.3.3 二叉树的性质：

---

1.树

树大家都见过吧，那么下面是根，上面是分叉。但是咱们今天要讲的树不是你们所想的那种树，而是一种倒过来的树的模型（即下面是分叉，上面是根）。OK，让我们来进入学习。

1.1 树的概念与结构

树是⼀种非线性的数据结构，它是由 n （ n>=0 ） 个有限结点组成⼀个具有层次关系的集合。把它叫做 树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，而叶朝下的。

1.有⼀个特殊的结点，称为根结点，根结点没有前驱结点。

2.除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm ，其中每⼀个集合 Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的子树。每棵⼦树的根结点有且只有⼀个前驱，可以 有 0 个或多个后继。因此，树是递归定义的。

如上图就是树。注意：树 形结构中，子树之间不能有交集，否则就不是树形结构 。

看完了树，咱们再来看看非树，

非树形结构：

1. 子树是不相交的（如果存在相交就是上图）。

2.除了根结点外，每个结点有且仅有⼀个父结点 。

3.⼀棵N个结点的树有N-1条边 。

1.2 树相关的术语

还是以这个图来看：

父结点/双亲结点：若⼀个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点

子结点/孩子结点：⼀个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点 结点的度：⼀个结点有几个孩子，他的度就是多少；比如A的度为6，F的度为2，K的度为0

树的度：⼀棵树中，最大的结点的度称为树的度；如上图：树的度为 6

叶子结点/终端结点：度为 0 的结点称为叶结点；如上图： B 、 C 、 H 、 I... 等结点为叶子结点

分支结点/非终端结点：度不为 0 的结点；如上图： D 、 E 、 F 、 G... 等结点为分支结点

兄弟结点：具有相同父结点的结点互称为兄弟结点(亲兄弟)；如上图：  B 、 C 是兄弟结点 结点的层次：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推；

树的高度或深度：树中结点的最大层次；如上图：树的高度为 4

结点的祖先：从根到该结点所经分支上的所有结点；如上图： A 是所有结点的祖先

路径：⼀条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；比如A到Q的路径为： A-E-J-Q；H到Q的路径H-D-A-E-J-Q

子孙：以某结点为根的子树中任⼀结点都称为该结点的子孙。如上图：所有结点都是A的子孙

森林：由 m （ m>0 ） 棵互不相交的树的集合称为森林； 

1.3 树的表示法

孩子兄弟表示法： 树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结 点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子 兄弟表示法等。我们这⾥就简单的了解其中最常用的孩子兄弟表示法。

 struct TreeNode 
{ 
struct Node* child;   // 左边开始的第⼀个孩⼦结点struct Node* brother; // 指向其右边的下⼀个兄弟结点int data;  // 结点中的数据域           
}; 

 

 

2.二叉树

OK，接下来是重头戏，也就是二叉树

2.1 概念与结构

在树形结构中，我们最常用的就是二叉树，⼀棵二叉树是结点的⼀个有限集合，该集合由⼀个根结点 加上两棵别称为左子树和右子树的二叉树组成或者为空。 

二叉树的特点：

1. 二叉树不存在度大于 2 的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

注意：对于任意的二叉树都是由以下几种情况复合而成的。

2.2 特殊的二叉树

2.2.1 满二叉树

⼀个二叉树，如果每⼀个层的结点数都达到最大值，则这个二叉树就是满⼆叉树。也就是说，如果⼀ 个二叉树的层数为 K ，且结点总数是2^k − 1 ，则它就是满二叉树。 

2.2.2 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个 结点的二叉树，当且仅当其每⼀个结点都与深度为K的满二叉树中编号从 1 至 n 的结点⼀⼀对应时称 之为完全二叉树。要注意的是满二叉树是⼀种特殊的完全二叉树。 （满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树）

二叉树的性质：

咱们由满二叉树推出：

1.若规定根结点的层数为 1 ，则⼀棵非空二叉树的第i层上最多有 2的（i-1）次方个结点。

2.若规定根结点的层数为 1 ，则深度为 h 的二叉树的最大结点数（二叉树的总的节点数）是 （2^h）-1。

3.若规定根结点的层数为 1 ，具有 n 个结点的满二叉树的深度h = log 以2为底，n+1为对数。

推导：因为n=2^h-1;n+1=2^h;h=log以2为底，n+1为对数。

2.3 二叉树存储结构

2.3.1 顺序结构

顺序结构存储就是使用数组来存储，⼀般使用数组只适合表示完全二叉树，因为不是完全二叉树会有 空间的浪费，完全二叉树更适合使用顺序结构存储。

现实中我们通常把堆（⼀种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。

OK，那么咱们现在引入了堆的概念。

2.3.2 实现顺序结构二叉树

2.3.2.1  堆的概念与结构

那么堆是什么呢？那些晦涩难懂的概念咱们就不看了，堆就是一种特殊的二叉树，即用堆来存储这个二叉树。那么堆分为大堆与小堆。大堆或大根堆就是根节点是最大的，而小堆或小根堆就是根节点是最小的。

 

 堆 具有以下性质 ：

1.堆中某个结点的值总是不大于或不小于其父结点的值；

2. 堆总是⼀棵完全二叉树。（这个很重要）

二叉树性质
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从
开始编号，则对于序号为的结点有：

这个对于编号，即下标（从0开始，若是i与n的性质一样，都是表示数，那么下面的可以写成i/2.
1.若i>0，i位置结点的双亲序号：
（i-1)/2;i=0，i为根结点编号，无双亲结点
2. 若2i+1<n，左孩子序号:2i+1，2i+1>=n否则无左孩子
3.若2i+2くn，右孩子序号：2i+2，2i+2>=n否则无右孩子

咱们前面说了堆总是一颗完全二叉树，而咱又知道完全二叉树是有顺序的，也就是说，你要是想使用这个堆，你得先确保它是个堆，那么怎么确保呢？就是通过建堆的方法来确定。

下面咱们来介绍两种方法： 

1.向上调整法：

//向上调整
void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){    //小堆：  <//大堆:   >if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}

这个方法是如何调整的呢？它需要传的是孩子结点的位置。因为它是从下面（最后一个孩子节点开始调整）往上调整。那么接下来进行父节点与子节点进行比较，如果说你要建立的是大堆，那么你只需要保证父亲节点始终大于孩子节点即可。（如果孩子节点比父亲节点大了，没关系，swap一下即可）。那么接下来，将此时的父亲节点更新为孩子节点，并且重新更新父节点的位置。最后，重要的是：循环结束的条件是什么呢？是当你这个孩子节点不能到根节点，不然会导致父亲节点越界了，这就很难搞了。

时间复杂度：

为O（logh），h为树的高度，因为不管向上调整还是向下调整，移动的次数，都是树的高度。而时间复杂度，恰好是移动的次数，而树的高度怎么求呢？咱们呢有个公式h=log以2为底，n+1为对数。那么等号后面的这个就是时间复杂度，即logh。

2.向下调整法：

//向下调整
void AdjustDown(HPDataType* arr,int parent,int n)
{int child = parent * 2 + 1;while (child < n){//大堆： <//小堆: >if (child + 1 < n && arr[child] > arr[child + 1]){child++;}//大堆：>//小堆: <if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}

向上调整法是从最底下往上调整，那么向下调整法就是最根节点开始往下调整。这个地方要传两个重要的参数，即数组中数据的个数，还有就是父亲节点的下标。假如说你要建立大堆，那么你得确保你的孩子节点是最大的（因为一个父亲节点有两个子节点），这里为什么要确保你的孩子节点是最大的呢？因为你下面要swap呀，swap完后就是父亲节点最大了。swap完后，更新此时的孩子节点，让父亲节点移动此时的孩子节点，之后依靠新的父节点的位置更新子节点的位置。因为这是向下调整嘛，所以肯定得向下。那么最后循环结束的条件：你不能让孩子节点越界吧。而且这里在第一个if这得加一个右孩子节点不可以越界（因为会出现，左孩子不越界，但是右孩子越界了，这就很尴尬）。 

时间复杂度：

也是logh，h为树的高度。原因同上。

OK，介绍完这两种方法，再来看一下，建堆：

建堆---向下调整
for (int i = (n-1-1)/2; i >= 0; i--)
{AdjustDown(arr, i, n);
}建堆---向上调整
for (int i = 0; i < n; i++)
{AdjustUp(arr, i);
}

这里需要注意的是，对于第二种，在一个空数组中循环插入建 堆的，只能用向上建堆法，因为，你后边没有数据，如何进行向下调整呢？只有从插入的最后一个数据开始，向上调整即可。

并且，对于向下调整法建堆，是从最后一个非叶子节点开始的（循环开始的位置）。但是你真正传到向下调整法中，还是从根节点开始（即单趟的向下调整法是从根节点开始）。而建堆是多趟的向下调整（可以想象一下动态图），从最后一个非叶子节点开始调整，一直调整到最上边。

对于向上调整法建堆，直接循环插入数据即可，用向上调整法建堆。这个动图也可以想象出来，即从下标为0开始，一直到最后一个数据结束。

并且，两种方法既可以建立大堆，也可以建立小堆，而具体建立大堆还是小堆，是看你的向下调整法or向上调整法里的具体的实现细节（上面代码有）。

这里比较推荐向下调整法建堆，为什么呢？来看一下数学分析：

向上调整法建堆：

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使⽤满⼆叉树来证明(时间复杂度本 来看的就是近似值，多几个结点不影响最终结果)

分析： 第1层，个结点，需要向上移动0层 

第2层，个结点，需要向上移动1层

第3层，个结点，需要向上移动2层

第4层，个结点，需要向上移动3层

...... 第h层，个结点，需要向上移动h-1层 

则需要移动结点总的移动步数为：每层结点个数*向上调整次数（第一层调整次数为0)
①T(h) =2^1 *1+2^2*2+2^3 *3+ . +2^(h-2) *(h-2) +2^(h-1)*(h - 1)

②2*T(h)=2^2*1+2^3 *2+2^4 *3+.+2^(h-1) *(h-2) +2^h *(h-1)

②一①错位相减：
T(h) = -2^1 *1 - (2² +2^3 + .. +2^(h-2) +2^(h-1)) +2^h *(h - 1)
T(h) = -2° -2^1 *1- (2² +2^3 +..+2^(h-2)+2^(h-1)) +2^h *(h - 1)+2^0
T(h) = -(2^0 +2^1 *1+2² +2^3+ . +2^(h-2)+2^(h-1)) +2^h *(h - 1)+2^0
T(h) =-(2^h - 1) +2^h * (h- 1) +2^0
根据二叉树的性质：n=2^h-1和h=log2(n+1）
T(n) =-N+2^h * (h-1) +2^0
F(h) =2^(h-2) +2
F(n) = (n + 1)(log2(n + 1) - 2) +2
由此可得：
向上调整算法建堆时间复杂度为：O(n*log2 n),即n*logn

 向下调整法建堆：

分析：
第1层，2°个结点，需要向下移动h-1层
第2层，2^1个结点，需要向下移动h-2层
第3层，2^2个结点，需要向下移动h-3层
第4层，2^3个结点，需要向下移动h-4层
第h-1层，2^h-2个结点，需要向下移动1层 

所以，向下调整法建堆的时间复杂度是O（N）。

OK，咱们再来分析一下这段代码：

建堆---向下调整
for (int i = (n-1-1)/2; i >= 0; i--)
{AdjustDown(arr, i, n);
}建堆---向上调整
for (int i = 0; i < n; i++)
{AdjustUp(arr, i);
}

第一个时间复杂度是O（N），即（（n-2）/2）*logn可能就是n，这涉及到数学问题。

第二个时间复杂度：O（nlogn），即n*logn，完全吻合。

2.3.2. 2 堆的插入与删除数据

咱们一般是把堆的插入与向上调整法一起使用，堆的删除与向下调整法一起使用。原因后面讲。

1.堆的插入：（向上调整法）

1.先将元素插入到堆的末尾，即最后一个孩子之后
2.插入之后如果堆的性质遭到破坏，将新插入结点顺着其双亲往上调整到合适位置即可 

//向上调整
void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){    //小堆：  <//大堆:   >if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间足够if (php->size == php->capacity){//增容int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//直接插入php->arr[php->size] = x;//向上调整AdjustUp(php->arr, php->size);++php->size;
}

2.堆的删除（向下调整法）

 向下调整算法有一个前提：左右子树必须是一个堆，才能调整。（这个在咱们之前建堆的时候已经保证好了）
1.将堆顶元素与堆中最后一个元素进行交换
果
2.删除堆中最后一个元素
3.将堆顶元素向下调整到满足堆特性为止

//向下调整
void AdjustDown(HPDataType* arr,int parent,int n)
{int child = parent * 2 + 1;while (child < n){//大堆： <//小堆: >if (child + 1 < n && arr[child] > arr[child + 1]){child++;}//大堆：>//小堆: <if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}
void HPPop(HP* php)
{assert(!HPEmpty(php));//0  php->size-1Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//向下调整AdjustDown(php->arr, 0, php->size);
}

OK，咱们来讲一下为什么 堆的插入与向上调整法一起使用，堆的删除与向下调整法一起使用：

你要是插入用向下调整法，不合适，因为会做很多不必要的动作，插入是在末尾插入，那么你要使用向下调整法，向下调整法是从根节点开始，那么你从根节点一直到你要调整的那个数据，是不是都是多余的比较？因为你在插入之前，已经是一个堆了。那还不如直接用向上调整法，从插入的那个数据开始调整。

你要是删除用向上调整法的话，删除后，只有根节点变了，下面的还是一个堆呀（因为咱们之前已经调整过了），所以说用向上调整法，从最后一个节点一直到根节点，都是多余的比较，那为啥不直接用向下调整法，从根节点开始调呢？

OK，明白了吧，其实就是减少冗余的步骤。

2.3.2.3 堆排序

前面咱们已经实现了建堆。那么如果咱们想将一个无序数组排成有序的，必须得两个步骤，先建堆，之后再进行堆排序。来看堆排序的代码：

//堆排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}

排升序用大堆（因为每次大堆堆顶都是这次的堆的最大值，而将这个最大值取出后放在最后，这个最大值就是整个升序数组中的最大值，压轴的存在）

排降序用小堆。原理同上。即降序的数组最后就是整个的最小的数据。

这个堆排序既可以实现排升序，也可以实现排降序，而具体怎么样，要看前面的是小堆还是大堆。

建堆---向下调整
for (int i = (n-1-1)/2; i >= 0; i--)
{AdjustDown(arr, i, n);
}
堆排序
int end = n - 1;
while (end > 0)
{Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;
}建堆---向上调整
for (int i = 0; i < n; i++)
{AdjustUp(arr, i);
}堆排序
int end = n - 1;
while (end > 0)
{Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;
}

OK，那么再来看看堆排序的时间复杂度呢？

 

分析：
第1层，2^0个结点，交换到根结点后，需要向下
移动0层
第2层，2^1个结点，交换到根结点后，需要向下
移动1层
第3层，2^2个结点，交换到根结点后，需要向下
移动2层
第4层，2^3个结点，交换到根结点后，需要向下
移动3层
第h层，2^(h-1)个结点，交换到根结点后，需要向
下移动h-1层 

 

这个n哪来的呢？是向下调整法建堆的时间复杂度。再加上第二个循环的时间复杂度，就是堆排序的时间复杂度。

OK，将堆的最主要最重要的部分讲完了。 

2.3.2.4 堆一些杂于实现

//堆的结构
typedef int HPDataType;
typedef struct Heap 
{HPDataType* arr;int size;      //有效数据个数int capacity;  //空间大小
}HP;
//堆的初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
//堆的销毁
void HPDestroy(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}
//堆的打印
void HPPrint(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}
//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//取堆顶元素
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

OK，可算是把堆的东西给讲完了。

2.3.3 实现链式结构二叉树 

用链表来表示⼀棵二叉树，即⽤链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组 成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址， 其结构如下：

typedef char BTDataType;
typedef struct  BinaryTreeNode
{struct  BinaryTreeNode* left;// 
指向当前结点左孩⼦struct  BinaryTreeNode* right; // 
指向当前结点右孩⼦BTDataType data;// 
当前结点值域}BTNode;

接下来让咱们手动来实现一颗二叉树吧，实现模型以及代码如下：

 

BTNode* buynode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
BTNode* creatBinaryTree()
{BTNode* node1 = buynode('A');BTNode* node2 = buynode('B');BTNode* node3 = buynode('C');BTNode* node4 = buynode('D');BTNode* node5 = buynode('E');BTNode* node6 = buynode('F');node1->left = node2;node1->right = node3;node2->left = node4;/*node2->right = node5;*/node3->left = node5;node3->right = node6;return node1;
}

2.3.3.1 二叉树的遍历：

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1）前序遍历(PreorderTraversal亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前 访 问顺序为：根结点、左子树、右子树

2）中序遍历(InorderTraversal)：访问根结点的操作发⽣在遍历其左右子树之中（间） 访 问顺序为：左子树、根结点、右子树

3）后序遍历(PostorderTraversal)：访问根结点的操作发⽣在遍历其左右子树之后 访 问顺序为：左子树、右子树、根结点

代码：

//前序遍历
void preOrder(BTNode* root)
{if (root == NULL){printf("NULL");return NULL;}printf("%c", root->data);preOrder(root->left);preOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL");return NULL;}InOrder(root->left);printf("%c", root->data);InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL");return NULL;}PostOrder(root->left);PostOrder(root->right);printf("%c", root->data);
}

 

 

由于涉及到递归，所以咱们来看一个前序遍历的递归图。 是挺复杂的，但也没有很复杂。你只要是搞清他们之间的关系就没什么问题。

注意：递归的时候，这行代码正在递归并不等于这行代码已经递归完了。

2.3.3.2 二叉树的几个操作

那么咱们下面实现另外的几个操作：都是用递归实现的：

以下都是以上面这个为模型。 

1.二叉树的节点个数

//二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

这个也是用递归版本实现的。

来看本作者画的一个递归的理解的思维导图，也是很好理解的。

2.二叉树叶子结点的个数 =左子树叶子节点加上右子树叶子节点

// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

这也是比较好理解的。

3.二叉树第k层节点的个数 

// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

 

4. 二叉树的深度/高度

 

int BinaryTreeDepth(BTNode* root)
{if(root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return 1 + (leftDep > rightDep ? leftDep : rightDep);
}

 5.二叉树查找值为x的结点

 

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}

这个也是用的递归写的，即如果当前的根节点不是的，那么就往左右子节点中去找即可。

6.二叉树的销毁

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

 这里由于要改变二叉树，所以传的是二级指针。

7.层序遍历----队列

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头出队头，打印结点值BTNode* top = QueueFront(&q);QueuePop(&q);printf("%c ", top->data);//将队头结点的非空左右孩子结点入队列if (top->left)QueuePush(&q, top->left);if (top->right)QueuePush(&q, top->right);}QueueDestroy(&q);
}

 首先，函数名为LevelOrder，参数是BTNode指针root，看起来是二叉树的根节点。函数内部创建了一个队列q，并进行了初始化。然后，将根节点入队。接下来进入一个循环，条件是队列不为空。在循环内部，取出队头元素并出队，打印该节点的数据。然后检查该节点的左右子节点，如果有非空的子节点，就将它们入队。最后，销毁队列。

整个的逻辑就是：首先根节点入队，然后循环处理队列中的节点，处理完一个节点后将其子节点入队。这样就能按层次遍历整个二叉树。

8.判断二叉树是否是完全二叉树

bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);
//根节点入队，开始层次遍历。while (!QueueEmpty(&q)){//取队头，出队头BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){break;}//队头结点的左右孩子入队列QueuePush(&q, top->left);QueuePush(&q, top->right);}
//入队所有子节点：无论子节点是否为空，均入队，确保后续能检测到结构异常。//终止条件：遇到第一个空节点时跳出循环，后续可能仍有未处理的节点。//队列不为空，继续取队头出队头//1）队头存在非空结点----非完全二叉树//2）队头不存在非空结点----完全二叉树while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
//剩余节点必须全为空：若存在非空节点，说明在空节点后仍有数据，违反完全二叉树
}

这段代码首先通过层次遍历，将节点依次入队，包括NULL节点。当遇到第一个NULL节点时，停止遍历，然后检查队列中剩下的节点是否都是NULL。如果有任何非NULL的节点存在，说明树不是完全二叉树。否则，是完全二叉树。这种方法的时间复杂度是O(n)，因为每个节点最多被访问两次。空间复杂度是O(n)，因为队列中可能需要存储最多n个节点。

2.3.3.3 二叉树的性质：

对任何一棵二叉树,如果度为0
其叶结点个数为n1，度为2的分支结点个数为n2.，则有
n1 = n2+1

 

证明上述性质：

假设⼀个二叉树有 2a+b a 个度为2的节点， b 个度为1的节点， c 个叶节点，则这个二叉树的边数是

另⼀方面，由于共有 a+b+c 个节点，所以边数等于 a+b+c-1

结合上面两个公式： 2a+b = a+b+c-1 ，即： a = c-1 。

OK，那么以上就是本篇要讲的全部内容，内容很多很多，本人写也花了很多时间。

希望大家下去可以好好研读。

本篇完....................