🚀write in front🚀
📜所属专栏：初阶数据结构
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！
前言
在之前的二叉树的顺序结构中我们发现，该二叉树对于堆（一种完全二叉树）非常实用，但是对于非完全二叉树就会出现以下的结构，造成空间浪费：
所以这里我们还是要通过链式结构来实现二叉树。但是其实普通二叉树是没有什么意义的，增删查改没有多大的意义。真正有意义的是搜索二叉树：
搜索二叉树的特点是左子树比根大/小，右子树比根小/大。这里的二叉树可以用来搜索，也可以用来进行插入，删除等操作，拥有实际的意义。所以对于普通二叉树，我们不用学习他的增删查改，只用学习他的遍历等操作，并且复习一下递归的相关知识。
一.二叉树的理解：
我们先回顾一下回顾下二叉树的概念，二叉树是：
- 空树
- 非空：根节点，根节点的左子树、根节点的右子树组成的。
对于一颗二叉树，我们看到它就要把他分为：根，左子树，右子树。对于左子树，在把他分为：根，左子树，右子树。对于右子树，在把他分为：根，左子树，右子树……以此类推直到左右子树都为空才停止。
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
二.二叉树的遍历：
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的每个节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历。我们以这颗二叉树为例：
创建二叉树：
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;
}
node->left = NULL;
node->right = NULL;
node->data = x;
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);
BTNode* node7 = BuyNode(7);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node3->right = node7;
return node1;
}
1.前序遍历：
前序遍历的顺序是：根，左子树，右子树。
代码实现：
void PreOrder(BTNode* root)
{
if (root = NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
结果：
2.中序遍历：
中序遍历的顺序是：左子树，根，右子树。
代码实现：
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
结果：
3.后序遍历：
后序遍历的顺序是：左子树，右子树，根。
代码实现：
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
结果：
其实上面的三种遍历就是通过s三句代码的顺序导致结果的不同，当然他们的递归过程都能用下面这张图来代表：
4.层序遍历：
除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历
那么如何实现层序遍历呢？这里我们就要用到我们之前所学的队列了！
在这里，我们将二叉树的根先进队列，然后将其出队列，每出一次，就让其左右子结点进入队列，随后在出一个队列，将其左右子节点加入队列……这样通过队列的push和pop就能实现层序遍历
我们首先将队列的代码导入即可，就可以创建队列了：
代码实现：
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);
}
注意：
这里我们放入队列的不是要打印的数据，而是树结点的指针，为什么呢？如果我们存入的是要打印的数据（整形数据），那么我们无法找到他们的子节点!所以我们每次pop出一个指针，然后push这个指针（结点）的子节点即可。图解如下：
三.判断二叉树是否为完全二叉树：
我们先来看看这张图：
我们会发现，通过层序遍历的方法，满二叉树在层序遍历时的非空结点一定是连续的，空结点也是连续的，所以我们只要在层序遍历的基础上把空结点存入，然后判断空结点是否连续即可。
代码实现：
// 判断二叉树是否是完全二叉树
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;
}
}
四.二叉树结点数量：
如果我们要计算结点的数量，通过上面所学的遍历的方式当然可以计算出结点数量。
这就是遍历的方法，但是事实上我们用分治的方法更多一些：
分治和遍历的区别：
拿学校人口统计作为例子，遍历法与分治法的区别如下：
遍历法，做法如下：
校长自己一个人带着一个本子，跑遍全校查人数
分治法，做法如下：
校长想知道人数，就找来院长统计每个院的人数相加，院长找来系主任统计每个系的人数相加……这样校长就不用亲自动手了。其实递归就是把任务交给打工人（呜呜）。
那么我们如何实现分治法呢？
总体思路就是 返回：左子树数量+右子树数量+1
代码实现：
int TreeSize(BTNode* root)
{
return root == NULL ? 0 :
TreeSize(root->left)
+ TreeSize(root->right) + 1;
}
五.二叉树的高度（深度）：
在这里要求二叉树的高度，我们也是用分治的思想：
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层节点个数
现在我们把他分为子问题：
当前树的第k层个数=左子树的第k-1层个数+右子树的第k-1层个数
代码如下：
int TreeKLevel(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
int leftklevel = TreeKLevel(root->left, k - 1);
int rightklevel = TreeKLevel(root->right, k - 1);
return leftklevel + rightklevel;
}
总结
更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
专栏订阅：
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！文章来源：https://www.toymoban.com/news/detail-435174.html
文章来源地址https://www.toymoban.com/news/detail-435174.html
到了这里，关于【数据结构】二叉树链式结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
