【C语言】数据结构-链式二叉树,详解分治递归和层序遍历
慕雪年华

[TOC]

前言

在之前关于树的学习中,我们接触了二叉树的知识点,以及堆和堆排序的操作。

两个知识点都是超链接,可以点击查看我之前的博客,复习一下这两个知识点哦!

image

接下来我们要更进一步,学习一下链式二叉树的操作

本篇博客将以知识点讲解+OJ题目验证的方式来展开链式二叉树的内容


1.链式二叉树的基本结构

在学习链式二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。

之前我们提到过,树最优的表示方法是父母孩子表示法。但是对于二叉树这种度固定的树来说,可以 直接使用最简单的方法,定义两个指针指向它的左右叶子节点即可

1
2
3
4
5
6
7
8
typedef int BTDataType;

typedef struct BTreeNode
{
BTDataType data;
struct BTreeNode* left;
struct BTreeNode* right;
}BTNode;

这里要说明的一件事是:普通树的“增删查改”操作是没有意义的,因为树并不是一个最优的储存结构。所以我们学习链式二叉树的操作时,更多学习的是分治 递归思想


2.分治递归思想

什么是分治思想

举个例子,学校里面需要进行排查,找出本校里面身高最高的人。这时候校长可以去找各个年级的级组长,然后级组长去找各个班主任,班主任让班级里面的小组长统计组员身高数据。

这时候的小组长已经可以返回一个身高最高的值给班主任了,然后再层层上报,校长只需要在最后上报的4个数据中找出一个最高的,即为本校最高的同学

image

分治策略的思想就是分而治之,即先将一个规模较大的大问题分解成若干个规模较小的小问题,再对这些小问题进行解决,得到的解,在将其组合起来得到最终的解。在上面的例子中,较小的问题就是小组长统计组员身高,并上报。转换成代码语言就是return一个值

更详细的解释可以参考这篇大佬的博客👇

五大常见算法策略之——递归与分治策略

早先学习的递归求斐波那契数就运用了分治的思想👉传送门

1
2
3
4
5
6
7
int fo2(int a)
{
if ((a == 1) || (a == 2))
return 1;
else
return (fo2(a - 1) )+( fo2(a- 2));//n-1和n-2项
}

当a=1或者2的时候,就是分治的末端节点,通过return 1开始终止递归


3.前/中/后序遍历

了解了上面所说的分治递归思想后,接下来我们再学习链式二叉树的三种遍历方式

  • 前序遍历:根节点-左子树-右子树
  • 中序遍历:左子树-根节点-右子树
  • 后序遍历:左子树-右子树-根节点

从前序遍历入手,我们来实操一下分治的思想:利用递归,以前序遍历的顺序打印出树中节点的值

假设我们现在创建了一个这样的简单二叉树👇你能想出来前序遍历的打印顺序应该是咋样的吗?

image

答案是1 2 3 4 5 6

看到这里,你肯定一脸懵逼:啊,咋出来的?

image

不着急,我们现给打印出来的内容加上它们的末端子树NULL,所以前序遍历的结果是:

1
1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

不卖关子啦,直接下手分析这个遍历结果是怎么出来的!

前面提到了,前序遍历的顺序是:根节点-左子树-右子树

image

下图能让你更直观地看出来这三种遍历方式的不同

image

其中前序遍历转换为代码语言就是下面这样

1
2
3
4
5
6
7
8
9
10
11
12
// 二叉树前序遍历 
void BTreePrevOrder(BTNode* root)
{
if (root == NULL)
{//为了方便理解,把空节点也打印出来
printf("NULL ");
return ;
}
printf("%d ", root->data);
BTreePrevOrder(root->left);
BTreePrevOrder(root->right);
}

在这之中,遇到根节点是NULL的情况,就是分治的末端情况,递归停止

这样说来恐怕还是不清楚,要彻底弄清,我们必须要通过画递归示意图来解决

image

图中某个单词打错了,画到一半才发现……请忽略它!😭


如果你能理解上图中前序遍历的思路,那中序遍历和后序遍历的操作就非常简单了!猜猜怎么修改前序的代码呢?

没错,只需要更改一下printf的位置就可以了!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 二叉树中序遍历
void BTreeInOrder(BTNode* root)
{
if (root == NULL){
printf("NULL ");
return;
}

BTreeInOrder(root->left);
printf("%d ", root->data);
BTreeInOrder(root->right);
}
// 二叉树后序遍历
void BTreePostOrder(BTNode* root)
{
if (root == NULL){
printf("NULL ");
return;
}

BTreePostOrder(root->left);
BTreePostOrder(root->right);
printf("%d ", root->data);
}

