30 树 · 二叉树

一、树

（一）树的概念与结构

（二）树相关术语

（三）树的表示

（四）树形结构的实际应用场景

二、二叉树

（一）概念与结构

（二）特殊的二叉树

（三）二叉树的存储结构

1、顺序结构

2、链式结构

三、顺序结构二叉树的实现

（一）堆的概念与结构

（二）堆的实现

（三）堆的使用

1、堆排序

（1）实现过程

（2）代码实现

（3）堆排序的时间复杂度

（4）总结

2、top-k问题

（1）解决思路

（2）实现过程

（3）代码实现

四、链式结构二叉树的实现

（一）前中后序遍历

1、遍历规则

2、代码实现

（二）节点个数以及高度等代码实现

（三）层序遍历

（四）代码总汇

五、二叉树算法题

（一）单值二叉树

（二）相同的树

（三）对称二叉树

（四）另一棵子树

（五）二叉树遍历

1、前序遍历

2、中序遍历

3、后续遍历

（六）二叉树的构建及遍历

六、二叉树选择题

一、树

（一）树的概念与结构

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

注意：

① 有一个特殊的结点，称为根结点，根结点没有前驱结点。

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

③ 树形结构中，子树之间不能有交集，否则就不是树形结构。

非树形结构如下所示：

④ 有 n 个节点的数有 n-1 条边。

（二）树相关术语

父结点/双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：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）棵互不相交的树的集合称为森林。

（三）树的表示

孩子兄弟表示法：

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

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

表示如下所示：

（四）树形结构的实际应用场景

文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被⼴泛应⽤，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。

如下图所示：

二、二叉树

（一）概念与结构

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

从上图可以看出⼆叉树具备以下特点：

① 二叉树不存在度大于 2 的结点。

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

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

（二）特殊的二叉树

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

二叉树的性质：

① 第 i 层节点数：若规定根结点的层数为 1 ，则一棵非空二叉树的第 i 层上最多有 2^(i−1) 个结点。

② 最大结点数：若规定根结点的层数为 1 ，则深度为 h 的二叉树的最大结点数是 2^h − 1。

