【数据结构】二叉树链式结构（c语言）（附源码）
ephemerals__ 2024-08-25 13:35:05 阅读 64
🌟🌟作者主页：ephemerals__
🌟🌟所属专栏：数据结构
目录
前言
一、节点的定义
二、创建一棵二叉树
1. 创建新节点
2. 手动创建二叉树
三、方法的声明
四、方法的实现
1. 前、中、后序遍历
1.1 前（先）序遍历
1.2 中序遍历
1.3 后序遍历
2. 层序遍历
3. 二叉树节点个数
4. 叶子节点个数
5. 第K层节点个数
6. 二叉树高度
7. 查找
8. 判断是否为完全二叉树
9. 销毁二叉树
五、程序全部代码
辅助数据结构--队列：
二叉树：
总结
前言
之前我们已经学习了树和二叉树的概念，以及二叉树的顺序实现方式--堆：
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）-CSDN博客
今天我们尝试以链式结构实现二叉树的一些功能（前中后序遍历、层序遍历、统计节点个数和树的高度，以及判断是否为完全二叉树等）。
一、节点的定义
以链式结构实现二叉树，即使用类似链表的方式，将数据存放于一个节点中，该节点的指针域存放指向左孩子和右孩子节点的指针。节点的定义如下：
<code>typedef int BTDataType;
//定义二叉树节点
typedef struct BinaryTreeNode
{
BTDataType data;//存放的数据
struct BinaryTreeNode* leftchild;//指向左孩子的指针
struct BinaryTreeNode* rightchild;//指向右孩子的指针
}BTNode;
二、创建一棵二叉树
由于目前我们所学习的二叉树结构并非是自平衡的，使用固定方法插入数据的意义不大，所以我们就来手动创建一棵二叉树，后续针对这棵二叉树，验证我们实现的方法。
1. 创建新节点
创建新节点的方式与链表相同。注意新节点的两指针都制为空：
//创建新节点
BTNode* BTBuyNode(BTDataType n)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));//申请一个节点的空间
if (newnode == NULL)//内存申请失败，则直接退出程序
{
perror("malloc");
exit(1);
}
newnode->data = n;
newnode->leftchild = newnode->rightchild = NULL;
return newnode;
}
2. 手动创建二叉树
接下来，我们创建一些节点，然后将这些节点连接起来，形成一颗二叉树。
//手动创建二叉树
BTNode* CreateTree()
{
//创建6个节点
BTNode* n1 = BTBuyNode(1);
BTNode* n2 = BTBuyNode(2);
BTNode* n3 = BTBuyNode(3);
BTNode* n4 = BTBuyNode(4);
BTNode* n5 = BTBuyNode(5);
BTNode* n6 = BTBuyNode(6);
//连接节点
n1->leftchild = n2;
n1->rightchild = n3;
n2->leftchild = n4;
n2->rightchild = n5;
n3->rightchild = n6;
//返回根节点
return n1;
}
二叉树已经创建好了，我们画一下它的逻辑结构图：
三、方法的声明
关于二叉树我们要实现的方法声明如下：
<code>//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//层序遍历
void LevelOrder(BTNode* root);
//二叉树节点个数
int BTSize(BTNode* root);
//叶子节点个数
int BTLeafSize(BTNode* root);
//第K层节点个数
int BTLevelKSize(BTNode* root, int k);
//二叉树高度
int BTDepth(BTNode* root);
//查找
BTNode* BTFind(BTNode* root, BTDataType n);
//判断是否为完全二叉树
bool BTComplete(BTNode* root);
//销毁二叉树
void BTDestroy(BTNode** proot);
四、方法的实现
接下来，我们一一介绍并尝试实现这些方法。
1. 前、中、后序遍历
前、中、后序遍历是二叉树最常见、最重要的遍历方式。这三种遍历方式都将二叉树分为三个部分：根节点、左子树、右子树。理解这三种遍历方式，会加深我们对函数递归的理解。接下来我们一一讲解。
1.1 前（先）序遍历
所谓前序遍历，指的是在遍历二叉树时，访问根节点的操作发生在左右子树之前。它的访问顺序是：
根节点-->左子树-->右子树
当访问到每一棵子树时，这棵子树也可以再分为根节点、左子树、右子树，然后继续遵循这一套访问方式。不难发现，这是一个递归的过程。递归结束的条件是访问到空指针，意味着该节点的左子树或右子树不存在。
我们就刚才创建好的那个二叉树，分析一下对其前序遍历的结果：
遍历逻辑看似十分复杂，但是它的代码写起来却非常简单。接下来我们实现前序遍历：
<code>//前序遍历
void PreOrder(BTNode* root)
{
if (root == NULL)//访问到空指针就停止遍历
{
return;
}
printf("%d ", root->data);//打印根节点数据
PreOrder(root->leftchild);//遍历左子树
PreOrder(root->rightchild);//遍历右子树
}
代入测试：
int main()
{
BTNode* root = CreateTree();
PreOrder(root);
return 0;
}
运行结果：
1.2 中序遍历
中序遍历指的是访问根节点的操作发生在左右子树之中。它的遍历顺序是：
左子树-->根节点-->右子树
对于左右子树，它的访问逻辑与前序遍历相同，也是递归的。接下来我们分析中序遍历结果：
当然，它的代码也十分简单：
<code>//中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)//访问到空指针就停止遍历
{
return;
}
InOrder(root->leftchild);//遍历左子树
printf("%d ", root->data);//打印根节点数据
InOrder(root->rightchild);//遍历右子树
}
测试结果：
1.3 后序遍历
后序遍历的含义是访问根节点的操作发生在其左右子树之后。它的遍历顺序是：
左子树-->右子树-->根节点
它的递归遍历逻辑不言而喻。遍历分析如下：
代码一如既往的简单：
<code>//后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
PostOrder(root->leftchild);//遍历左子树
PostOrder(root->rightchild);//遍历右子树
printf("%d ", root->data);//打印根节点数据
}
测试结果：
2. 层序遍历
所谓层序遍历，通俗地讲，就是从上到下，从左到右逐层遍历。对于我们创建的二叉树，它的遍历结果应该是：1，2，3，4，5，6。
进行层序遍历操作，需要借助数据结构“队列”来实现。关于队列，在博主的另一篇文章中有所实现：
【数据结构】栈和队列（c语言实现）（附源码）-CSDN博客
在实现层序遍历时，队列相关函数我们就直接调用了，不再重复实现（注意将队列的数据元素类型调整为二叉树的节点指针类型）。接下来讲讲层序遍历的方法：
1.首先将头节点存放于队列当中。
2.如果队列不为空，则读取一个节点的数据，并让该节点出队。
3.读取一个节点的数据之后，若该节点有左子节点，则将左子节点入队；有右子节点，则将右子节点入队。
4.重复第2步，直到队列为空为止。
我们画图表示一下遍历过程：
不难发现，从上到下出队的数据依次排成了1，2，3，4，5，6。接下来，我们尝试写代码实现该过程：
<code>//层序遍历
void LevelOrder(BTNode* root)
{
Queue q;//创建队列
QInit(&q);//初始化队列
QPush(&q, root);//根节点入队
while (!QEmpty(&q))//队列不为空，进入循环
{
BTNode* front = QFront(&q);//记录队头数据
printf("%d ", front->data);//读数据
QPop(&q);//出队
if (front->leftchild != NULL)
{
QPush(&q, front->leftchild);//若左孩子不为空，则左孩子入队
}
if (front->rightchild != NULL)
{
QPush(&q, front->rightchild);//若右孩子不为空，则右孩子入队
}
}
QDestroy(&q);//销毁队列
}
测试结果：
3. 二叉树节点个数
接下来，我们写一个函数统计二叉树节点个数。它的实现方法十分简单，当一个节点有效时，返回1，之后递归判断该节点的左右孩子是否有效......最后将这些“1”相加即可。代码如下：
int BTSize(BTNode* root)
{
if (root == NULL)//访问到空指针，则结束
{
return 0;
}
return 1 + BTSize(root->leftchild) + BTSize(root->rightchild);//节点有效，返回1，再与左右孩子的判断结果相加
}
递归示意图：
测试结果：
4. 叶子节点个数
在统计叶子节点时，需要注意：叶子节点是度为0的节点。所以我们在做节点判断时，要判断该节点的左右孩子是否为空。如果都为空，则它是一个叶子节点。实现代码如下：
int BTLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->leftchild == NULL && root->rightchild == NULL)//满足叶子节点的条件，返回1
{
return 1;
}
return BTLeafSize(root->leftchild) + BTLeafSize(root->rightchild);//将左子树和右子树统计结果相加
}
递归示意图：
测试结果：
5. 第K层节点个数
在统计第K层节点的个数时，我们不仅需要判断节点的有效性，而且需要确定该节点所在的层数。至于层数该怎么确定呢？
首先来看一段代码：
<code>int main()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
int k = 5;
int i = 0;
while (k != 1)
{
k--;
i++;
}
printf("%d\n", arr[i]);
return 0;
}
运行结果：
在这里，我们使用了一种特殊的方式访问数组中的第五个元素。我们循环使k自减，当k的值为1时，下标 i 就走到了第五个元素的位置处。而对于二叉树第k层节点的统计，也是这个原理。在使用递归时，每次遍历下一层（左右孩子）并传入k-1这个值，当k值为1时，再做统计，就实现了统计第k层节点的功能。代码实现：
int BTLevelKSize(BTNode* root, int k)
{
if (root == NULL)//访问到空，返回0
{
return 0;
}
if (k == 1)//k值为1，做统计
{
return 1;
}
return BTLevelKSize(root->leftchild, k - 1) + BTLevelKSize(root->rightchild, k - 1);//递归访问左右孩子（下一层）
}
递归示意图：
测试代码与结果：
<code>int main()
{
BTNode* root = CreateTree();
int k = 0;
scanf("%d", &k);
printf("第%d层节点个数为：%d\n", k, BTLevelKSize(root, k));
}
6. 二叉树高度
二叉树的高度计算原理十分简单，和之前节点个数的统计相似，当访问了一个有效节点之后，说明层数至少为1。之后再去访问它的左子树和右子树是否有效...这里需要注意：有时候二叉树的左子树和右子树高度不相同，需要将最高的那棵子树计入到高度当中。
代码实现：
<code>//二叉树高度
int BTDepth(BTNode* root)
{
if (root == NULL)//根节点为空则为0层
{
return 0;
}
int leftDepth = BTDepth(root->leftchild);//统计左子树高度
int rightDepth = BTDepth(root->rightchild);//统计右子树高度
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//统计左右子树最大高度，再与根节点层数相加
}
递归示意图：
测试结果：
7. 查找
查找的思路也比较简单，只需要遍历根节点、左子树、右子树，若找到相应的值，则将该节点返回即可。代码如下：
<code>//查找
BTNode* BTFind(BTNode* root, BTDataType n)
{
if (root == NULL)//访问到空则停止
{
return NULL;
}
if (root->data == n)//找到了，返回该节点
{
return root;
}
BTNode* leftFind = BTFind(root->leftchild, n);//遍历左子树
if (leftFind != NULL)//若查找结果不是空，则说明找到了，将该节点带回
{
return leftFind;
}
BTNode* rightFind = BTFind(root->rightchild, n);//遍历右子树
if (rightFind != NULL)//若查找结果不是空，则说明找到了，将该节点带回
{
return rightFind;
}
}
测试代码及结果：
int main()
{
BTNode* root = CreateTree();
int x = 0;
while (1)
{
scanf("%d", &x);
if (BTFind(root, x) != NULL)
{
printf("找到了\n");
}
else
{
printf("找不到\n");
}
printf("\n");
}
}
8. 判断是否为完全二叉树
我们在进行层序遍历二叉树时，是按照从上到下，从左到右的顺序进行的。由于完全二叉树最后一层的节点需要从左到右依次排列，我们就可以对这棵二叉树进行层序遍历。
如果遍历结果当中有两个节点之间有空指针，就说明这两个节点不是从左到右依次排列的，这棵二叉树也就不是完全二叉树了；反之，如果节点之间没有空指针，则说明它就是一棵完全二叉树。这里需要注意：由于要判断空指针的存在，遍历时就需要将空指针也存入队列。
我们针对创建好的二叉树，画个图演示一下执行流程：
代码实现：
<code>//判断是否为完全二叉树
bool BTComplete(BTNode* root)
{
Queue q;
QInit(&q);//初始化队列
QPush(&q, root);//根节点入队
while (!QEmpty(&q))//队列不为空进入循环
{
BTNode* front = QFront(&q);//记录队头
QPop(&q);//队头出队
if (front == NULL)//当读取到空指针时，跳出循环
{
break;
}
QPush(&q, front->leftchild);//左孩子入队
QPush(&q, front->rightchild);//右孩子入队
}
//此时，再次循环读取队头数据，若读取到非空节点，说明不是完全二叉树
while (!QEmpty(&q))
{
BTNode* front = QFront(&q);//记录队头
QPop(&q);//队头出队
if (front != NULL)
{
//出现非空节点
QDestroy(&q);//销毁队列
return false;
}
}
//读完了所有的空指针，还没有遇到非空节点，说明是完全二叉树
QDestroy(&q);//销毁队列
return true;
}
测试代码与结果：
int main()
{
BTNode* root = CreateTree();
if (BTComplete(root))
{
printf("是完全二叉树\n");
}
else
{
printf("不是完全二叉树\n");
}
}
9. 销毁二叉树
完成了这么多的工作之后，我们就要销毁这棵二叉树了。销毁二叉树的过程与后序遍历相似，先将左右子树销毁，然后销毁根节点。由于这里会改变根节点的值，所以需要传入二级指针。
代码如下：
<code>//销毁二叉树
void BTDestroy(BTNode** proot)
{
if (*proot == NULL)//访问到空指针则回退
{
return;
}
BTDestroy(&((*proot)->leftchild));//销毁左子树（leftchild是一级指针，函数接收二级指针所以要取地址）
BTDestroy(&((*proot)->rightchild));//销毁右子树（rightchild是一级指针，函数接收二级指针所以要取地址）
free(*(proot));//销毁根节点
*proot = NULL;
}
五、程序全部代码
辅助数据结构--队列：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef BTNode* QDataType;
//定义队列
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//初始化
void QInit(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//入队列
void QPush(Queue* pq, QDataType n);
//出队列
void QPop(Queue* pq);
//取队头数据
QDataType QFront(Queue* pq);
//取队尾数据
QDataType QBack(Queue* pq);
//获取队列有效元素个数
int QSize(Queue* pq);
//销毁
void QDestroy(Queue* pq);
//初始化
void QInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//判空
bool QEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL && pq->ptail == NULL;
}
//入队列
void QPush(Queue* pq, QDataType n)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = n;
newnode->next = NULL;
if (QEmpty(pq))
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
pq->size++;
}
//出队列
void QPop(Queue* pq)
{
assert(pq && !QEmpty(pq));
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
//取队头数据
QDataType QFront(Queue* pq)
{
assert(pq && !QEmpty(pq));
return pq->phead->data;
}
//取队尾数据
QDataType QBack(Queue* pq)
{
assert(pq && !QEmpty(pq));
return pq->ptail->data;
}
//获取队列有效元素个数
int QSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//销毁
void QDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
二叉树：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int BTDataType;
//定义二叉树节点
typedef struct BinaryTreeNode
{
BTDataType data;//存放的数据
struct BinaryTreeNode* leftchild;//指向左孩子的指针
struct BinaryTreeNode* rightchild;//指向右孩子的指针
}BTNode;
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//层序遍历
void LevelOrder(BTNode* root);
//二叉树节点个数
int BTSize(BTNode* root);
//叶子节点个数
int BTLeafSize(BTNode* root);
//第K层节点个数
int BTLevelKSize(BTNode* root, int k);
//二叉树高度
int BTDepth(BTNode* root);
//查找
BTNode* BTFind(BTNode* root, BTDataType n);
//判断是否为完全二叉树
bool BTComplete(BTNode* root);
//销毁二叉树
void BTDestroy(BTNode** proot);
//创建新节点
BTNode* BTBuyNode(BTDataType n)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));//申请一个节点的空间
if (newnode == NULL)//内存申请失败，则直接退出程序
{
perror("malloc");
exit(1);
}
newnode->data = n;
newnode->leftchild = newnode->rightchild = NULL;
return newnode;
}
//手动创建二叉树
BTNode* CreateTree()
{
//创建6个节点
BTNode* n1 = BTBuyNode(1);
BTNode* n2 = BTBuyNode(2);
BTNode* n3 = BTBuyNode(3);
BTNode* n4 = BTBuyNode(4);
BTNode* n5 = BTBuyNode(5);
BTNode* n6 = BTBuyNode(6);
//连接节点
n1->leftchild = n2;
n1->rightchild = n3;
n2->leftchild = n4;
n2->rightchild = n5;
n3->rightchild = n6;
//返回根节点
return n1;
}
//前序遍历
void PreOrder(BTNode* root)
{
if (root == NULL)//访问到空指针就停止遍历
{
return;
}
printf("%d ", root->data);//打印根节点数据
PreOrder(root->leftchild);//遍历左子树
PreOrder(root->rightchild);//遍历右子树
}
//中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)//访问到空指针就停止遍历
{
return;
}
InOrder(root->leftchild);//遍历左子树
printf("%d ", root->data);//打印根节点数据
InOrder(root->rightchild);//遍历右子树
}
//后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
PostOrder(root->leftchild);//遍历左子树
PostOrder(root->rightchild);//遍历右子树
printf("%d ", root->data);//打印根节点数据
}
//层序遍历
void LevelOrder(BTNode* root)
{
Queue q;//创建队列
QInit(&q);//初始化队列
QPush(&q, root);//根节点入队
while (!QEmpty(&q))//队列不为空，进入循环
{
BTNode* front = QFront(&q);//记录队头数据
printf("%d ", front->data);//读数据
QPop(&q);//出队
if (front->leftchild != NULL)
{
QPush(&q, front->leftchild);//若左孩子不为空，则左孩子入队
}
if (front->rightchild != NULL)
{
QPush(&q, front->rightchild);//若右孩子不为空，则右孩子入队
}
}
QDestroy(&q);//销毁队列
}
//二叉树节点个数
int BTSize(BTNode* root)
{
if (root == NULL)//访问到空指针，则结束
{
return 0;
}
return 1 + BTSize(root->leftchild) + BTSize(root->rightchild);//节点有效，返回1，再与左右孩子的判断结果相加
}
//叶子节点个数
int BTLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->leftchild == NULL && root->rightchild == NULL)//满足叶子节点的条件，返回1
{
return 1;
}
return BTLeafSize(root->leftchild) + BTLeafSize(root->rightchild);//将左子树和右子树统计结果相加
}
//第K层节点个数
int BTLevelKSize(BTNode* root, int k)
{
if (root == NULL)//访问到空，返回0
{
return 0;
}
if (k == 1)//k值为1，做统计
{
return 1;
}
return BTLevelKSize(root->leftchild, k - 1) + BTLevelKSize(root->rightchild, k - 1);//递归访问左右孩子（下一层）
}
//二叉树高度
int BTDepth(BTNode* root)
{
if (root == NULL)//根节点为空则为0层
{
return 0;
}
int leftDepth = BTDepth(root->leftchild);//统计左子树高度
int rightDepth = BTDepth(root->rightchild);//统计右子树高度
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//统计左右子树最大高度，再与根节点层数相加
}
//查找
BTNode* BTFind(BTNode* root, BTDataType n)
{
if (root == NULL)//访问到空则停止
{
return NULL;
}
if (root->data == n)//找到了，返回该节点
{
return root;
}
BTNode* leftFind = BTFind(root->leftchild, n);//遍历左子树
if (leftFind != NULL)//若查找结果不是空，则说明找到了，将该节点带回
{
return leftFind;
}
BTNode* rightFind = BTFind(root->rightchild, n);//遍历右子树
if (rightFind != NULL)//若查找结果不是空，则说明找到了，将该节点带回
{
return rightFind;
}
}
//判断是否为完全二叉树
bool BTComplete(BTNode* root)
{
Queue q;
QInit(&q);//初始化队列
QPush(&q, root);//根节点入队
while (!QEmpty(&q))//队列不为空进入循环
{
BTNode* front = QFront(&q);//记录队头
QPop(&q);//队头出队
if (front == NULL)//当读取到空指针时，跳出循环
{
break;
}
QPush(&q, front->leftchild);//左孩子入队
QPush(&q, front->rightchild);//右孩子入队
}
//此时，再次循环读取队头数据，若读取到非空节点，说明不是完全二叉树
while (!QEmpty(&q))
{
BTNode* front = QFront(&q);//记录队头
QPop(&q);//队头出队
if (front != NULL)
{
//出现非空节点
QDestroy(&q);//销毁队列
return false;
}
}
//读完了所有的空指针，还没有遇到非空节点，说明是完全二叉树
QDestroy(&q);//销毁队列
return true;
}
//销毁二叉树
void BTDestroy(BTNode** proot)
{
if (*proot == NULL)//访问到空指针则回退
{
return;
}
BTDestroy(&((*proot)->leftchild));//销毁左子树（leftchild是一级指针，函数接收二级指针所以要取地址）
BTDestroy(&((*proot)->rightchild));//销毁右子树（rightchild是一级指针，函数接收二级指针所以要取地址）
free(*(proot));//销毁根节点
*proot = NULL;
}
总结
今天，我们学习了二叉树链式结构相关功能的实现，如遍历、统计节点个数、查找、销毁等。这些功能的实现加深了我们对递归的理解，并且让我们学会了使用数据结构作为辅助来解决问题。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。