C语言实现二叉树的基本操作
- 导读
- 一、层次遍历
- 1.1 算法思路
- 1.2 算法实现
- 1.2.1 存储结构的选择
- 1.2.2 函数的三要素
- 1.2.3 函数的实现
- 1.3 小结
- 二、求二叉树的深度
- 2.1 层序遍历
- 2.2 分治思想——递归
- 三、 求二叉树的结点数
- 3.1 求二叉树的结点总数
- 3.1.1 层序遍历
- 3.1.2 分治思想——递归
- 3.2 求二叉树第K层的结点数
- 3.2.1 层序遍历
- 3.2.2 分治思想——递归
- 3.3 求二叉树叶结点数
- 3.3.1 层序遍历
- 3.3.2 分治思想——递归
- 结语
导读
大家好，很高兴又和大家见面啦！！！
在上一篇内容中，咱们详细介绍了二叉树的三种遍历算法以及算法的递归与非递归之间的转换。在今天的内容中我们将会继续介绍二叉树的一些基本操作如二叉树的层次遍历、求二叉树的深度、求二叉树的结点总数、求二叉树第K层的结点数、求二叉树的叶结点数……以及如何通过C语言来实现这些基本操作。
通过今天的内容我们将对二叉树的递归定义会有更进一步的了解，接下来我们就进入今天的主题吧！！！
一、层次遍历
在树形结构中，从根结点开始一直往下到叶结点结束，整棵树被分成了不同的层次，根结点为第一层，其子结点为第二层，以此类推。而树的层次遍历指的是按照树的层次，从第一层开始依次对每一层的结点进行访问，如下所示：
图中例举的二叉树如果按照层序遍历的方式，则会得到结点序列 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a_1a_2a_3a_4a_5a_6a_7a_8 a1a2a3a4a5a6a7a8。那现在问题来了，我们应该如何实现二叉树的层次遍历呢？
1.1 算法思路
这里有两种思路：
-
通过顺序存储的方式将树中的各个结点存放进数组中，然后依次访问数组中的各个元素，如下所示：
在二叉树的顺序存储中结点就是按照层次依次存入数组，因此顺序存储是可以实现二叉树的层次遍历的。但是顺序存储在前面我们也讨论过，它更适合于满二叉树和完全二叉树，对于如上图这种一般的二叉树而言，很容易造成空间的浪费。 -
为了减少空间的浪费，提高空间的利用率，我们可以借助队列来实现。通过队列实现的具体思路如下：
- 先将根结点入队
- 若结点有左孩子，则将左孩子入队；若结点有右孩子则将右孩子入队；
- 完成结点的左右孩子入队后，将该结点出队；
- 访问队尾结点并重复第二步和第三步直到队列为空
在队列中，由于数据元素的操作特性为先入先出，所以当我们从上往下遍历时，位于队头的元素一定是队尾元素的上一层或者同一层的元素。
1.2 算法实现
1.2.1 存储结构的选择
在今天的算法实现中，我们同样还是采用二叉链表的存储结构来实现二叉树的基本操作，对应的数据结构类型如下所示：
//二叉链表
typedef int ElemType;
typedef struct BTNode {
ElemType data;//数据域
struct BTNode* lchild, * rchild;//指针域
}BTN, * BTL;
//BTN——二叉树的结点类型
//BTL——二叉链表的类型
对于二叉树的层次遍历，这里我们主要介绍的是第二种思路——通过队列实现二叉树的层序遍历。因此我们还需要定义一个能够存储二叉树的结点的队列，队列的数据类型如下所示：
//存放二叉树结点的链队列
typedef struct LinkNode {
BTN* data;//数据域
struct LinkNode* next;//指针域
}LQN;//链队列的结点类型
typedef struct LinkQueue {
LQN* front, * rear;//链队列的队头与队尾指针
}LQ;//链队列的数据类型
考虑到二叉树中的层数是未知的，每一层的结点数也是未知的，因此这里我选用的是链队列来实现，当然大家也可以选用循环队列来实现，这个可以根据个人的需求进行选择。
1.2.2 函数的三要素
在层序遍历的算法中，我们想要解决的问题是实现二叉树的层序遍历，因此函数名我们不妨定为LevelOrder——层次遍历；
在完成遍历后，我们不需要任何的返回值，所以函数的返回类型定为void；
在该算法中，我们需要处理的对象是二叉树，所以函数的参数肯定是整棵二叉树；
//二叉树的层序遍历
void LevelOrder(BTL T);
这里大家需要注意的是形参T的数据类型是一个一级指针，在涉及到参数为指针时，建议大家养成判断指针是否为空指针的习惯。
1.2.3 函数的实现
由于该算法是借助队列来实现的，因此在进入函数后，我们需要先创建一个队列并将其初始化：
LQ Q;//创建链队列
InitQueue(&Q);//初始化链队列
在完成队列的初始化后，我们需要先将二叉树的根结点进行入队，在后续的遍历过程中我们同样是借助临时指针p来完成二叉树的遍历：
BTN* p = T;//指针p指向根结点
EnQueue(&Q, p);//将根结点入队
之后的操作过程就是不断的重复入队与出队的操作，直到队列为空才结束，因此我们需要通过循环来实现整个过程，整个循环可以用队列是否为空来进行控制：
while (!isEmpty(Q)) {
//当队列非空时，进入循环
}
在循环体中我们需要做两件事——入队与出队：
- 当结点的左孩子或右孩子非空时入队
- 完成入队后将该元素出队
在完成了入队与出队后，我们还需要获取当前的队头元素，对应代码如下所示：
if (p->lchild)//判断左孩子是否为空
EnQueue(&Q, p->lchild);//非空则入队
if (p->rchild)//判断右孩子是否为空
EnQueue(&Q, p->rchild);//非空则入队
DeQueue(&Q, &p);//队头元素出队
visit(p);//访问队头元素
GetHead(Q, &p);//获取队头元素
当然，我们也可以先将队头元素出队，再将该元素的左孩子与右孩子入队：
DeQueue(&Q, &p);//队头元素出队
visit(p);//访问队头元素
if (p->lchild)//判断左孩子是否为空
EnQueue(&Q, p->lchild);//非空则入队
if (p->rchild)//判断右孩子是否为空
EnQueue(&Q, p->rchild);//非空则入队
像这样的话，我们就不需要重复获取队头元素了，这两种方式都是可以的，根据个人喜好来选择具体的编写方式。现在我们也就完成了层序遍历的算法实现，完整代码如下所示：
//二叉树的层序遍历
void LevelOrder(BTL T) {
assert(T);
LQ Q;//创建链队列
InitQueue(&Q);//初始化链队列
BTN* p = T;//指针p指向根结点
EnQueue(&Q, p);//将根结点入队
while (!isEmpty(Q)) {
//当队列非空时，进入循环
DeQueue(&Q, &p);//队头元素出队
visit(p);//访问队头元素
if (p->lchild)//判断左孩子是否为空
EnQueue(&Q, p->lchild);//非空则入队
if (p->rchild)//判断右孩子是否为空
EnQueue(&Q, p->rchild);//非空则入队
}
}
1.3 小结
在二叉树的遍历中，不管是先序、中序、后序还是层序遍历，当我们想用非递归的方式实现遍历时，如何找到一个结点的父结点是我们必须攻克的难题。因此我们需要借助线性表、链表、栈和队列等这些方便存取数据的数据结构来实现二叉树的遍历。
在先序、中序和后序遍历中，因为我们是从二叉树的下层结点依次往上进行访问，因此对结点操作时满足后入先出的操作特性，所以我们在实现非递归算法时借助了栈；
在层序遍历中，因为是从二叉树的上层结点依次往下进行访问，因此对结点操作时满足先入先出的操作特性，所以我们在实现层序遍历时借助了队列；
在二叉树中，二叉树的遍历是二叉树的其它操作的基础，不管是求二叉树的深度、求二叉树的总结点数、求二叉树第K层的结点数、求二叉树的叶结点数……这些操作都是基于二叉树的遍历才能得以实先，所以我们必须要掌握二叉树的这四种遍历算法。
二、求二叉树的深度
二叉树的深度也就是二叉树的高度同样也是二叉树的最大层次。因此我们如果想求二叉树的深度，我们只需要找到最底层的结点即可，实现的方式有很多，这里我主要介绍两种方式：
- 通过层序遍历找到二叉树的最底层的结点
- 通过递归找到二叉树最底层的结点
2.1 层序遍历
前面我们才介绍过，二叉树的层序遍历就是从第一层开始一层一层的往下找，因此我们可以通过计数器来记录查找的层数，那现在就有一个问题——我们应该如何判断查找的是第几层？
在二叉树中，由于每一层的结点数都不相同，我们可以通过记录每一层的结点数来完成层数的判断：
- 在计算第 i i i层的结点数时，我们通过在记录第 i − 1 i-1 i−1层中入栈的结点个数来实现；
- 在计算当前层次时，我们通过将上一层的元素全部出队后获取；
因此我们需要有三个变量来实现：
- 记录当前层序的变量
level； - 记录当前层序的结点个数的变量
level_num； - 记录下一层的结点个数的变量
nextleve_num；
算法的实现需要两层循环：
- 第一层循环记录当前的层序；
- 第二层循环将当前层序中的结点全部出队；
在第二层循环结束时，说明当前层序的结点全部完成了出队，此时如果下一层的结点数量不为0，那就说明二叉树还有一层，这时我们需要将层序加1；
当下一层的结点数量为0时，那就说明此时已经是二叉树的最大层序，我们只需要将该层序返回给函数即可，对应代码如下所示：
//二叉树的深度——层序遍历
int Depth(BTN* root) {
if (!root)
return 0;
LQ Q;//创建链队列
InitQueue(&Q);//初始化链队列
BTN* p = root;//指向二叉树结点的指针
EnQueue(&Q, p);//将根结点入队
int level = 1;//记录二叉树的层序
int level_num = 1;//记录当前层次的结点个数
int nextlevel_num = 0;//记录下一层的结点个数
for (level; isEmpty(Q); ) {
while (level_num) {
DeQueue(&Q, &p);
level_num--;//每出队一个元素，该层结点个数-1
if (p->lchild) {
EnQueue(&Q, p->lchild);
nextlevel_num++;//每入队一个元素，下层结点个数+1
}
if (p->rchild) {
EnQueue(&Q, p->rchild);
nextlevel_num++;//每入队一个元素，下层结点个数+1
}
}
level_num = nextlevel_num;//记录下一层的结点个数
nextlevel_num = 0;
if(level_num)
level++;//当下一层的结点个数不为0时，层次+1
}
return level;
}
2.2 分治思想——递归
一棵二叉树是由三个部分组成——左子树、根结点和右子树。而二叉树的深度则是二叉树中左右子树深度的最大值加上根结点的深度1，因此我们要求二叉树的深度，我们可以将其转换成求左右子树的最大深度。
假设有一棵结点数为n的二叉树，其左子树的深度为 h 1 h_1 h1，右子树的深度为 h 2 h_2 h2，那么该二叉树的深度为左右子树深度的最大值+1，即 h = m a x ( h 1 , h 2 ) + 1 h=max(h_1,h_2)+1 h=max(h1,h2)+1，如下所示：
在上图的例子中，我们如果要求
a
1
a_1
a1这棵树的深度
h
h
h，我们就需要将其左子树
a
2
a_2
a2的深度
h
1
h_1
h1和右子树
a
3
a_3
a3的深度
h
2
h_2
h2求出来，然后再取两棵子树深度的最大值+1就是
a
1
a_1
a1这棵树的深度了。
现在问题就变成了如何求左子树 a 2 a_2 a2的深度 h 1 h_1 h1和右子树 a 3 a_3 a3的深度 h 2 h_2 h2？
在介绍二叉树的遍历时，我们为了完成整棵二叉树的遍历就曾将二叉树分为三个部分：左子树、根结点、右子树，之后就通过遍历这三个部分来实现二叉树的遍历，而在遍历左子树和右子树时，我们又同样将其分为这三个部分，以此类推，直到完成所有结点的遍历，这就是递归的思想，将复杂的问题拆分成一个个重复的简单问题。
按照同样的思路，现在我们要求二叉树的深度，实际上就是求的二叉树的左子树的深度和右子树的深度，因此我们根据这种递归的思路就可以编写如下代码：
//二叉树的深度——递归
int Depth2(BTN* root) {
if (!root)//当树为空树时
return 0;//返回0
int l = Depth2(root->lchild);//递归查找左子树的深度
int r = Depth2(root->rchild);//递归查找右子树的深度
return l > r ? l + 1 : r + 1;//返回左右子树深度的最大值+1
}
可以看到当我们在求二叉树的深度时，我们将其拆分成了求左子树的深度和右子树的深度，这种将问题拆分的思路是算法中的分治思想，目前我们先简单的了解一下，在后面的内容中我们会再进一步介绍该内容。
三、 求二叉树的结点数
在二叉树中我们可能会遇到求一棵二叉树的总结点数、对高为h的二叉树求第K层的结点数、求二叉树的叶结点数……一系列的求结点数的问题，下面我们就来分别介绍一下如何求二叉树的总结点数，求第K层二叉树的结点数以及求二叉树的叶结点数。
3.1 求二叉树的结点总数
对于二叉树而言，如果我们要求树中总的结点个数，我们能够想到的方式就是将每一层的结点数都求出来然后相加，那如何求每一层的结点数呢？
3.1.1 层序遍历
有朋友很快就想到了，可以通过层序遍历的方式，在对二叉树进行层序遍历时，设置一个计数器，每出队一个元素，计数器就+1，我们就能获取二叉树的结点总数了，代码如下所示：
//二叉树的结点总数——层序遍历
int BTSize(BTL T) {
if (!T)//当树为空树时
return 0;
LQ Q;//创建链队列
InitQueue(&Q);//初始化链队列
BTN* p = T;
EnQueue(&Q, p);
int count = 0;//计数器
while (!isEmpty(Q)) {
DeQueue(&Q, &p);
count++;//每出队一个元素，计数器+1
if (p->lchild)
EnQueue(&Q, p->lchild);
if (p->rchild)
EnQueue(&Q, p->rchild);
}
return count;
}
那还有没有其它的解题思路呢？
3.1.2 分治思想——递归
在求二叉树的深度时，我们根据分治的思想将其拆分成了求左右子树的深度。
同理，在这里我们也可以通过分治的思想将求二叉树的结点总数 n n n拆分成求二叉树的左子树的结点数 n 1 n_1 n1与二叉树的右子树的结点数 n 2 n_2 n2。最终二叉树的结点数为左子树的结点数+右子树的结点数+根结点，即 n = n 1 + n 2 + 1 n=n_1+n_2+1 n=n1+n2+1，代码如下所示：
//二叉树的结点总数——递归（分治）
int BTSize2(BTL T) {
if (!T)
return 0;
return BTSize(T->lchild) + BTSize(T->rchild) + 1;
}
3.2 求二叉树第K层的结点数
这个基本操作的实现的第一种思路是通过层序遍历的方式，找到第K层这样我们就可以获取第K层的结点数了。在这种思路中，如何找到第K层就是我们需要关注的问题。
3.2.1 层序遍历
- 因为层序遍历是从第一层开始遍历，因此我们可以通过变量level来记录当前遍历的层次；
- 在层序遍历中，我们主要是通过队列进行结点的入队和出队。当我们遍历到第 i i i层时，入队的元素则是第 i + 1 i+1 i+1层的结点，而出队的元素是第 i i i层的结点。
- 当我们要找第K层的结点数时，我们只需要在对
K
−
1
K-1
K−1层的元素进行出队时记录第
K
K
K层的元素即可，因此我们可以通过
level_num来记录第 i i i层的结点个数，通过nextlevel_num来记录第 i + 1 i+1 i+1层的结点个数； - 每入队一个元素我们需要增加
nextlevel_num的值，每出队一个元素我们需要减少level_num的值； - 当
level_num为0时表示第i层的元素全部完成出队，此时我们就需要通过level_num来记录下一层的结点个数；
完整代码如下所示：
//求第K层的结点数——层序遍历
int LevelKSize(BTL T, int k) {
if (!T)//当树为空树时
return 0;
LQ Q;//创建链队列
InitQueue(&Q);//初始化队列
BTN* p = T;//遍历二叉树的指针
EnQueue(&Q, p);//将根结点入队
int level = 1;//记录层次
int level_num = 1;//记录该层的结点数
int nextlevel_num = 0;//记录下一层的结点数
for (level; level < k; level++) {
while (level_num) {
DeQueue(&Q, &p);//将第i层的元素出队
level_num--;//第i层的元素个数-1
if (p->lchild) {
EnQueue(&Q, p->lchild);//该元素有左孩子时，将左孩子入队
nextlevel_num++;//下一层元素个数+1
}
if (p->rchild) {
EnQueue(&Q, p->rchild);//该元素有右孩子时，将右孩子入队
nextlevel_num++;//下一层元素个数+1
}
}
//当结束循环时表示第i层的元素全部完成出队
level_num = nextlevel_num;//记录下一层的结点数
nextlevel_num = 0;
}
//当结束循环时，变量level_num记录的就是第K层的结点数
return level_num;
}
3.2.2 分治思想——递归
从层序遍历的算法中我们不难发现，在求第 K K K层的结点数量时，我们需要知道第 K − 1 K-1 K−1层的结点数量，同理在求第 K − 1 K-1 K−1层的结点数量是，我们需要知道第 K − 2 K-2 K−2层的结点数量，以此类推，最终问题就会变成求第1层的结点数量。
在二叉树中，第一层的结点数量是固定的，第一层只有一个根结点，所以结点数量为1，那么第二层的结点数量就变成了第一层结点的左右子树的结点数量之和；第三层的结点数量就变成了第二层结点的左右子树之和的总数……以此类推，那我们就得到了第 K K K层的结点数量是第 K − 1 K-1 K−1层所有结点的左右子树之和；
可以看到，此时我们就把问题转变成了求第 K − 1 K-1 K−1层所有结点的左右子树之和，对应的代码如下所示：
//第K层的结点数量——递归
int LevelKSize2(BTL T, int k) {
if (!T)
return 0;
if (k == 1)
return 1;
int l = LevelKSize2(T->lchild, k - 1);//获取第K-1层的左子树结点数
int r = LevelKSize2(T->rchild, k - 1);//获取第K-1层的右子树结点数
return l + r;//返回左右子树结点数之和
}
这个代码看上去不太好理解，下面我们通过图来帮助理解该算法：
注意看图中的左右两侧的K值左侧的是我们递归时向函数传入的K值，右侧是我们实际求的K值。函数在传参时传入的是根结点和需要求的层数K，当我们通过递归算法从上往下找时，整个算法执行的过程以前5层为例，如下所示：
从图中可以看到每一次递进只要该结点不为空就会继续往下递进，直到k=1时然后开始回归；当结点为空时，则不不再进行往下递进，直接回归。图比较小，我们需要重点关注的是每一层递进时的k值与回归时的值。
3.3 求二叉树叶结点数
二叉树中的叶结点指的是其左右子树都为空树的结点，我们要求一棵二叉树中的叶结点数，肯定是需要遍历整棵二叉树，因此求叶结点数的实现也是有多种方式，这里我们还是介绍层序遍历与递归两种方式。
3.3.1 层序遍历
在对二叉树进行层序遍历时，我们只需要记录每一层中没有左右子树的结点的数量即可，整体实现只需要在层序遍历上进行一些修改，如下所示：
//叶结点数——层序遍历
int LeafSize(BTL T) {
if (!T)
return 0;
LQ Q;//创建队列
InitQueue(&Q);//初始化队列
BTN* p = T;//遍历二叉树的指针
EnQueue(&Q, p);//将根结点入队
int count = 0;//记录叶结点数量的计数器
while (!isEmpty(Q)) {
DeQueue(&Q, &p);//将队头元素出队
if (p->lchild)
EnQueue(&Q, p->lchild);//将左子树入队
if (p->rchild)
EnQueue(&Q, p->rchild);//将右子树入队
if (!p->lchild && !p->rchild)//当左右子树都为空时
count++;//记录叶结点数量
}
return count;
}
通过层序遍历实现起来比较简单，这里我就不再赘述。
3.3.2 分治思想——递归
当我们求叶结点的数量时，我们同样也可以通过分治的思想来进行求解。要求一棵二叉树的叶结点数量，我们可以将其拆分成求其左右子树中的叶结点数量，对应代码如下所示：
//叶结点数——递归
int LeafSize2(BTL T) {
if (!T)
return 0;
if (T->lchild == NULL && T->rchild == NULL)
return 1;
int l = LeafSize2(T->lchild);//递归查找左子树的叶结点数
int r = LeafSize2(T->rchild);//递归查找右子树的叶结点数
return l + r;//返回左右子树叶结点数之和
}
可以看到在该递归算法中，我们通过判断是否为叶结点作为递归的结束标志，当找到叶结点时，我们就将该结点的数量放回给上一层；当未找到叶结点时，则继续向下递进寻找，直到找到所有子树的叶结点。感兴趣的朋友可以自己画一下算法的递归流程，这里我们就不再继续展开赘述。
结语
在今天的内容中，我们详细介绍了二叉树的层次遍历、求二叉树的深度以及求二叉树的结点数。
今天的重点内容主要是对层序遍历算法和分治思想实现的递归算法的应用。不难发现对于求二叉树的结点数的相关操作中，我们都可以采用层序遍历和递归两种算法来实现：
- 层序遍历的算法属于是暴力求解的算法，对于有n个结点的二叉树，算法需要的时间复杂度为 O ( N ) O(N) O(N)；
- 通过分治思想实现的递归算法则是根据二叉树的特性实现的一种快速求解的算法，对于高为h的二叉树，算法所需的最坏时间复杂度为 O ( l o g 2 H ) O(log_2H) O(log2H)；
在学习二叉树的阶段，这两种算法思想是我们必须要掌握的算法思想。相比于层序遍历这种暴力求解的算法，分治思想实现的递归算法要相对复杂难懂一点，因此我建议大家可以多花点时间通过画递归流程图来加深对该算法的理解。
今天的全部内容到这里就结束了，如果大家喜欢博主的内容，可以点赞、收藏加评论支持一下博主，当然也可以转发给身边需要的朋友。在下一篇内容中，我们将会介绍如何通过C语言实现一棵二叉树，大家记得关注哦！！！最后感谢各位朋友的支持，咱们下一篇再见！！！