③ 求高度：若规定根结点的层数为 1 ，具有 n 个结点的满二叉树的深度 h = log2 (n + 1) ( log以2为底， n+1 为对数）。

（三）二叉树的存储结构

⼆叉树一般可以使用两种结构存储，⼀种顺序结构，⼀种链式结构。

1、顺序结构

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

使用顺序结构存储完全二叉树与非完全二叉树的区别如下：

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

2、链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为⼆叉链和三叉链，当前学习中一般都是二叉链。后面数据结构如红黑树等会用到三叉链。

二叉链与三叉链如下所示：

三、顺序结构二叉树的实现

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性。

（一）堆的概念与结构

如果有一个关键码的集合 K = {k0 , k1 , k2 , ...，kn−1 } ，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足： Ki <= K2∗i+1 （ Ki >= K2∗i+1 且 Ki <= K2∗i+2 ）， i = 0、1、2... ，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

注意：

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

堆总是一颗完全二叉树。

二叉树的性质：

对于具有 n 个结点的完全⼆叉树，如果按照从上至下从左至右的数组顺序对所有结点从

0 开始编号，则对于序号为 i 的结点有：

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 否则无右孩子。

对任何⼀棵⼆叉树, 如果度为 0 其叶结点个数为 n0 , 度为 2 的分支结点个数为 n2 ,则有

n 0 = n 2 + 1。

（二）堆的实现

堆的常用名Heap。

堆的编写：

① 头文件：定义堆的结构体，声明要提供的操作（起到目录作用）。

② cpp文件：编写具体实现各种操作（起到内容作用）。

Heap.h

#pragma once
#include<stdlib.h>
#include<iostream>
#include<assert.h>
#include<stdbool.h>
#include<time.h>using namespace std;
typedef int HPDataType;typedef struct Heap
{HPDataType* arr;int capacity;//最大容量int size;//有效元素个数
}HP;//一、堆的初始化与销毁
//（一）初始化
void HPInit(HP& hp);
//（二）销毁
void HPDestroy(HP& hp);
//（三）元素交换
void Swap(HPDataType& x, HPDataType& y);//二、堆的插入
//（一）小堆的向上调整
void HPAdjustUp_S(HPDataType*& arr, int child);
//（二）大堆的向上调整（只需改小堆的向上调整的孩子节点与父节点的比较即可）
void HPAdjustUp_B(HPDataType*& arr, int child);
//（三）插入
void HPPshu(HP& hp, HPDataType num);//三、堆的删除（删除的是头元素）
//（一）小堆的向下调整
void HPAdjustDowm_S(HPDataType*& arr, int parent, int n);
//（二）大堆的向下调整
void HPAdjustDowm_B(HPDataType*& arr, int parent, int n);
//（三）删除
void HPPop(HP& hp);//四、取栈顶元素
HPDataType HPGetTop(HP& hp);//五、判空
bool HPEmpty(HP& hp);

Heap.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"//一、堆的初始化与销毁
//（一）初始化
void HPInit(HP& hp)
{hp.arr = nullptr;hp.capacity = hp.size = 0;
}
//（二）销毁
void HPDestroy(HP& hp)
{if (hp.arr)free(hp.arr);hp.arr = nullptr;hp.capacity = hp.size = 0;
}
//（三）元素交换
void Swap(HPDataType& x, HPDataType& y)
{HPDataType temp = 0;temp = x;x = y;y = temp;
}//二、堆的插入（尾插，然后向上调整）
//（一）小堆的向上调整
void HPAdjustUp_S(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;}elsebreak;}
}
//（二）大堆的向上调整（只需改小堆的向上调整的孩子节点与父节点的比较即可）
void HPAdjustUp_B(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;}elsebreak;}
}
//（三）插入
void HPPshu(HP& hp, HPDataType num)
{//检查空间是否足够并扩容if (hp.size == hp.capacity){hp.capacity = hp.capacity == 0 ? 4 : 2 * hp.capacity;HPDataType* new_arr = (HPDataType*)realloc(hp.arr, sizeof(HPDataType) * hp.capacity);if (new_arr == nullptr){perror("HPPush realloc fail !");exit(1);}hp.arr = new_arr;}//插入数据hp.arr[hp.size] = num;//小堆的向上调整HPAdjustUp_S(hp.arr, hp.size);hp.size++;
}//三、堆的删除（目的是删堆顶，要先交换，进行尾删，再向下排序）
//（一）小堆的向下调整
void HPAdjustDowm_S(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[parent] > arr[child])//交换父节点与孩子节点，移动节点位置{Swap(arr[parent], arr[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
//（二）大堆的向下调整
void HPAdjustDowm_B(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[parent] < arr[child])//交换父节点与孩子节点，移动节点位置{Swap(arr[parent], arr[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
//（三）删除，删除的是堆顶数据
void HPPop(HP& hp)
{assert(hp.arr);//交换Swap(hp.arr[0], hp.arr[hp.size - 1]);//减一hp.size--;//向下调整HPAdjustDowm_S(hp.arr, 0, hp.size);//参数为：需要调整的数组，父母节点位置，有效数据个数
}//四、取栈顶元素
HPDataType HPGetTop(HP& hp)
{assert(hp.arr);return hp.arr[0];
}//五、判空
bool HPEmpty(HP& hp)
{return hp.size == 0;
}

注意：

1.向上调整算法：

① 先将元素插⼊到堆的末尾,即最后⼀个孩子下标size的位置；

② 插入之后如果堆的性质遭到破坏，将新插入结点顺着其双双亲往上调整到合适位置即可。如下图所示：

③ 向上调整算法建堆时间复杂度为： O(n ∗ log2 n)。

2.向下调整算法：

删除堆是删除堆顶的数据，将堆顶的数据根最后⼀个数据⼀换，然后删除数组最后⼀个数据，再进行向下调整算法。如下图所示：

向下调整算法的过程：

（前提：左右子树必须是一个堆才能调整）

① 将堆顶元素与堆中最后一个元素进行交换。

② 删除堆中最后一个元素。

③ 将堆顶元素向下调整到满足堆特性为止。如下图所示：

④ 向下调整算法建堆时间复杂度为： O(n)。

总结：使用向下调整算法来建堆更优。

（三）堆的使用

1、堆排序

堆排序：使用堆结构进行排序。（堆这个数据结构存在的主要用处）

（1）实现过程

第一步：建堆（进行一次向上排序/向下排序，形成小堆或大堆排序）

排升序：建大堆；排降序：建小堆。

可使用向上调整法进行建堆，也可以使用向下调整法建堆；若使用向上调整法，逻辑与之前的代码一样；若使用向下调整法建堆，思路如下：

向下调整建堆的算法：若在大根堆中，从最后一个节点(下标为：size-1)的父节点(下标为：（size-2）/ 2)开始调整，依次把最下层的子树使用向下调整排序，i 不断--，这个过程中 i 都是叶子节点的父节点，且向下调整的范围越来越大，先是最后一颗子树的大小，最后变成调整整个二叉树的大小。