最后打印出来的结果分别是这样的,和上面的示意图完全对应!回到示意图

image


3.1通过递归遍历计算节点个数

上面的递归,我们打印出了各个节点的值

只需要对其中一个递归的代码进行小修改,将printf改成计数++,就能把它从遍历变成计算二叉树的节点个数

这里我选择指针变量的方式让主函数中能获取计数的结果

1
2
3
4
5
6
7
8
9
10
// 二叉树节点个数
void BTreeSize(BTNode* root,int* pcount)
{
if (root == NULL)
return ;

(*pcount)++;//指针变量,main函数中可调用
BTreeSize(root->left,pcount);
BTreeSize(root->right,pcount);
}

你可以使用全局静态变量来进行计数,但是那样的计数会在下一次调用的时候叠加,需要在调用后置0,非常不方便

image

当然,我贴出来的这个方法也不是最优的,因为它需要创建一个额外的变量count作为参数调用,而不能直接return节点的数量

image

所以就有了下面这个使用三目操作符? :来进行分治递归,计算节点个数

  • 其中根节点为空是末端情况,返回0
  • 其他情况返回左子树和右子树的节点大小+1(该节点自己)
1
2
3
4
5
6
//进阶方法
int BTreeSize(BTNode* root) {
return root == NULL ? 0 :
BTreeSize(root->left)
+ BTreeSize(root->right) + 1;
}

3.2 用后续遍历的思想销毁树

当我们不需要用二叉树后,需要将其调用的内存释放

问题就来了,如果你释放了根节点,那要咋找到它的左右子树呢

所以我们在释放的时候,要用后序遍历的顺序来进行释放,即先销毁左右子树,再向上销毁。这样就能避免找不到子树的问题

1
2
3
4
5
6
7
8
9
10
11
12
// 二叉树销毁
void BTreeDestory(BTNode** root)
{
if (*root == NULL)
return;

//通过后续遍历的思想来摧毁树
BTreeDestory(&(*root)->left);
BTreeDestory(&(*root)->right);
free(*root);
*root = NULL;//使用二级指针可以直接在函数中置空根节点的指针
}

3.3前/中/后序遍历OJ题

三道Leetcode OJ题

这里只对前序遍历的题目做出讲解,因为后面两个的思路完全一致,只需稍微更改代码

image

题目给出一个树,需要你将它以前序遍历的顺序,将各个节点的值保存在一个数组中并返回它

这里的输入用例是“伪代码”,[1,null,2,3]代表1的左子树是NULL,右子树是2;2的左子树是3,右子树是NULL

既然需要用数组来储存,首先我们需要知道这个二叉树一共有几个节点,这样才能方便我们开辟数组

  • 注意:这种接口型题目,数组都必须是动态内存函数malloc开辟的

image

然后把前序遍历中的printf改成将值放入arr数组中即可!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 二叉树节点个数
void BTreeSize(struct TreeNode* root,int* pcount)
{
if (root == NULL)
return ;

(*pcount)++;
BTreeSize(root->left,pcount);
BTreeSize(root->right,pcount);

}
// 前序遍历代码
void BTreePrevOrder(struct TreeNode* root,int*arr,int* i)
{
if (root == NULL){
return ;
}

arr[(*i)++]=root->val;
//因为在递归调用中需要多次调用不同的i,所以需要取地址
BTreePrevOrder(root->left,arr,i);
BTreePrevOrder(root->right,arr,i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
int count=0;
BTreeSize(root,&count);//计算树节点个数
int* arr=(int*)malloc(sizeof(int)*count);//开辟数组

int i=0;//下标
BTreePrevOrder(root,arr,&i);
*returnSize=count;
return arr;
}

image


4.计算节点个数

3.1中已经讲述了计算二叉树节点个数的方法,下面是更细致的节点个数计算

4.1叶子节点个数

众所周知,在这颗二叉树中,只有3、5和6是叶子节点

image

想要判断一个节点是不是叶子节点,其实非常简单:只要它的左右子树都是空,就是叶子节点了。

  • 以此作为分治的末端条件,只要满足这个条件,就返回1
  • 如果已经遍历到空节点了,返回0
  • 其他情况,返回左子树和右子树的叶子节点个数之和
1
2
3
4
5
6
7
8
9
10
11
// 二叉树叶子节点个数
int BTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;

if (root->left == NULL && root->right == NULL)
return 1;

return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

4.2二叉树第k层节点个数

假设根节点是第1层,要想知道第k层一共有几个节点,需要怎么设计函数呢?

image

先来这么想:3所在层数对于根来说是第三层,但是对于2来说是第二层,对于3自己来说是第1层

那么,我们是不是可以让第k层往下-1来进行递归呢?

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 二叉树第k层节点个数
int BTreeLevelKSize(BTNode* root, int k)
{
assert(k >= 1);//保证k>=1

if (root == NULL)
return 0;

if (k == 1)
return 1;

return BTreeLevelKSize(root->left,k - 1)
+ BTreeLevelKSize(root->right,k-1);
}

image


4.3二叉树的深度

在之前树的概念学习中,讲解过树的深度(即树一共有几层)

深度和之前举例的校长统计身高很相似,我们需要找出左右子树中较深的那一个并进行返回。末端的条件,就是节点为空的时候,return 0终止递归

1
2
3
4
5
6
7
8
9
10
11
// 二叉树深度,即一共有几层
int BTreeDepth(BTNode* root)
{
if (root == NULL)
return 0;

int left = BTreeDepth(root->left);
int right = BTreeDepth(root->right);

return left > right ? left + 1 : right + 1;
}

注意:这里left+1和right+1是为了计算上节点自己

求二叉树深度OJ题

leetcode上有一道oj题就是求二叉树的最大深度,代码复制上,改个名,搞定!

题目链接:104. 二叉树的最大深度

image


5.查找树中值为x的节点

在二叉树中查找一个值,基本思想就是把它遍历一遍,判断根节点以及左右子树中是否有x值的节点。

具体的解析,写道下面的代码注释里啦!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;//节点为空返回空

if (root->data == x)
return root;//节点自己就是x,返回节点自己的地址

BTNode* ret1 = BTreeFind(root->left, x);
if (ret1 != NULL)//如果左边找到了,返回左节点的地址
return ret1;

BTNode* ret2 = BTreeFind(root->right, x);
if (ret2 != NULL)//如果右边找到了,返回右节点的地址
return ret2;

return NULL;//两个都找不到,它自己也不是,返回空
}

