目录
1.树概念及结构
1.1树的概念
树是一种非线性的数据结构,它是由 n (n>=0) 个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
● 有一个特殊的结点,称为根结点,根结点没有前驱结点
● 除根结点外,其余结点被分成 M(M>0) 个互不相交的集合T1、T2 、……、 Tm,其中每一个集合 Ti(1 <= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
● 因此,树是递归定义的。（任何一颗树都可以分成一个根结点和 n 颗子树，子树又分为一个根结点和 n 颗子树）
树与非树（图）？
- 子树是不相交的;
- 除了根结点外,每个结点有且仅有一个父结点;
- 一棵N个结点的树有N-1条边。
1.2树的相关概念
- 结点的度:一个结点含有的子树的个数称为该结点的度;如上图:A的为6
- 叶结点或终端结点:度为0的结点称为叶结点;如上图:B、C、H、I ... 等结点为叶结点
- 非终端结点或分支结点:度不为0的结点;如上图: D、E、F、G ... 等结点为分支结点
- 双亲结点或父结点:若一个结点有子结点,这个结点为其子结点的父结点;如上图:A是B的父结点
- 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点;如上图:B是A的子结点
- 兄弟结点:具有相同父结点的结点互称为兄弟结点;如上图:B、C是兄弟结点
- 树的度:一棵树中,最大的结点的度称为树的度;如上图:树的度为6
- 结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推;
- 树的高度或深度:树中结点的最大层次;如上图:树的高度为4（根结点可以认为是第 1 层，也可以认为是第 0 层，推荐将根结点作为第 1 层，原因是如果将根结点作为第 0 层，那么空树的高度或深度就是 -1 了）
- 堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图:H、I互为兄弟结点
- 结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先
- 子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙
- 森林:由m (m>0)棵互不相交的树的集合称为森林;
1.3树的表示
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既要保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法（左孩子右兄弟表示法）。
思考：现在给你一颗树，如何定义树的结点的结构呢？
先尝试一下吧：
struct TreeNode
{
struct TreeNode* child1;
struct TreeNode* child2;
struct TreeNode* child3;
//...不知道有多少个孩子。
int data;
};
问题来了：不知道有多少个孩子。那如果已知树的度是 5 呢 ：
//树的度为 N
#define N 5
struct TreeNode
{
struct TreeNode* childrenA[N]; // 指针数组
int data;
};
也就只能在已知树的度是 5 的情况下才能这样定义，那如果不知道树的度呢？
......
还是看看大佬如何定义的吧：
typedef int DataType;
struct TreeNode
{
struct TreeNode* firstChild1; // 第一个孩子结点
struct TreeNode* pNextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
结构分析：不管一个结点有多少个孩子，这个结点都只指向它的某一个孩子， 这个结点的其他孩子，像单向不循环链表一样，以这个结点的那个被指向的孩子为头结点，被链接成一个链表的结构。
1.4 树在实际中的运用
(表示文件系统的目录树结构)
2.二叉树概念及结构
2.1二叉树的概念
一棵二叉树是结点的一个有限集合,该集合:
1. 或者为空
2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成
从上图可以看出:
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
注意:对于任意的二叉树都是由以下几种情况复合而成的:
2.2特殊的二叉树
1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。
如果一个二叉树的层数为K,且结点总数是 2^k-1 ,则它就是满二叉树。
2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。（完全二叉树：前 k - 1 层都是满的，最后一层要求从左到右是连续的）
注意：这种情况不是完全二叉树：
满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树
完全二叉树结点的数量取值范围：[ 2^( h - 1 ) 到 2^h - 1 ]
2.3 二叉树的性质
1. 若规定根结点的层数为1, 则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点.
2. 若规定根结点的层数为1, 则深度为 h 的二叉树的最大结点数是 2^h-1.
3. 对任何一棵二叉树,如果其叶结点个数为 n0 , 度为2的分支结点个数为 n2 ,则有 n0 = n2 + 1（对于任何一颗完全二叉树，n1 要么等于 0，要么等于 1。若 n 是结点数，要根据 n 、n0、n1、n2 一定是整数的性质来解题）
4. 若规定根结点的层数为1, 则具有n个结点的满二叉树的深度 h=log(n+1). (ps: log是以2为底的对数)
5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号,则对于序号为 i 的结点有:
1. 若 i > 0 , i 位置结点的双亲序号: (i - 1)/2; 若 i == 0, i 为根结点编号 , 无双亲结点
2. 若 2i+1 < n , i 位置结点的左孩子序号: 2i+1 , 若 2i+1>=n 则无左孩子
3. 若 2i+2 < n , i 位置结点的右孩子序号: 2i+2 , 若 2i+2>=n 则无右孩子
2.4二叉树的存储结构
1. 顺序存储结构
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
2. 链式存储结构
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,高阶数据结构如红黑树等会用到三叉链。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data;// 当前结点值域
};
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* parent; // 指向当前结点的双亲
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data;// 当前结点值域
};
3.二叉树的顺序存储结构及实现
3.1 二叉树的顺序结构
普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。
3.2 堆的概念及结构
如果有一个关键码（就是堆中的数据）的集合 K={ k0,k1,k2, .... k(n-1) },把它的所有元素按完全二叉树的顺序存储存方式存储存在一个一维数组中,并满足 : Ki <= K(2i+1) 且 Ki <= K(2i+2) (Ki >=K(2i+1) 且 Ki >=K(2i+2)) i=0, 1, 2 ... , 则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。
堆的性质:
● 堆中某个结点的值总是不大于或不小于其父结点的值;
● 堆总是一棵完全二叉树。
以上图的大堆为例，介绍堆的相关功能：
插入 20：
数组尾插 20 后，将 20 的下标（ i - 1 ）/ 2 后找到 20 的父亲 30 ，30 > 20 , 仍然满足大根堆的定义，20 的祖先（30、70）的位置没有影响，接下来插入 60：
数组尾插 60 后，将 60 的下标（ i - 1 ）/ 2 后找到 60 的父亲 25 ，由于 60 > 25 ，不满足大根堆的定义，需要将 60 和 25 的位置互换：
再将 60 的下标（ i - 1 ）/ 2 后找到 60 的父亲 56，将 25 的下标（ i - 1 ）/ 2 后找到 25 的父亲 60，发现 60 还是大于 56，于是将 60 和 56 的位置互换：
再将 60 的下标（ i - 1 ）/ 2 后找到 60 的父亲 70，将 56 的下标（ i - 1 ）/ 2 后找到 56 的父亲 60，发现 60 小于 70，符合大根堆，调整结束。
上述过程叫做向上调整，最多调整 logN 次（N 是结点数量）
3.3堆的实现
接下来用代码实现一个大堆：（C）
一、定义一个堆
a：指向动态开辟内存的数组的首地址
size：当前堆的结点个数
capacity：当前堆的最大容量
二、堆初始化函数
三、堆插入函数
每次插入一个元素，都要向上调整一次，这样使得每次插入一个元素后，都能立刻调整使之仍然保持大堆的特征。这样所有元素插入完了，堆也就建好了。
四、向上调整函数
注意：
1、将 > 改成 < 就变成了建小堆
2、函数的参数是 HPDataType* a（数组），而不是 HP* php（堆结构体），目的是在堆排序中也能使用该函数，下面的 AdjustUp 函数同理。
3、Swap 函数是用来交换变量的值的。
五、堆 pop 函数
思考：堆删除一个元素，是删除最大的根结点 ，还是删除较小的叶子呢？答案是删除最大的根结点，因为删除最大的根结点具有更多的现实意义：在一些元素中选出前几名。而在一些元素中选出最后几名的意义不大。
如果直接删除最大的根结点（数组首元素），然后挪动数据往前覆盖，这种做法一是效率低，二是将父子兄弟的关系全打乱了。为了解决这个问题，有大佬想出这样一个办法：将物理结构的数组的最后一个元素（叶子）与数组首元素互换，然后删除数组的最后一个元素，这样就最大化保持了父子兄弟的关系，而堆的最大的根结点（数组首元素）与其余元素的关系不满足大堆的特点，此时采取向下调整，使它重新变成一个大堆。
如何向下调整使它重新变成一个大堆：
从根结点开始，选出根结点左右孩子中大的那一个，如果这个孩子大于根结点，就将它们互换，再以根结点左右孩子中大的那一个为父结点，重复上述过程。
六、向下调整函数
注意：
1、向下调整的前提是左右子树都是大堆或小堆
2、小心数组越界，if 括号内要判断是否存在右孩子。由于 && 的短路性，if 括号内不能写成 a[child + 1] > a[child] && child + 1 < n 。
3、采用假设的方法，假设默认是左孩子大，如果假设错误就调整，这样可以避免代码冗余。
4、建立大堆的另一种方法：
上面建立大堆的方法是：每次插入一个元素，都从这个元素开始向上调整，所有元素插入完了，堆也就建好了。建立大堆还有另一种方法，就是将所有元素都一次性插入到堆，再以倒数第一个非叶子结点（最后的一个最小子树的根，也就是最后一个结点的父亲）开始，向下调整，再以这个根的上一个根开始，直到以整个堆的根开始，向下调整后，一个大堆就建好了，这种向下调整建堆的方法比向上调整建堆的方法效率更高。一般使用这种方法来建立堆
七、堆删除函数
建堆的时间复杂度
因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个结点不影响最终结果):
向下调整建堆的时间复杂度：
设 T(N) 是调整结点位置的总次数，h 是完全二叉树的层数，以最坏的情况来看，倒数第二层一共要调整的次数有：
2 ^ ( h - 2 ) * 1 次 （向下调整建堆从倒数第二层开始调整，倒数第二层一共有 2^( h - 2 ) 颗子树，每颗子树都调整结点位置一次）
倒数第三层一共要调整的次数有：
2 ^ ( h - 3 ) * 2 次 （ 倒数第三层一共有 2^( h - 3 ) 颗子树，每颗子树都调整结点位置两次）
以此类推，调整结点位置的总次数：
T(N) = 2 ^ ( h - 2 ) * 1 + 2 ^ ( h - 3 ) * 2 + 2 ^ ( h - 4 ) * 3 + ... + 2 ^ 1 * ( h - 2 ) + 2 ^ 0 * ( h - 1)
这是等差乘以等比，使用错位相减法，得：
T(N) = 2 ^ h - 1 - h
又因为 h = log（N - 1） ( N 是结点个数）
即 T(N) = N - 1 - 1 - logN
所以，向下调整建堆的时间复杂度是O(N)。
向上调整建堆的时间复杂度：
设 T(N) 是调整结点位置的总次数，h 是完全二叉树的层数，以最坏的情况来看，第二层一共要调整的次数为：
2 ^ 1 * 1（第二层一共有 2 ^ 1 个结点，每个结点都要往上调整一次）
第三层一共要调整的次数为：
2 ^ 2 * 2
以此类推，第 n 层一共要调整的次数为：
2 ^ (h-1) * (h-1)
所以：
T(N) = 2 ^ 1 * 1 + 2 ^ 2 * 2 + .... + 2 ^ (h-2) * (h-2) + 2 ^ (h-1) * (h-1)
使用错位相减法化简得：
T(N) = - 2 ^ h + 2 + 2 ^ h * h - 2 ^ h
又因为 h = log（N - 1） ( N 是结点个数）
所以：
T(N) = - ( N - 1) + 2 + log（N - 1）* ( N - 1 ) - ( N - 1 )
所以，向上调整建堆的时间复杂度是O(N*logN)。
对比：向下调整建堆是：随着调整的进行，每层的结点数在增加，但是从每个结点开始的调整次数越来越少。向上调整建堆是：随着调整的进行，每层的结点数在增加，从每个结点开始的调整次数也在增加。
3.4堆排序
以上的堆已经有排序功能了，但它的排序只是有序打印，接下来使用堆的思想来对数组排序
HeapSort 函数
函数原型：
void HeapSort ( int*a , int n )
a: 待排序的数组的数组名，n：数组元素个数
如果 HeapSort 函数一开始就建立一个堆，然后把数组的所有元素 push 进堆，再 pop 到数组，会有很大的弊端：
1、空间复杂度为O(N)
2、考试时要从头写堆的所有接口，很麻烦
所有我们要使用堆的思想直接对数组排序：
以下是排升序的例子：
先以数组下标为 1 的元素开始，将它作为孩子，然后向上调整，再以下标为 2 的元素向上调整，直到数组最后一个元素，这一步就是在模拟建一个大堆。
然后再根据堆 pop 的思想，模拟堆 pop 的过程，每次 “pop” 出数组最大的元素，将 “pop” 出的元素排在数组倒数第一个位置、倒数第二个位置、倒数第三个位置......，这样，数组就排好升序了。
上文说过，向下调整建堆的方法比向上调整建堆的方法效率更高，所以在该函数中模拟建一个大堆时我们也可以采取向下调整建堆的方法。
注意：
排升序不能建小堆，因为建好小堆之后，最小的元素在根上了，如果把接下来的元素看成一个堆，接下来的元素的关系就全乱了，又要重新建好小堆，其效率还不如每次遍历找最小的元素。
所以，排升序要建大堆：(排降序要建小堆）
建好大堆后，用 pop 的思想将数组的首元素（此时它就是最大的元素）与末尾的元素互换，然后向下调整，向下调整时，将数组元素的个数减一，即将末尾的元素（那个最大的元素）排除在外，因为它已经排好了，向下调整后，数组的首元素就是第二大的元素，以此类推。
堆排序的时间复杂度
上文已经证明，向下调整建堆的时间复制度是 O(N)，
接下来看看用堆 pop 的思想调整顺序的时间复制度：
排好堆最后一层（数组的后 2 ^（h - 1）个元素）的顺序所需的调整元素的次数为：
2 ^ ( h - 1) * ( h - 1)（堆最后一层一共有 2 ^ ( h - 1) 个结点，每次互换结点后要调整 h - 1 次）
以此类推，设 T(N) 是调整结点位置的总次数，h 是完全二叉树的层数，以最坏的情况来看，
T(N) = 2 ^ 1 * 1 + 2 ^ 2 * 2 + .... + 2 ^ (h-2) * (h-2) + 2 ^ (h-1) * (h-1)
所以，用堆 pop 的思想调整顺序的时间复制度是 O(N * logN)。
所以，不管堆排序中使用向上还是向下调整建堆，时间复制度都是 O(N * logN)。
综上所述，堆排序的时间复杂度是 O(N * logN)
TOP-K问题
即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-Ki问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大（10000亿）,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
○ 前k个最大的元素,则建小堆
○ 前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素后向下调整
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
4.二叉树的链式存储结构及实现
4.1二叉树的遍历
前序、中序以及后序遍历
学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的结点进行相应的操作,并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。
按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:
以这颗二叉树为例：
1. 前序遍历(Preorder Traversal) -- 访问根结点的操作发生在遍历其左右子树之前。
根 --> 左子树 --> 右子树
2. 中序遍历(Inorder Traversal) -- 访问根结点的操作发生在遍历其左右子树之间。
左子树 --> 根 --> 右子树
3. 后序遍历() -- 访问根结点的操作发生在遍历其左右子树之后。
左子树 --> 右子树 --> 根
4. 层序遍历 -- 按照二叉树层的先后依次访问每个结点。
1 2 3 4 5 6
4.2二叉树链式结构的实现
在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研究二叉树真正的创建方式。
手动创建这颗二叉树：
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode (BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
BTNode* CreatTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}
注意：以上代码不是真正创建二叉树的方式
4.3二叉树的一些简单操作
假设将打印作为访问结点的方式，通过函数的递归调用，完成遍历。
前序遍历：
void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); }中序遍历：
void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }层序遍历：使用队列
void LevelOrder (BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%d ", front->data); if(front->left) QueuePush(&q, front->left); if(front->right) QueuePush(&q, front->right); } QueueDestroy(&q); }后序遍历：
void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
求结点个数函数：
void TreeSize(BTNode* root)
{
if (root == NULL)
return;
++size;
TreeSize(root->left);
TreeSize(root->right);
}
缺点：size 是定义在函数外的全局变量，每次调用这个函数，都要重置 size 的值为 0。
另一种方式：
void TreeSize(BTNode* root, int* psize)
{
if (root == NULL)
return;
++(*psize);
TreeSize(root->left, psize);
TreeSize(root->right, psize);
}
使用举例：
int size1 = 0;
TreeSize(root, &size1);
printf("TreeSize:%d\n", size1);
int size2 = 0;
TreeSize(root, size2);
printf("TreeSize:%d\n", size2);这种方式虽然可以将 size 做不同的区分，但仍然不够简洁。
使用分治的思想，想象每个根结点指挥左右子树报告它们的结点数，而每个左右子树的根结点又指挥左右子树报告它们的结点数，直到叶子结点返回 1。
int TreeSize(BTNode* root)
{
return root == NULL ? 0 :
TreeSize(root->left)
+ TreeSize(root->right)
+ 1;
}0：叶子结点的左右子树的结点数是 0。
TreeSize(root->left) ：左子树的结点数。
TreeSize(root->right) ：右子树的结点数。
+1 ： 根结点往上“报告”结点数时，要算上自己。
求树的深度函数：
仍然采用分治的思想，即：当前树的深度 == 左右子树深度大的那个的深度 + 1，如果左右子树是 NULL，则返回 0。
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return TreeHeight(root->left) > TreeHeight(root->right)
? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}
以上代码存在很大的效率问题：三目运算符判断真假后，知道表达式的结果该选哪一个，但由于它没有记住 TreeHeight(root->left) 或 TreeHeight(root->right) 的值，所以它又去调用了一次 TreeHeight 函数，而问题是每个结点都会这样做，这就导致效率低下。
所以要把左右子树的深度记下来：
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
求第 K 层的结点个数：
int TreeKLevel(BTNode* root, int k)
{
assert( K > 0 );
if (root == NULL)
return 0;
if (k == 1)
return 1;
return TreeKLevel(root->left, k - 1) +
TreeKLevel(root->right, k - 1);
}寻找值为 x 的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* lret = BinaryTreeFind(root->left, x);
if (lret)
return lret;
BTNode* rret = BinaryTreeFind(root->right, x);
if (rret)
return rret;
return NULL;
}判断是否是完全二叉树
// 判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if(root)
QueuePush(&q, root);
while(!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
else
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
// 判断是不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//后面有非空,说明非空节点不是完全连续
if(front)
{
QueueDestroy(&q);//小心内存泄漏
return false;
}
}
QueueDestroy(&q);
return true;
}思路：运用层序遍历（不同的是，NULL 也进队列），当队列第一次 pop 出 NULL 后，检查后面还有没有非空指针，如果有，说明不是完全二叉树。
二叉树的销毁
void TreeDestory(BTNode* root)
{
if (root == NULL)
return;
TreeDestory(root->left);
TreeDestory(root->right);
free(root);
}
采用后序遍历的顺序销毁结点，如果采用其他顺序，在销毁之前还要保存结点的地址。