总结：优先使用向下调整算法来建堆，因为向下调整算法的时间复杂度更优。

第二步：排序

小堆：先首尾交换（有效数据 - 1），剩下的数据使用小堆的向下调整法，把首元素调到最小。重复以上操作即可。

大堆：先首尾交换（有效数据 - 1），剩下的数据使用大堆的向下调整法，把首元素调到最大。重复以上操作即可。

（2）代码实现

堆排序中使用了部分上文中堆相关代码：

//堆排序
//空间复杂度为O(1)，只用堆这个数据结构进行排序，不额外借助其他的数据结构
void HeapSort(HPDataType* arr, int size)//堆排序，传入需要排序的数组，和数组的有效长度
{//一、建堆（建小堆则是降序排序，建大堆则是升序排序）：//（一）使用向上调整建堆的堆排序（时间复杂度不如向下调整建堆）//1、建小堆//for (int i = 0; i < size; i++)//{//	HPAdjustUp_S(arr, i);//直接拿数组过来进行向上调整建成小堆//}//2、建大堆//for (int i = 0; i < size; i++)//{//	HPAdjustUp_B(arr, i);//直接拿数组过来进行向上调整建成小堆//}//（二）向下调整建堆的堆排序（时间复杂度最优）// 思想为：从最后一棵子树开始，每一棵子树都进行向下调整，越往上(i--)，需要调整的子树越大，最后来到根结点的位置进行整棵树的向下调整。//1、向下调整建大堆for (int i = (size - 2) / 2; i >= 0; i--)//注意 i 是最后一棵子树的父结点的起始位置（(size - 1 - 1) / 2），size-1为最后一个结点的下标。{HPAdjustDowm_B(arr, i, size);}//二、打印cout << "建小根堆：" << endl;//cout << "建大根堆：" << endl;for (int i = 0; i < size; i++){cout << arr[i] << " ";}cout << endl;//三、堆排序（利用的是大根堆和小根堆的根节点是整个数组中最大或者最小值的特性来进行排序的）//先把最大或者最小值向后调，下标--，让向后调的最大或者最小值出了数组的调整范围，如此往复循环。int end = size - 1;//有效元素下标while (end > 0){Swap(arr[0], arr[end]);//HPAdjustDowm_S(arr, 0, end);HPAdjustDowm_B(arr, 0, end);end--;}
}

void HeapSort_test()//测试堆排序方法二，时间复杂度为:O(n*logn)
{//给定一个数组进行堆排序HPDataType arr[] = { 20, 5, 17, 36, 2, 8 };int size = sizeof(arr) / sizeof(HPDataType);//堆排序HeapSort(arr, size);//打印结果cout << "堆排序后：" << endl;for (int i = 0; i < size; i++){cout << arr[i] << " ";}cout << endl;
}

int main()
{HeapSort_test();return 0;
}

（3）堆排序的时间复杂度

堆排序的时间复杂度：需要循环的地方在于交换和向上或者向下调整：

交换的时间复杂度为T(n) = n，O(n)；

由建堆时的时间复杂度可得，交换后的向下调整的时间复杂度与向上调整的复杂度一样，为：T(n) = n*log n，O(n*log n)。

所以堆排序的时间复杂度为：T(n) = n + n*log n ， O(n + n*log n) = O(n*log n)。（省略低阶）

（4）总结

由上两步可知，当使用最优的向下排序建堆时，堆排序的总的时间复杂度为：T(n) = n + n*log n ， O(n + n*log n) = O(n*log n)。

而冒泡排序的时间复杂度为O（n^2）。若需要在庞大的计算中如循环100w次，冒泡排序的时间复杂度就是100w * 100w，而堆排序只需100w * 20，堆排序的排序效率更优。

2、top-k问题

（1）解决思路

用集合的前k个数据进行建堆，例如建小根堆，则用n-k个数据与堆顶数据进行比较，若比堆顶数据大，则进行交换，开始向下调整，当n个数据遍历完成后，小堆中的数据就是最大的前k个数据

时间复杂度为：O( k + (n - k) * log k ) = O(n)，空间复杂度为O(k)。

（2）实现过程

第一步，操作文件模拟数据。

第二步，创建k个大小的数组（用户输入，动态开辟），打开文件（关闭文件的操作也要一起写了），读取文件的前k个数据，向下调整法建堆，再循环读取文件中剩下的 n-k 个元素，与堆顶元素进行比较，满足条件就进行交换，然后再向下调整。

（3）代码实现