6.层序遍历

如同其名,层序遍历就是一层一层地遍历

image

比如上面这棵树,层序遍历的结果如下

1
1 2 4 3 NULL 5 6

要想实现层序遍历,我们需要借助之前学习的栈和队列知识里的队列👉传送门

在VS项目里面,导入预先写好的队列的头文件和源文件,再引用它就可以了!

image

这里就能体现出之前预先typedef类型的作用了:只需要更改最先的数据类型,就可以搞定后面的一切!

image

而引用头文件的时候,因为我们需要在栈的代码中使用二叉树的定义,所以需要先引用二叉树的头文件,再引用队列的头文件

image

搞定这个后,我们再来讲述一下层序遍历的思路

先插入根节点,然后在根节点出队列的同时,插入它的左右子树的节点

当队列中的值都为NULL时,代表层序遍历完成

image

所以我们需要入队列的不是节点的值,因为那样无法找到节点的左右子树。入队列的是节点的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 层序遍历
void BTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);

if (root != NULL){//根节点非空,开始入队列
QueuePush(&q, root);
}

while (!QueueEmpty(&q))
{
BTNode* head = QueueFront(&q);//取队头数据
QueuePop(&q);//出队列

printf("%d ", head->data);
if (head->left != NULL)
{
QueuePush(&q, head->left);
}
if (head->right != NULL)
{
QueuePush(&q, head->right);
}
//层序遍历不需要递归,可以用循环解决问题
}

printf("\n");
QueueDestory(&q);//防止内存泄漏
return;
}

遍历的结果如下

image

6.1判断二叉树是否为完全二叉树

学习了层序遍历后,就可以来判断一个二叉树是否为完全二叉树了!

完全二叉树:前k-1层为满二叉树,最后一层不满,但是从左到右分布

image

具体的思路是

  • 当队列中的队头为NULL时开始遍历,如果队列中都是NULL,代表是满二叉树
  • 如果有非空节点,就不是满二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);

if (root != NULL) {
QueuePush(&q, root);
}

while (!QueueEmpty(&q))
{
BTNode* head = QueueFront(&q);//取队头数据
QueuePop(&q);//出队列

if (head == NULL){
break;//遇到队列中空节点,退出循环
}

QueuePush(&q, head->left);
QueuePush(&q, head->right);
}

while (!QueueEmpty(&q))
{
BTNode* head = QueueFront(&q);//取队头数据
QueuePop(&q);//出队列

if (head != NULL)
{
//printf("不是完全二叉树\n");
return false;
}
}

QueueDestory(&q);//防止内存泄漏
return true;
}

结语

链式二叉树的内容到这里就结束啦!

如果博客里面有讲的不清楚的地方,欢迎大家在评论区提出哦!

image

下篇博客将讲解一些有关二叉树的OJ题和概念选择题!我们不见不散哦~