片头
嗨！小伙伴们，大家好，今天我们来学习二叉树这种数据结构，学习二叉树之前，我们先了解一下树的概念做个铺垫，Ready Go ! ! !
一、树
1. 树概念及结构
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树，一颗根朝上，叶朝下的树。
观察上图，我们可以发现：
①有一个特殊的结点，称为根节点，根节点没有前驱结点
②除根节点外，其余结点被分成M（M>0）个互不相交的集合T1、T2、.......、Tm,其中每一个集合Ti （1<=i<=m）又是一颗结构与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继（BEFJ为一颗子树，CGKL为一颗子树，DHIM为一颗子树）
③因此，树是递归定义的。
这里有一个注意点：在树形结构中，子树之间不能有交集，否则就不是树形结构
1.2 树的相关概念
（1）节点的度：一个节点含有的子树的个数称为该节点的度。例如A节点的度为6。
（2）叶节点或终端节点：度为0的节点。例如：B、C、H、I、P...等节点为叶节点（没有孩子的节点）
（3）分支节点或非终端节点：度不为0的节点。例如：D、E、F、G...等节点为分支节点
（4）双亲节点或父节点：如果一个节点含有子节点，则该节点称为其子节点的父节点。例如：A是B的父节点。
（5）孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。例如：B是A的子节点。
（6）兄弟节点：具有相同父节点的节点互为兄弟节点。例如：B和C是兄弟节点。
（7）树的度：一个树中最大的节点的度就是树的度。例如：A的度为6，它的度最大，则树的度为6。
（8）节点的层次：从根开始定义，根为第1层，根的子节点为第2层，以此类推。
（9）树的高度或深度：树中节点的最大层次。如上图：树的高度为4。
（10）堂兄弟节点：父节点在同一层的节点互为堂兄弟节点。如上图：H和K互为堂兄弟节点。
（11）节点的祖先：从根到该节点所经分支上的所有节点。例如：A是所有节点的祖先。
（12）子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：A是所有节点的祖先。
（13）森林：由m（m>0）棵互不相交的树的集合称为森林。
二、二叉树
2.1 二叉树的概念
一颗二叉树是结点的一个有限集合，该集合:
1. 或者为空
2. 由一个根节点加上两棵分别称为左子树和右子树的二叉树组成
从上图中可以看出：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成：
2.2 现实中的二叉树
2.3 特殊二叉树
1. 满二叉树：一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。换句话说，如果一个二叉树的层数为K，且节点总数是 ,则它就是满二叉树。（简便记忆：每层结点都是满的二叉树）
2.完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引申出来的。对于深度为K，有n个节点的二叉树，当且仅当其每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树。要注意的是：满二叉树是一种特殊的完全二叉树。（简便记忆：前n-1层都是满的，最后一层可以不满，但是一定是连续的）
满二叉树【补充】：满二叉树每一层都是满的；完全二叉树最后一层可以不满，但是从左到右必须是连续的
2.4 二叉树的性质
（1）若定义根节点的层数为1，则一棵非空二叉树的第i层上最多有个结点。
（2）若定义根节点的层数为1，则深度为h的二叉树的最大结点数是。
（3）若定义根节点的层数为1，则具有n个结点的满二叉树的高度， （ps:
是log以2为底， n+1为对数）
（4）对任何一棵二叉树，如果度为0，其叶节点个数为,度为2的分支节点个数为
, 则有
（5）对于具有n个节点的完全二叉树，如果按照从上到下，从左到右的数组顺序对所有节点从0开始编号，则对于序号为i的节点：
- 若 i > 0,其父节点序号为
；i = 0, i 为根节点编号，无父节点
- 若 2i + 1 < n, 左孩子序号：
, 若 2i + 1 >= n ，无左孩子
- 若 2i + 2 < n, 右孩子序号：
, 若 2i + 2 >= n ，无右孩子
2.5 二叉树的存储结构
二叉树一般可以使用2种结构存储，一种是顺序结构，另一种是链式结构。
（1） 顺序存储
顺序结构存储就是使用数组来存储数据，一般使用数组只适合表示完全二叉树，因为非完全二叉树不连续，会造成空间的浪费。
在前面的数据结构之堆中我们提到过，堆也是一种完全二叉树，而平时生活中也只有堆会用数组存储，存储顺序对应二叉树的性质五
二叉树的顺序存储在物理上是一个数组，而在逻辑结构上是一棵二叉树。
（2）链式存储
用链表来表示一棵二叉树，即用链来指示节点之间的逻辑关系。
一般情况下，链表中每个节点由3个域组成：数据域和左右指针域，左右指针分别指向左孩子和右孩子所在的节点地址。链式结构存储又分为二叉链和三叉链，当前我们主要使用二叉链。后面学的内容才会涉及到三叉链。
代码如下：
typedef int BTDataType;
//二叉链
typedef struct BinaryTreeNode
{
BTDataType data;//节点的数据域
struct BinaryTreeNode* left;//指向左孩子
struct BinaryTreeNode* right;//指向右孩子
}BTNode三、二叉树的相关操作
在学习二叉树的基本操作前，需要先创建一棵二叉树，然后才能学习相关的基本操作。由于现在大家对二叉树结构还不够深入，为了降低学习成本，我们来手撕一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树的真正的创建方式。
3.1 创建一棵二叉树
要创建二叉树，我们要先写一个创建二叉树新结点的函数
//创建一个新结点
BTNode* BuyBTNode(BTDataType x) {
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));//创建一个新结点
if (newNode == NULL)//内存空间不足，创建失败
{
perror("malloc fail!\n");
exit(1);
}
newNode->data = x;//将x赋值给新结点的数据域
newNode->left = NULL;//假设新结点的左孩子指向NULL
newNode->right = NULL;//假设新结点的右孩子指向NULL
return newNode;//将新结点返回
}然后我们用代码实现下图的二叉树
//手搓一棵树
BTNode* CreateTree() {
BTNode* n1 = BuyBTNode(1);//创建一个新结点n1
BTNode* n2 = BuyBTNode(2);//创建一个新结点n2
BTNode* n3 = BuyBTNode(3);//创建一个新结点n3
BTNode* n4 = BuyBTNode(4);//创建一个新结点n4
BTNode* n5 = BuyBTNode(5);//创建一个新结点n5
BTNode* n6 = BuyBTNode(6);//创建一个新结点n6
n1->left = n2;//n1的左孩子是n2
n1->right = n4;//n1的右孩子是n4
n2->left = n3;//n2的左孩子是n3
n4->left = n5;//n4的左孩子是n5
n4->right = n6;//n4的右孩子是n6
return n1;//将n1结点返回
}3.2 二叉树的遍历
二叉树的遍历即按照一定的顺序依次对二叉树中的节点进行相关操作，且每个节点只操作一次
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
1. 前序遍历/先序遍历：访问根节点的操作发生在遍历其左右子树之前。
2. 中序遍历：访问根节点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历：访问根节点的操作发生在遍历其左右子树之后。
由于被访问的节点必是某子树的根，所以N(Node)、L(Left subtree) 和 R(Right subtree) 可解释为根，根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
//二叉树的前序遍历
void PreOrder(BTNode* root);
//二叉树的中序遍历
void InOrder(BTNode* root);
//二叉树的后序遍历
void PostOrder(BTNode* root);（1）前序遍历/先序遍历
先访问根节点，再依次访问左子树和右子树，即为前序遍历。
前序遍历的代码如下：
//前序遍历
void PreOrder(BTNode* root) {
if (root == NULL) {
printf("N ");//遇到空结点打印NULL
return;
}
printf("%d ", root->data);//数据域
PreOrder(root->left);//左孩子
PreOrder(root->right);//右孩子
}我们测试一下代码：
（2）中序遍历
先访问左子树，再访问根节点，最后访问右子树，即为中序遍历
中序遍历的代码如下：
//中序遍历
void InOrder(BTNode* root) {
if (root == NULL) {
printf("N ");//遇到空节点就打印NULL
return;
}
InOrder(root->left);//左孩子
printf("%d ", root->data);//数据域
InOrder(root->right);//右孩子
}我们可以发现，中序遍历和前序遍历只是将代码交换一下即可，后面的后序遍历也是一样。
我们测试一下代码：
（3）后序遍历
先访问左子树和右子树，最后再访问根节点，即为后序遍历
后序遍历的代码如下：
//后序遍历
void PostOrder(BTNode* root) {
if (root == NULL) {
printf("N ");//遇到空节点就打印NULL
return;
}
PostOrder(root->left);//左孩子
PostOrder(root->right);//右孩子
printf("%d ", root->data);//数据域
}我们测试一下代码：
（4）层序遍历
从上到下，从左到右逐层访问树的节点的过程就是层序遍历。
与前中后序不同的是，层序遍历不使用递归，而是使用队列来实现。
队列中不是直接存放节点的值，而是存放节点的地址。
其核心思路是：上一层的节点出队列时带入下一层的节点入队列
在写层序遍历的时候，我们把之前的队列搬过来即可
层序遍历的代码如下：
// 层序遍历1
void BinaryTreeLevelOrder(BTNode* root) {
//创建队列
Queue que;
//初始化队列
QueueInit(&que);
//如果根节点非空，那么将根节点放入队列中
if (root != NULL) {
QueuePush(&que, root);
}
while (!QueueEmpty(&que)) {
//获取队头元素
BTNode* front = QueueTop(&que);
//打印结点的值
printf("%d ", front->data);
//删除队头元素
QueuePop(&que);
//如果该结点的左孩子存在，那么将左孩子放入队列中
if (front->left) {
QueuePush(&que, front->left);
}
//如果结点的右孩子存在，那么将右孩子放入队列中
if (front->right) {
QueuePush(&que, front->right);
}
}
//销毁队列
QueueDestroy(&que);
}我们测试一下代码：
如果我们想要和前序 、中序、后序遍历一样，遇到空节点就打印“N”，该怎么做呢？
很简单，当前结点不为空时，不管它的左孩子和右孩子为空与否，都要进入队列~
代码如下：
// 层序遍历2
void BinaryTreeLevelOrder1(BTNode* root) {
//创建队列
Queue que;
//初始化队列
QueueInit(&que);
//如果根节点非空，那么将根节点放入队列中
if (root != NULL)
QueuePush(&que, root);
while (!QueueEmpty(&que)) {
//获取队头元素
BTNode* front = QueueTop(&que);
//删除队头元素
QueuePop(&que);
if (front != NULL) {
printf("%d ", front->data);
//带入下一层（不管左右孩子是否存在，都要带入下一层）
QueuePush(&que, front->left);
QueuePush(&que, front->right);
}
else
{
//如果是空，那么就没有下一层了
printf("N ");
}
}
//销毁队列
QueueDestroy(&que);
}我们来测试一下代码：
3.3 二叉树的其他操作
(1)求二叉树的结点个数
哈哈哈，看到这里，有的小伙伴们可能会说：太简单了，二叉树的结点个数不就是等于左子树结点的个数 + 右子树结点的个数嘛？ 最后将结果返回就行了，真的是这样吗？我们实践一下：
错误代码如下：
//这种写法是错误的
//求二叉树的结点个数
int TreeSize(BTNode* root) {
static int size = 0;//定义静态变量size
if (root == NULL) //如果根节点为空，返回0
{
return 0;
}
else { //结点个数+1
size++;
}
TreeSize(root->left);//递归左子树
TreeSize(root->right);//递归右子树
return size;//返回size
}我们测试一下：
啊哦！出事了！三个代码一模一样，但是运行结果不一样！
这是因为：局部的静态变量只会被初始化一次，当调用多次的时候，static int size = 0;（这句代码只会执行一次）。局部变量是在第一次调用的时候被初始化，后面再去调用就不会再执行初始化。
那怎么改进呢？
改进方法一：将size定义为全局静态变量或者全局变量，每次使用size之前，都先将size置为0
//改进方法一：
//将size定义为全局静态变量或者全局变量
int size = 0;
//static int size = 0;
int TreeSize(BTNode* root) {
if (root == NULL)//如果根节点为空，返回0
{
return 0;
}
else {
size++; //结点个数+1
}
TreeSize(root->left);//递归左子树
TreeSize(root->right);//递归右子树
return size;//返回size
}
int main() {
//创造一棵二叉树
BTNode* root = CreateTree();
printf("二叉树的结点个数为：%d\n", TreeSize(root));
size = 0; //每次使用size之前，先将size置为0
printf("二叉树的结点个数为：%d\n", TreeSize(root));
size = 0; //每次使用size之前，先将size置为0
printf("二叉树的结点个数为：%d\n", TreeSize(root));
return 0;
}测试一下：
改进方法二：
//改进方法二：
int TreeSize(BTNode* root,int* psize) {
if (root == NULL) //如果根节点为空，返回0
{
return 0;
}
else {
(*psize)++;
}
TreeSize(root->left, psize);//递归左子树
TreeSize(root->right, psize);//递归右子树
}还有没有方法呢？肯定有，而且比前面2种都要简单，我们一起来康康~
改进方法三：我们采用分治思想。
分治，即分而治之，就是将一个复杂的问题分解成子问题，子问题再分解成更小子问题，直到最后一个子问题可以简单求解。
例如：我们要求二叉树的节点个数，我们可以将其拆分成左子树、根和右子树。
左子树的节点个数加上右子树的节点个数，再加上根，即为二叉树的节点个数。
而左子树和右子树也能以相同的方式进行拆分，这样就可以将一个大问题拆分成了许多个相同的小问题。
代码如下：
//改进方法三：分治思想
int TreeSize(BTNode* root) {
//如果根节点为空，返回0；
//如果根节点非空，返回左子树结点的个数 + 右子树结点的个数 + 根
return root == NULL ? 0 :
TreeSize(root->left) + TreeSize(root->right) + 1;
}测试一下：
（2）求二叉树的高度
取左右子树的最大值，再加上自身，就是二叉树的高度。
代码如下：
//二叉树的高度
int TreeHeight(BTNode* root) {
if (root == NULL) //如果根节点为空，返回0；
{
return 0;
}
//递归求左子树的高度
int LeftTree = TreeHeight(root->left);
//递归求右子树的高度
int RightTree = TreeHeight(root->right);
//将左子树的高度和右子树的高度进行比较，取大的那一个，再加上根节点自身，最后得出答案
return LeftTree > RightTree ? LeftTree + 1 : RightTree + 1;
}这里递归的返回值必须要记录下来，不然会重复计算
测试一下：
（3）求二叉树第k层节点个数
当前树的第k层节点的个数 = 左子树第 k-1 层节点个数 + 右子树第 k-1 层节点个数
代码如下：
//二叉树第k层结点个数
int TreeKLevel(BTNode* root, int k) {
//如果根节点为空，返回0；
if (root == NULL)
{
return 0;
}
//如果是求第1层的结点个数，返回1
if (k == 1)
{
return 1;
}
//当前树的第k层个数 = 左子树第k-1层个数 + 右子树第k-1层个数
return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}测试一下：
（4） 求二叉树叶子节点的个数
代码如下：
//求二叉树叶子结点的个数
int TreeLeafSize(BTNode* root) {
//如果根节点为空，返回0；
if (root == NULL)
{
return 0;
}
//如果整棵二叉树中只有根节点，返回1
//如果该结点的左孩子为空，右孩子也为空，返回1
if (root->left == NULL && root->right == NULL)
{
return 1;
}
//将左右子树的叶子结点加起来，将结果返回
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}测试一下：
（5）判断二叉树中是否存在值为x的节点
先访问根，根不为x则访问左子树
左子树中没找到则访问右子树，找到了则返回 true
右子树中找到了返回 true，没找到则说明树中没有值为x的节点，返回 false
代码如下：
//判断二叉树里面是否存在值为x的结点
bool TreeFind1(BTNode* root, int x) {
//如果根节点为空，返回false
if (root == NULL)
{
return false;
}
//如果根节点的数据域为x，那么返回true
if (root->data == x)
{
return true;
}
//在根节点的右子树中查找x，如果找到，返回true
// 只要在左子树中找到x，就不需要在右子树中查找了，因此用短路或来连接
//在根节点的右子树中查找x，如果找到，返回true
return TreeFind1(root->left, x)
|| TreeFind1(root->right, x);
}测试一下：
（6）在二叉树中查找值为x的节点
先访问根，根不为x则访问左子树
左子树中没找到则访问右子树，找到了则返回节点地址
右子树中找到了返回节点地址，没找到则说明树中没有值为x的节点，返回NULL
代码如下：
//查找二叉树里面存在值为x的结点
BTNode* TreeFind(BTNode* root, int x) {
//如果根节点为空，返回NULL
if (root == NULL)
{
return NULL;
}
//如果根节点的数据域为x，那么返回该节点
if (root->data == x) {
return root;
}
//在根节点的左子树中查找x，如果找到，返回该结点
BTNode* ret1 = TreeFind(root->left, x);
if (ret1) {
return ret1;
}
//在根节点的右子树中查找x，如果找到，返回该结点
BTNode* ret2 = TreeFind(root->right, x);
if (ret2) {
return ret2;
}
//在左子树和右子树中都没找到x，返回NULL
return NULL;
}（7）销毁二叉树
销毁一棵二叉树最好使用后序，先销毁左子树和右子树，最后销毁根节点
代码如下：
//销毁二叉树
void TreeDestroy(BTNode* root) {
//如果根节点为空，直接返回
if (root == NULL)
{
return;
}
TreeDestroy(root->left);//销毁左子树
TreeDestroy(root->right);//销毁右子树
free(root);//释放根节点
}测试一下：
片尾
今天我们学习了二叉树这个数据结构，重点介绍了二叉树的相关操作，希望看完这篇文章能对友友们有所帮助 ！ ！ !
求点赞收藏加关注 ！ ！ ！
谢谢大家 ！ ！ ！