void HeapTop_k_test()//topk的实现
{int k = 0;cout << "请输入k：" << endl;cin >> k;HPDataType* arr = nullptr;//创建数组HPDataType* new_arr = (HPDataType*)malloc(sizeof(HPDataType) * k);if (new_arr == nullptr){perror("malloc fail！");exit(1);}arr = new_arr;FILE* pfile = fopen("data.txt", "r");//打开文件if (pfile == nullptr){perror("fopen fail！");exit(2);}for (int i = 0; i < k; i++)//读取文件的前k个数据到数组中{fscanf(pfile, "%d", &arr[i]);}for (int i = (k - 2) / 2; i >= 0; i--)//把数组中的数据进行小堆排序{//HPAdjustDowm_S(arr, i, k);//获得前k个最大数，排小堆，因为堆排序中建小堆是降序，前面的数据大HPAdjustDowm_B(arr, i, k);//获得前k个最小数，排大堆，因为堆排序中建大堆是升序，前面的数据小}int exchange = 0;while (fscanf(pfile, "%d", &exchange) != EOF)//读取文件中剩下的n-k个数据，直到文件末尾，将读取来的数据与堆中的头元素进行比较，满足条件则进行交换，然后进行排序{/*if (exchange > arr[0]){arr[0] = exchange;HPAdjustDowm_S(arr, 0, k);}*/if (exchange < arr[0]){arr[0] = exchange;HPAdjustDowm_B(arr, 0, k);}}for (int i = 0; i < k; i++){cout << arr[i] << " ";}cout << endl;fclose(pfile);free(arr);arr = nullptr;
}int main()
{HeapTop_k_test();return 0;
}

注意：

获取前 k 个最大的元素，则建小堆。

获取前 k 个最小的元素，则建大堆。

四、链式结构二叉树的实现

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

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

（一）前中后序遍历

1、遍历规则

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

① 前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前，访问顺序为：根结点、左子树、右子树。

② 中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右子树之中（间）

访问顺序为：左子树、根结点、右子树。

③ 后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右子树之后

访问顺序为：左子树、右子树、根结点。

2、代码实现

//(一)先序遍历
void PreOrder(BTNode* root)
{if (root == nullptr)return;cout << root->data << " ";PreOrder(root->left);PreOrder(root->right);
}
//(二)中序遍历
void InOrder(BTNode* root)
{if (root == nullptr)return;InOrder(root->left);cout << root->data << " ";InOrder(root->right);
}
//(三)后序遍历
void PostOrder(BTNode* root)
{  if (root == nullptr)return;PostOrder(root->left);PostOrder(root->right);cout << root->data << " ";
}

递归图解如下：

（二）节点个数以及高度等代码实现

//(一)二叉树结点个数
int BinaryTreeSize(BTNode* root);//(二)二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);//(三)二叉树第k层结点个数
//左子树第k层节点个数 + 右子树第k层节点个数   
int BinaryTreeLevelKSize(BTNode* root, int k);//(四)二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);//(五)二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);//(六)二叉树销毁
void BinaryTreeDestory(BTNode*& root);

//(一)二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == nullptr)return 0;return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//(二)二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == nullptr)return 0; if (root->left == nullptr && root->right == nullptr)return 1;return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
//(三)二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == nullptr)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
//(四)二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == nullptr)return 0;int Left_depth = BinaryTreeDepth(root->left);int Right_depth = BinaryTreeDepth(root->right);return Left_depth > Right_depth ? Left_depth + 1: Right_depth + 1;
}
//(五)二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == nullptr)return 0;if (root->data == x)return root;BTNode* left_root = BinaryTreeFind(root->left, x);if (left_root)return left_root;BTNode* right_root = BinaryTreeFind(root->right, x);if (right_root)return right_root;return nullptr;
}
//(六)二叉树销毁(后序遍历)
void BinaryTreeDestory(BTNode*& root)
{if (root == nullptr)return;BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);root = nullptr;
}

（三）层序遍历

需要借助队列结构进行遍历

Queue.h

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<iostream>
#include<stdbool.h>
using namespace std;//typedef int QDataType;
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;struct Queue
{QueueNode* phead;QueueNode* ptail;int size;//储存队列的有效数据
};//一、初始化队列,判断是否为空,取有效元素个数,销毁队列
//（一）初始化队列
void QueueInit(Queue& q);
//（二）判断是否为空
bool QueueEmpty(Queue& q);
//（三）取有效元素个数
int QueueSize(Queue q);
//（四）销毁队列
void QueueDestroy(Queue& q);//二、队尾入数据，队头出数据
//（一）队尾入数据
void QueuePush(Queue& q, QDataType num);
//（二）队头出数据
void QueuePop(Queue& q);//三、取队头、队尾数据
//（一）取队头数据
QDataType QueueGetHead(Queue& q);
//（二）取队尾数据
QDataType QueueGetTail(Queue& q);

