【数据结构】二叉树链式结构——感受递归的暴力美学

🕗 发布于 2024-07-27 12:00 数据结构 算法

前言：

在上篇文章【数据结构】二叉树——顺序结构——堆及其实现中，实现了二叉树的顺序结构，使用堆来实现了二叉树这样一个数据结构；现在就来实现而二叉树的链式结构。

一、链式结构

链式结构，使用链表来表示一颗二叉树，即用链来指示二叉树中元素的逻辑关系。通常的就是链表中每个节点右三个域组成，数据域和左右指针域，左右指针分别指向该节点的左孩子节点和右孩子节点的存储地址。

链式结构分为二叉链和三叉链（三叉链比而二叉链多一个指向父节点的指针域）。

这里使用二叉链来实现。

二、二叉树链式结构实现相关功能

在实现之前，先来看一下，具体要实现哪些功能？

首先就是二叉树的结构，我们使用链表来实现，链表的每一个节点都由数值域和左右指针域组成。

二叉树链式结构的节点

typedef int TreeDataType;
typedef struct TreeNode
{
TreeDataType data;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;

二叉树链式结构如上，接下来再来看一下二叉树链式结构实现的相关功能：

//二叉树的前序排序
int PreOrder(TreeNode* root);
//二叉树的中序排序
int InOrder(TreeNode* root);
//二叉树的后序遍历
int AfterOrter(TreeNode* root);
//二叉树节点个数
int BinaryTreeSize(TreeNode* root);
//二叉树叶子节点个数
int BinaryTreeLeafSize(TreeNode* root);
//二叉树第k层节点个数
int BinaryTreeLevelKSize(TreeNode* root, int k);
//二叉树的深度
int BinaryTreeDepth(TreeNode* root);
//查找二叉树值为x的节点
TreeNode* BinaryTreeFind(TreeNode* root, TreeDataType x);
//层序遍历
void LevelOrder(BTNode* root)
//判断是否为满二叉树
bool BinaryTreeComplete(BTNode* root)
//二叉树的销毁
void TreeDesTroy(TreeNode** root);

2.1、二叉树前、中、后序遍历

这里，前序、中序和后序遍历什么意思呢，

说白了，这三种遍历其实就是以对二叉树访问的顺序，来遍历二叉树

这里以前序遍历为例，遍历二叉树

现在有一个这样的二叉树，用前序遍历来访问这颗二叉树（这里访问并输出访问到的数据）

首先访问根节点，输出访问到的数据 1 ；再访问左子树

再访问其左子树的根节点，输出访问到的数据 2 ；再接着访问左子树

再访问其左子树的根节点，输出访问到的数据 4 ；再接着访问左子树

此时访问到了空节点，就直接回退，回退到其父节点的函数栈帧，访问父节点的右子树

访问4这个节点的右子树，也为空，此时节4这个点为根节点的左子树已经访问结束了，回退到其父节点的函数栈帧，访问其父节点的右子树

访问2这个节点的右子树，先输出右子树的根节点数据 5 ；再访问根节点5的左子树

这里节点5的左右节点都为空，这里省略一些过程；此时5这个节点访问结束，回退到2这个节点，而2这个节点右子树访问结束，也已经访问结束了；此时再回退到根节点，访问根节点的右子树。

此时访问根节点的右子树的根节点，输出访问到的数据 3 ；再接着访问3这个节点的左子树

这里，3这个节点的左右节点都为空，访问就直接返回，回退到根节点，就说明根节点的右子树访问已经结束，此时二叉树已经变了结束。

这里前序遍历的输出结果为 1 2 4 5 3

这三个前、中、后序遍历本质上没啥差别，这里直接看实现代码

//二叉树的前序排序
void PreOrder(TreeNode* root)
{
if (root == NULL)
{
return;
}
//输出数据
printf("%d ", root->data);
//遍历左子树
PreOrder(root->left);
//遍历右子树
PreOrder(root->right);
}
//二叉树的中序排序
void InOrder(TreeNode* root)
{
if (root == NULL)
{
return;
}
//遍历左子树
InOrder(root->left);
//输出数据
printf("%d ", root->data);
//遍历右子树
InOrder(root->right);
}
//二叉树的后序遍历
void AfterOrter(TreeNode* root)
{
if (root == NULL)
{
return;
}
//遍历左子树
AfterOrter(root->left);
//遍历右子树
AfterOrter(root->right);
//输出数据
printf("%d ", root->data);
}

这里我们来测试代码对不对，我们先创建一个二叉树，然后看输出结果是否正确、

TreeNode* BuyNode(TreeDataType x)
{
TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = x;
newnode->left = newnode->right = NULL;
return newnode;
}

void test()
{
TreeNode* node1 = BuyNode(1);
TreeNode* node2 = BuyNode(2);
TreeNode* node3 = BuyNode(3);
TreeNode* node4 = BuyNode(4);
TreeNode* node5 = BuyNode(5);
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;

//前序遍历
PreOrder(node1);
printf("\n");
//中序遍历
InOrder(node1);
printf("\n");
//后序遍历
AfterOrter(node1);
printf("\n");
}
int main()
{
test();
return 0;
}

这里代码没有问题。

2.2、二叉树节点个数

这里，二叉树的链式结构我们是使用递归来实现的，那我们该如何去计算二叉树的节点个数呢？

思路：
遍历二叉树，遍历到空节点就返回0，不是空节点就返回其左子树和右子树节点个数之和再加一

代码如下：

//二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

2.3、二叉树叶子结点个数

所谓叶子节点：就是左右子节点都为空的节点，我们就利用这个特点来判断

思路：

遍历二叉树，遍历到空节点就返回空；遍历到节点的左右节点都为空，返回1；否则就返回节点的左子树和右子树的叶子结点之和。

代码如下：

//二叉树叶子节点个数
int BinaryTreeLeafSize(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

2.4、二叉树第k层节点个数

求二叉树第k层节点的个数，我们先来看这样的一个图

通过图我们可以看到，每次向下遍历一层，k-1；当k=1时，正好是第k层

思路：

遍历二叉树，遍历到空节点就返回 0 ；遍历到k=1时，就返回1；否则就返回该节点左子树和右子树中第k - 1层的节点个数。

这里需要注意，要在判断k=1之前判断节点是否为空。

代码如下：

//二叉树第k层节点个数
int BinaryTreeLevelKSize(TreeNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + 
           BinaryTreeLevelKSize(root->right, k - 1);
}

2.5、二叉树的深度

求二叉树的深度，我们这里是将二叉树的左子树和右子树分开依次遍历的，显然我们不能像上面一样，返回遍历左子树和右子树的和；这里就返回其中最大的。

思路：

遍历二叉树，遍历到空节点就返回空；定义两个值，记录其节点左子树和右子树的深度再加一；返回其中最大的即可。

理解：这里定义两个值记录其左右子树的深度加一（加一就是记录当前这一层）。

代码如下：

//二叉树的深度
int BinaryTreeDepth(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
int depth_left = BinaryTreeDepth(root->left) + 1;
int depth_right = BinaryTreeDepth(root->right) + 1;
return (depth_left > depth_right) ? depth_left : depth_right;
}

2.6、查找二叉树中值为 x 的节点

查找相对来说就比较简单了，遍历二叉树，为空就返回NULL，值为x就返回该节点的地址，如果遍历过程中函数返回值不为NULL，就证明找到了，直接返回即可。

思路：

遍历二叉树，遍历到空节点就返回NULL；判断节点的值是否为x，是就返回该节点的地址；不是。就创建指针变量接受其左右子树遍历的结果，如果不为NULL就直接返回该返回值。为空则继续遍历。

代码如下：

//查找二叉树值为x的节点
TreeNode* BinaryTreeFind(TreeNode* root, TreeDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
TreeNode* pleft = BinaryTreeFind(root->left, x);
if (pleft)
return pleft;
TreeNode* pright = BinaryTreeFind(root->right, x);
if (pright)
return pright;
return NULL;
}

到这里，来看一下这些代码是否正确

对于这样的一个二叉树，代码输出结果都正确。

2.7、层序遍历

这里层序遍历，我们需要借用队列这样一个数据结构（前面有详细讲解），

大致思路如此：

将根节点数据放入队列中；然后出队列，并且把该节点的左右子节点插入到队列当中。

将1这个节点出队列，再把左右子节点插入到队列当中

再出队头节点，将其左右子节点插入队列当中

依次类推，当队头数据左右子节点为空，就不进插入队列这一操作。

代码如下：

这里用到了对列相关代码，详细代码在上篇

//层序遍历
//借助数据结构---队列
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取队头，打印
BTNode* front = QueueFront(&q);
printf("%d ", front->data);
QueuePop(&q);
//队头节点的左右孩子入队列
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
//队列为空
QueueDestroy(&q);
}

2.8、判断二叉树是否为满二叉树

判断二叉树是否为满二叉树，还是借用队列这样的数据结构，和层序遍历有相似之处；与层序遍历不同的是，这里，即便左右子节点为空，有进行入队列操作；当队头数据为空，就判断队列剩余数据是否都为空，如果都为空，就证明二叉树为满二叉树；否则就不是满二叉树。

代码如下：

//判断二叉树是否为完全二叉树
//---队列
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
//队列不一定为空
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}

