不要有太大压力李
生活不是选择而是热爱李
- ⭐前言⭐
- 0️⃣手搓一个二叉树
- 1️⃣二叉树的遍历
- 1. 深度优先遍历
- ① 前序遍历
- ② 中序遍历
- ③ 后序遍历
- 2. 广度优先遍历
- 层序遍历
- 层序遍历代码
- 2️⃣求二叉树的节点个数
- 方法1
- 缺陷:
- 方法2
- 3️⃣求叶子节点数量
- 4️⃣求第k层节点的个数
- 5️⃣查找某个节点
- 6️⃣求二叉树的深度
- 7️⃣二叉树的销毁
- 8️⃣判断是否为完全二叉树
- ⭐写在最后⭐
我们已经学习了二叉树的顺序结构 —>完全二叉树 、 堆
但那是特殊的二叉树,对于普通的二叉树,不适合利用顺序结构来存储
因为可能存在很多的空间浪费,如:
数组中很多空间是没有存放数据的!
//手搓一个二叉树
BTNode* CreateBinaryTree()
{
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;
//没赋值的 一定都是NULL
return node1;
}
int main()
{
BTNode* root = CreateBinaryTree();
return 0;
}
得到这样一个二叉树:
首先我们要知道两个名词:深度优先遍历和广度优先遍历
- 深度优先遍历
深度优先遍历:DFS
沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当沿着某个节点已经到达最深(已经到空),然后就回去遍历该节点的另一条边。
如图就是一种深度优先遍历
深度优先遍历又分为先序遍历,后序遍历,中序遍历
区别就是访问根节点的先后
- 广度优先遍历:
1. 深度优先遍历 ① 前序遍历广度优先遍历 BFS(Breadth-First-Search),也就是宽度优先,BFS是从根节点开始,沿着树的某一层遍历树的节点,优先横向遍历。
前序遍历的顺序就是 访问根节点的操作发生在遍历其左右子树之前
如图:
代码:
注:我们用 # 表示空,前序结果应该是 1 2 3 # # # 4 5 # # 6 # #
// 二叉树的前序遍历
void PreOrder_Traversal(BTNode* root)
{
//如果节点为空树
if (root == NULL)
{
printf("# ");
return;
}
//先访问 根节点数据 -->左子树 --> 右子树
printf("%d ", root->val);//访问根节点数据
PreOrder_Traversal(root->left);//找左子树
PreOrder_Traversal(root->right);
}
前序打印结果:
同理,中序遍历就是 遇到根节点并不访问,先去找左子树,左子树找完回来再访问根,然后再去找右子树
在前序遍历的基础上 如图:
代码:
//二叉树的中序遍历
void InOrder_Traversal(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
//先左子树 --> 根 --> 右子树
InOrder_Traversal(root->left);
printf("%d ", root->val);
InOrder_Traversal(root->right);
}
③ 后序遍历
后序遍历: 先访问左子树,然后访问右子树,左右子树都找完了再回来访问根节点
//二叉树的后序遍历
void PostOrder_Traversal(BTNode*root)
{
if (root == NULL)
{
printf("# ");
return;
}
//左树 --> 右树 --> 根
PostOrder_Traversal(root->left);
PostOrder_Traversal(root->right);
printf("%d ", root->val);
}
2. 广度优先遍历
层序遍历
层序遍历就是一种广度优先遍历,这种遍历会先访问同一层的节点,而不会一昧的往深了走
但是二叉树的结构是这样的:
每一个根 只能去找他的左右孩子,而并没有兄弟节点去找每一层的兄弟
那么怎么实现呢?
—— 利用队列!
我们可以利用队列 先进先出的性质 来实现对每一层的遍历
- 根节点入队,然后出队,把根节点的左孩子left和右孩子right入队
- left出队的同时 left->left和left->right入队
- right出队的同时right->left和right->right入队
- 继续上面过程,直到队列为空
但是这里有个问题就是 完成层序遍历需要队列这个数据结构
C语言没有库!所以只能我们自己写一个队列的数据结构!
队列的实现比较简单,博主就不写了哈~~
层序遍历代码
void TreeLevel(BTNode* root)
{
Queue q;//创建队列
QueueInit(&q);//队列初始化
//如果root为空,那么直接返回
if (root == NULL)
return;
//然后把root根节点push到队列
// 注意push的是 树的一整个节点:因为需要利用该节点的拷贝去找下一个节点!(递归)
QueuePush(&q, root);
// 进入循环
while (!QueueEmpty(&q))//如果队列不为空
{
//拿到队头元素(树节点指针的拷贝)
BTNode* front = QueueFront(&q);
// 拿到之后出队即可
//先打印一下
printf("%d ", front->val);
QueuePop(&q);
//当前节点出队之后 带入root的两个子节点(即下一层入队)
if (front->left)//如果左节点不为空,入队
{
QueuePush(&q, front->left);
}
if (front->right)//右节点不为空,入队!
{
QueuePush(&q, front->right);
}
//如果左右节点都为空,那么直接把该front出队即可。
}
}
2️⃣求二叉树的节点个数
方法1
因为二叉树是递归实现的,所以如果简单地像链表那样,在函数内部定义一个局部变量通过遍历求出节点个数,会涉及到一个问题:每一次递归都会创建一个新的局部变量,实际上这个局部变量并不会起到计数的作用
所以我们可以利用一个全局变量记录节点的个数
思路很简单:前序遍历,如果节点不为空 count++
int count = 0;//定义全局变量
void TreeSize1(BTNode* root)
{
if (root == NULL)
{
return;
}
++count;
TreeSize1(root->left);
TreeSize1(root->right);
}
缺陷:
- 每一次调用都要先在主函数中把count清0,因为count的值是上一次求节点个数的值,并没有被清零!
- 多线程问题:count是全局变量,可能被多个线程同时利用,这样计算出的count就有问题!
我们可以利用返回值+递归的方法
也就是分治思想:
root的节点数量 = 1 + root->left的节点数量 + root->right的节点数量
int TreeSize2(BTNode* root)
{
return root == NULL ? 0 : 1 + TreeSize2(root->left) + TreeSize2(root->right);
}
3️⃣求叶子节点数量
叶子节点有一个特征:
节点的左孩子和右孩子都为NULL
所以这就是我们遍历的一个限制条件
- 如果节点为空 返回0
- 如果节点的左右孩子都为空:返回1 (是叶子节点)
- 如果都不满足,说明正在查找的该节点不是叶子节点,我们递归去找该节点的左右孩子
int TreeLeafSize(BTNode* root)
{
return root == NULL ? 0 : ((root->left == NULL && root->right == NULL) ? 1 : TreeLeafSize(root->left) + TreeLeafSize(root->right));
}
4️⃣求第k层节点的个数
int KLevelSize(BTNode* root, int k)
{
assert(k >= 1);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
//如果 k不等于1 那么继续递归
return KLevelSize(root->left, k - 1) + KLevelSize(root->right, k - 1);
}
5️⃣查找某个节点
BTNode* TreeFind(BTNode* root,BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->val == x)
{
return root;
}
// 简单的逻辑: 先找左树 找到就返回,找不到去找右树,如果也找不到 返回空
// 每一个子树都这样进行!
BTNode* left = TreeFind(root->left, x);
if (left)
return left;
BTNode* right = TreeFind(root->right, x);
if (right)
return right;
//这里也可以不用找右树,直接返回右树的结果
// 因为右树也有两个结果:1. 空 ,2. 找到了
//return TreeFind(root->right, x);
return NULL;
//以下是三目的方法
}
6️⃣求二叉树的深度
分析:
求root的深度 也就是求出 1 + 左右孩子深度的较大值
int TreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeDepth(root->left);
int right = TreeDepth(root->right);
int max = left > right ? left : right;
return 1 + max;
//return left > right ? left + 1 : right + 1;
}
7️⃣二叉树的销毁
最直接的想法是 直接遍历就好了啊 把每一个节点销毁释放!
但是 要用后序哦!!
因为如果用前序,先把根销毁了怎么找 左右孩子呢?找不到了!
利用后序 销毁的顺序应该是 3 2 5 6 4 1
我们可以每一次销毁之前打印一下验证对不对
void TreeDestory(BTNode* root)
{
if (root == NULL)
return;
//如果不为空
TreeDestory(root->left);
TreeDestory(root->right);
//销毁之前打印一下
printf("%d ", root->val);
free(root);
}
8️⃣判断是否为完全二叉树
我们知道完全二叉树的最后一层是 从左到右依次编号的,最后一层不可以存在有右子树而没有左子树的情况
如图就是一个非完全二叉树 3的后面为空,而空的后面还有非空的节点!
那么如何判断是否为空呢?
我们可以借助队列!
如果是完全二叉树 应该是这样
代码
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root == NULL)// 完全二叉树也可以是空树
return true;
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取出 队头
BTNode* front = QueueFront(&q);
// 然后出队
QueuePop(&q);
if (front)
{
// 这里不需要判断front的左右是否为空 空也需要入队
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
else// 如果front为空直接break
{
break;
}
}
//退出循环的时候 说明遇到了空
// 再一次进入循环 找一找有没有非空
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);//这里必须先pop一下 否则就死循环了!
// 如果遇到非空 返回false
if (front)
{
QueueDestory(&q);
return false;
}
}
QueueDestory(&q);
//来到这 说明 第一次遇到空之后全都是空了
return true;
}
⭐写在最后⭐
2022 / 06 / 06 高考倒计时:1天
去年这个时候我正在准备明天的高考
今年,我的复读的同学正在紧张地复习
是的去年我也考砸了,但是决定人生的并不是高考
今后路还长
放平心态,不要去想什么高考多难,不要去听一些 “千军万马过独木桥”
拿出平时做练习的姿态去迎接这场考试就好
2022的考生,高考加油!
愿你们前程 如你们所愿
✨感谢阅读~ ✨
❤️码字不易,给个赞吧~❤️