Queue.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"//一、初始化队列,判断是否为空,取有效元素个数,销毁队列
//（一）初始化队列
void QueueInit(Queue& q)
{q.phead = q.ptail = nullptr;q.size = 0;
}
//（二）判断是否为空
bool QueueEmpty(Queue& q)
{return q.phead == nullptr && q.ptail == nullptr;
}
//（三）取有效元素个数
int QueueSize(Queue q)
{return q.size;
}
//（四）销毁队列
void QueueDestroy(Queue& q)
{//assert(!QueueEmpty(q));QueueNode* pcur = q.phead;while (pcur){QueueNode* next_node = pcur->next;free(pcur);pcur = next_node;}q.phead = q.ptail = nullptr;q.size = 0;
}//二、队尾入数据，队头出数据
//（一）队尾入数据
void QueuePush(Queue& q, QDataType num)
{//创建队列节点QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));if (new_node == nullptr){perror("QueuePush malloc fail!");exit(1);}new_node->data = num;new_node->next = nullptr;//插入队尾，尾插有两种情况：头节点为空与不为空if (q.phead == nullptr && q.ptail == nullptr)q.phead = q.ptail = new_node;else{q.ptail->next = new_node;q.ptail = new_node;}q.size++;
}
//（二）队头出数据
void QueuePop(Queue& q)
{assert(!QueueEmpty(q));//需要考虑队列中只有一个节点的情况和多个节点的情况if (q.phead == q.ptail){free(q.phead);q.phead = q.ptail = nullptr;}else{QueueNode* next_node = q.phead->next;free(q.phead);q.phead = next_node;}q.size--;
}//三、取队头、队尾数据
//（一）取队头数据
QDataType QueueGetHead(Queue& q)
{assert(!QueueEmpty(q));return q.phead->data;
}
//（二）取队尾数据
QDataType QueueGetTail(Queue& q)
{assert(!QueueEmpty(q));return q.ptail->data;
}

Tree.h

//借助数据结构-队列
void LevelOrder(BTNode* root);//五、判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root); 
//如果是完全二叉树，跳出一个循环之后队列中剩下的全是nullptr节点
//如果不是完全二叉树，跳出一个循环之后队列中还有非空节点

Tree.cpp

//借助数据结构-队列
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);//创建并初始化一个队列QueuePush(q, root);//把头结点插入到队列中while (!QueueEmpty(q))//当队列不为空时，把根节点打印并出队列，然后往队列里面插入根节点的左右子树，再判断空{BTNode* top = QueueGetHead(q);cout << top->data << " ";QueuePop(q);//把根节点打印并出队列if (top->left)//注意！需要判断二叉树的节点是否为空才进行插入QueuePush(q, top->left);if (top->right)QueuePush(q, top->right);//往队列里面插入根节点的左右子树}cout << endl;QueueDestroy(q);
}//这样就能保证每一行都进行遍历//五、判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);//创建并初始化一个队列QueuePush(q, root);//把头结点插入到队列中while (!QueueEmpty(q))//这个循环是层序遍历所有的节点放入队列中{BTNode* top = QueueGetHead(q);QueuePop(q);if (top == nullptr)break;QueuePush(q, top->left);QueuePush(q, top->right);//往队列里面插入根节点的左右子树}//队列不一定为空while (!QueueEmpty(q))//这个循环检测队列中剩下的元素是不是纯nullptr，若是则为完全二叉树，反之则不是{BTNode* top = QueueGetHead(q);QueuePop(q);if (top != nullptr)return false;}return true;QueueDestroy(q);
}

（四）代码总汇

Queue.h

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<iostream>
#include<stdbool.h>
using namespace std;//typedef int QDataType;
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;struct Queue
{QueueNode* phead;QueueNode* ptail;int size;//储存队列的有效数据
};//一、初始化队列,判断是否为空,取有效元素个数,销毁队列
//（一）初始化队列
void QueueInit(Queue& q);
//（二）判断是否为空
bool QueueEmpty(Queue& q);
//（三）取有效元素个数
int QueueSize(Queue q);
//（四）销毁队列
void QueueDestroy(Queue& q);//二、队尾入数据，队头出数据
//（一）队尾入数据
void QueuePush(Queue& q, QDataType num);
//（二）队头出数据
void QueuePop(Queue& q);//三、取队头、队尾数据
//（一）取队头数据
QDataType QueueGetHead(Queue& q);
//（二）取队尾数据
QDataType QueueGetTail(Queue& q);