2.9、二叉树的销毁

这里为了测试这些代码，就手动创建了一个二叉树，这些都是动态开辟的空间，养成好习惯，手动释放动态开辟的空间。

这里需要注意的是：使用后序遍历，先是否底层的节点，

代码如下：

// 二叉树销毁
void BinaryTreeDesTroy(TreeNode** root)
{
if (*root == NULL)
{
return;
}
BinaryTreeDesTroy(&((*root)->left));
BinaryTreeDesTroy(&((*root)->right));

free(*root);
*root = NULL;
}

感谢各位大佬支持并指出问题，

如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！

原文地址：https://blog.csdn.net/LH__1314/article/details/140674131

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【JVM基础08】——类加载器-说一下类加载的执行过程？
下一篇：YOLO v8目标检测（一）—网络模型与构建

linux线程cp模型，posix信号量，线程池，线程封装，单例模型，懒汉饿汉实现方式，自旋锁，读者写者模型
前面的同步，我们并没有一个很好的场景来模拟同步，只是简单的将有序的现象输出出来；现在我们来讲解一个比较合理且常见的模型——生产者消费者模型；
阅读更多2024-09-07
Qt/C++开源项目 TCP服务器调试助手（源码分享+发布链接下载）
该TCP服务器调试助手是用于测试和监控基于TCP协议的网络通信工具，能够帮助开发者便捷地进行网络通信调试。通过简洁的界面设计，用户可以轻松配置、管理TCP端口的连接，收发消息并进行数据监控分析。123
阅读更多2024-09-07
vue3整合antv x6实现图编辑器快速入门
例如：在上面节点基础上，我们有一个新的需求：给节点加上右键菜单。X6 支持使用 SVG、HTML 来渲染节点内容，在此基础上，我们还可以使用 React、Vue 组件来渲染节点，这样在开发过程中会非常
阅读更多2024-09-07
linux使用samba共享目录，其他虚拟机和windows都可以访问
linux使用samba共享目录，其他虚拟机和windows都可以访问
阅读更多2024-09-07
Linux系统编程实现ls -l | wc -l指令
由于该指令是通过管道的形式实现的，所以我们要使用系统函数pipe。ls -l |wc -l的作用就是统计当前目录有多少文件。由于父子间通过管道实现，所以存在读写阻塞问题，不用担心僵尸进程的产生，所以可
阅读更多2024-09-07
MySQL表操作及约束
MySQL表操作及约束
阅读更多2024-09-07
1.2CubeMAX创建FREERTOS入门示例
内核参数设置，用户根据自己的实际应用来裁剪定制。：相关宏的定义，可以自建一些常量在工程中使用。User Constants（用户常量）：定时器和信号量的创建。：用于查看堆使用情况。：任务与队列
阅读更多2024-09-07
YOLOv9改进策略【注意力机制篇】| PSA极化自我关注：实现高质量像素回归
本文记录的是基于PSA注意力模块的YOLOv9目标检测方法研究。PSA模块。本文将其应用到YOLOv9的检测任务中，使模型能够更好地捕捉图像中的细节信息，以实现目标检测任务中准确识别和定位。
阅读更多2024-09-07
爆改YOLOv8|利用yolov10的SCDown改进yolov8-下采样
yolov8改进，yolov10, 下采样SCDown, 即插即用
阅读更多2024-09-07
PDF样本图册转换为一个链接，随时打开无需印刷
想象一下，您手中有一本厚重的样本图册，里面包含了丰富多样的内容，如产品介绍、项目方案、学术论文等。在过去，您需要逐一翻阅、筛选，甚至为了便于查看，不得不将其印刷出来。如今，借助先进的数字化技术，还能实
阅读更多2024-09-07

【数据结构】二叉树链式结构——感受递归的暴力美学

前言：

一、链式结构

二、二叉树链式结构实现相关功能

二叉树链式结构的节点

2.1、二叉树前、中、后序遍历

2.2、二叉树节点个数

2.3、二叉树叶子结点个数

2.4、二叉树第k层节点个数

2.5、二叉树的深度

2.6、查找二叉树中值为 x 的节点

2.7、层序遍历

2.8、判断二叉树是否为满二叉树

2.9、二叉树的销毁

相关文章