Queue.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"//一、初始化队列,判断是否为空,取有效元素个数,销毁队列
//（一）初始化队列
void QueueInit(Queue& q)
{q.phead = q.ptail = nullptr;q.size = 0;
}
//（二）判断是否为空
bool QueueEmpty(Queue& q)
{return q.phead == nullptr && q.ptail == nullptr;
}
//（三）取有效元素个数
int QueueSize(Queue q)
{return q.size;
}
//（四）销毁队列
void QueueDestroy(Queue& q)
{//assert(!QueueEmpty(q));QueueNode* pcur = q.phead;while (pcur){QueueNode* next_node = pcur->next;free(pcur);pcur = next_node;}q.phead = q.ptail = nullptr;q.size = 0;
}//二、队尾入数据，队头出数据
//（一）队尾入数据
void QueuePush(Queue& q, QDataType num)
{//创建队列节点QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));if (new_node == nullptr){perror("QueuePush malloc fail!");exit(1);}new_node->data = num;new_node->next = nullptr;//插入队尾，尾插有两种情况：头节点为空与不为空if (q.phead == nullptr && q.ptail == nullptr)q.phead = q.ptail = new_node;else{q.ptail->next = new_node;q.ptail = new_node;}q.size++;
}
//（二）队头出数据
void QueuePop(Queue& q)
{assert(!QueueEmpty(q));//需要考虑队列中只有一个节点的情况和多个节点的情况if (q.phead == q.ptail){free(q.phead);q.phead = q.ptail = nullptr;}else{QueueNode* next_node = q.phead->next;free(q.phead);q.phead = next_node;}q.size--;
}//三、取队头、队尾数据
//（一）取队头数据
QDataType QueueGetHead(Queue& q)
{assert(!QueueEmpty(q));return q.phead->data;
}
//（二）取队尾数据
QDataType QueueGetTail(Queue& q)
{assert(!QueueEmpty(q));return q.ptail->data;
}

Tree.h

#pragma once
#include<stdlib.h>
#include<iostream>
#include<assert.h>
#include<stdbool.h>
#include<time.h>
using std::cout;
using std::cin;
using std::endl;
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//一、节点的创建、初始化
BTNode* Buy_Node(BTDataType num);//二、遍历
//(一)先序遍历
void PreOrder(BTNode* root);
//(二)中序遍历
void InOrder(BTNode* root);
//(三)后序遍历
void PostOrder(BTNode* root);//三、各种功能的实现
//(一)二叉树结点个数
int BinaryTreeSize(BTNode* root);//(二)二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);//(三)二叉树第k层结点个数
//左子树第k层节点个数 + 右子树第k层节点个数   
int BinaryTreeLevelKSize(BTNode* root, int k);//(四)二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);//(五)二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);//(六)二叉树销毁
void BinaryTreeDestory(BTNode*& root);//四、层序遍历
//借助数据结构-队列
void LevelOrder(BTNode* root);//五、判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root); 
//如果是完全二叉树，跳出一个循环之后队列中剩下的全是nullptr节点
//如果不是完全二叉树，跳出一个循环之后队列中还有非空节点

Tree.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
#include"Queue.h"//一、节点的创建、初始化
BTNode* Buy_Node(BTDataType num)
{BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));if (new_node == nullptr){perror("Buy_Node malloc fail!");exit(1);}new_node->data = num;new_node->left = new_node->right = nullptr;return new_node;
}//二、遍历
//(一)先序遍历
void PreOrder(BTNode* root)
{if (root == nullptr)return;cout << root->data << " ";PreOrder(root->left);PreOrder(root->right);
}
//(二)中序遍历
void InOrder(BTNode* root)
{if (root == nullptr)return;InOrder(root->left);cout << root->data << " ";InOrder(root->right);
}
//(三)后序遍历
void PostOrder(BTNode* root)
{  if (root == nullptr)return;PostOrder(root->left);PostOrder(root->right);cout << root->data << " ";
} //三、各种功能的实现
//(一)二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == nullptr)return 0;return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//(二)二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == nullptr)return 0; if (root->left == nullptr && root->right == nullptr)return 1;return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
//(三)二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == nullptr)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
//(四)二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == nullptr)return 0;int Left_depth = BinaryTreeDepth(root->left);int Right_depth = BinaryTreeDepth(root->right);return Left_depth > Right_depth ? Left_depth + 1: Right_depth + 1;
}
//(五)二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == nullptr)return 0;if (root->data == x)return root;BTNode* left_root = BinaryTreeFind(root->left, x);if (left_root)return left_root;BTNode* right_root = BinaryTreeFind(root->right, x);if (right_root)return right_root;return nullptr;
}
//(六)二叉树销毁(后序遍历)
void BinaryTreeDestory(BTNode*& root)
{if (root == nullptr)return;BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);root = nullptr;
}//四、层序遍历
//借助数据结构-队列
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);//创建并初始化一个队列QueuePush(q, root);//把头结点插入到队列中while (!QueueEmpty(q))//当队列不为空时，把根节点打印并出队列，然后往队列里面插入根节点的左右子树，再判断空{BTNode* top = QueueGetHead(q);cout << top->data << " ";QueuePop(q);//把根节点打印并出队列if (top->left)//注意！需要判断二叉树的节点是否为空才进行插入QueuePush(q, top->left);if (top->right)QueuePush(q, top->right);//往队列里面插入根节点的左右子树}cout << endl;QueueDestroy(q);
}//这样就能保证每一行都进行遍历//五、判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);//创建并初始化一个队列QueuePush(q, root);//把头结点插入到队列中while (!QueueEmpty(q))//这个循环是层序遍历所有的节点放入队列中{BTNode* top = QueueGetHead(q);QueuePop(q);if (top == nullptr)break;QueuePush(q, top->left);QueuePush(q, top->right);//往队列里面插入根节点的左右子树}//队列不一定为空while (!QueueEmpty(q))//这个循环检测队列中剩下的元素是不是纯nullptr，若是则为完全二叉树，反之则不是{BTNode* top = QueueGetHead(q);QueuePop(q);if (top != nullptr)return false;}return true;QueueDestroy(q);
}

TreeTest.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"void test()
{BTNode* Node1 = Buy_Node(1);BTNode* Node2 = Buy_Node(2);BTNode* Node3 = Buy_Node(3);BTNode* Node4 = Buy_Node(4);BTNode* Node5 = Buy_Node(5);Node1->left = Node2;Node1->right = Node3;Node2->left = Node4;Node2->right = Node5;cout << "size:" << BinaryTreeSize(Node1) << endl;cout << "Leaf_size:" << BinaryTreeLeafSize(Node1) << endl;cout << "k_Leaf_size:" << BinaryTreeLevelKSize(Node1, 3) << endl;cout << "depth:" << BinaryTreeDepth(Node1) << endl;BTNode* re =  BinaryTreeFind(Node1, 5);printf("%s\n", re == nullptr ? "没找到" : "找到了");//LevelOrder(Node1);if (BinaryTreeComplete(Node1))cout << "完全二叉树" << endl;elsecout << "非完全二叉树" << endl;BinaryTreeDestory(Node1);
}int main()
{test();return 0;
}

五、二叉树算法题

（一）单值二叉树

题目链接：https://leetcode.cn/problems/univalued-binary-tree/description/

解题思路：

使用递归，递归过程：若左孩子节点不为空，则与父节点进行比较；若右孩子节点不为空，则与父节点进行比较；

递归：先写最终要执行的语句，然后写下一次递归要做的事情，最后 return 有接近终止条件的参数的函数。

答案代码：

typedef struct TreeNode TreeNode;
bool isUnivalTree(struct TreeNode* root) {if(root == NULL)return true;if(root->left && root->left->val != root->val)return false;if(root->right && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

（二）相同的树

题目链接：https://leetcode.cn/problems/same-tree/description/

解题思路：

同步递归遍历两颗树，可以保证结构是相同的。

递归终止条件：两棵树都为空是相同的，一个为空则是不相同，都不为空且值不相同则为不相同。

先比较根节点的值，然后递归遍历左且右节点。

答案代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//终止情况//一、都为空if(p == NULL && q == NULL)return true; //二、其中一个为空if(p == NULL || q == NULL)return false;//三、都不为空if(p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

（三）对称二叉树

题目链接：https://leetcode.cn/problems/symmetric-tree/description/

解题思路：与相同的树类似，只是需要对比的左右子树不同。

答案代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//终止情况//一、都为空if(p == NULL && q == NULL)return true; //二、其中一个为空if(p == NULL || q == NULL)return false;//三、都不为空if(p->val != q->val)return false;return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
}bool isSymmetric(struct TreeNode* root) {return isSameTree(root->left, root->right);
}

（四）另一棵子树

题目链接：https://leetcode.cn/problems/subtree-of-another-tree/description/

解题思路：在递归二叉树的过程中加入对子树的相同检查。

答案代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//终止情况//一、都为空if(p == NULL && q == NULL)  return true; //二、其中一个为空if(p == NULL || q == NULL)return false;//三、都不为空if(p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {if(root == NULL)return false; if(isSameTree(root, subRoot))return true;return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

（五）二叉树遍历

1、前序遍历

题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

解题思路：

第一步：先求出二叉树结点个数。二叉树结点个数 = 根节点个数+左子树节点数+右子树节点数。

第二步：动态申请数组

第三步：前序遍历

答案代码：

typedef struct TreeNode TreeNode;int TreeNode_size(TreeNode* root)
{if(root == NULL)return 0;return 1 + TreeNode_size(root->left) + TreeNode_size(root->right);
}void _preorderTraversal(struct TreeNode* root, int* return_arr, int* i)
{if(root == NULL)return ;return_arr[(*i)++] = root->val;_preorderTraversal(root->left, return_arr, i);_preorderTraversal(root->right, return_arr, i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {//第一步：计算节点个数为动态申请数组的元素个数*returnSize = TreeNode_size(root);//第二步：申请数组大小int* return_arr = (int*)malloc(sizeof(int)*(*returnSize));//第三步：前序遍历数组后，把节点的val值输入到数组中int i = 0;_preorderTraversal(root, return_arr, &i);return return_arr;
}

2、中序遍历

题目链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

解题思路：与前序遍历类似，只是输入值到数组时的顺序不同。

答案代码：

typedef struct TreeNode TreeNode;int TreeNode_size(TreeNode* root)
{if(root == NULL)return 0;return 1 + TreeNode_size(root->left) + TreeNode_size(root->right);
}void _inorderTraversal(struct TreeNode* root, int* return_arr, int* i)
{if(root == NULL)return ;_inorderTraversal(root->left, return_arr, i);return_arr[(*i)++] = root->val;_inorderTraversal(root->right, return_arr, i);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {//第一步：计算节点个数为动态申请数组的元素个数*returnSize = TreeNode_size(root);//第二步：申请数组大小int* return_arr = (int*)malloc(sizeof(int)*(*returnSize));//第三步：前序遍历数组后，把节点的val值输入到数组中int i = 0;_inorderTraversal(root, return_arr, &i);return return_arr;
}

3、后续遍历

题目链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

解题思路：与前序遍历类似，只是输入值到数组时的顺序不同。

答案代码：

typedef struct TreeNode TreeNode;int TreeNode_size(TreeNode* root)
{if(root == NULL)return 0;return 1 + TreeNode_size(root->left) + TreeNode_size(root->right);
}void _postorderTraversal(struct TreeNode* root, int* return_arr, int* i)
{if(root == NULL)return ;_postorderTraversal(root->left, return_arr, i);_postorderTraversal(root->right, return_arr, i);return_arr[(*i)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {//第一步：计算节点个数为动态申请数组的元素个数*returnSize = TreeNode_size(root);//第二步：申请数组大小int* return_arr = (int*)malloc(sizeof(int)*(*returnSize));//第三步：前序遍历数组后，把节点的val值输入到数组中int i = 0;_postorderTraversal(root, return_arr, &i);return return_arr;
}

（六）二叉树的构建及遍历

题目链接：https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef

解题思路：

第一步：创建二叉节点；

第二步：输入字符串保存在字符数组中；

第三步：根据字符串（前序遍历）创建二叉树；

第四步：输出二叉树的中序遍历。

答案代码如下：

#include <stdio.h>
#include <stdlib.h>typedef struct binaryNodeTree
{char data;struct binaryNodeTree* left;struct binaryNodeTree* right;
} BTNode;BTNode* creatNode(char data)
{BTNode* new_bt = (BTNode*)malloc(sizeof(BTNode));new_bt->data = data;new_bt->left = new_bt->right = NULL;return new_bt;
}BTNode* creatTree(char* arr, int* pi)
{if (arr[*pi] == '#') {(*pi)++;return NULL;}BTNode* new_node = creatNode(arr[(*pi)++]);new_node->left = creatTree(arr, pi);new_node->right = creatTree(arr, pi);return new_node;
}void inOrder(BTNode* root)
{if(root == NULL)return;inOrder(root->left);printf("%c ", root->data);inOrder(root->right);    
}int main() {//读取用户输入的字符串保存在字符数组中char arr[100];scanf("%s", arr);//根据字符串（前序遍历）创建二叉树int pi = 0;BTNode* root = creatTree(arr, &pi);//printf("%s", arr);//输出二叉树的中序遍历inOrder(root);return 0;
}