【数据结构与算法】详解二叉树下：实践篇————通过链式结构深入理解并实现二叉树
目录
在计算机科学中，二叉树是一种重要的数据结构，它以其独特的结构和性质在数据存储、搜索和算法设计中发挥着重要作用。链式结构作为二叉树的一种常见表示方式，通过节点间的指针连接，实现了对二叉树的高效存储和访问。
一、二叉树前置知识
参考前置文章：二叉树理论篇
二、二叉树链式结构实现的结构定义
二叉树的每个节点包括三个部分：
- 数据部分，这里称为data
- 左指针，指向节点的左孩子，这里称为left指针。如果左孩子为空，则指向NULL
- 右指针，指向节点的右孩子，这里称为right指针。如果右孩子为空，则指向NULL
结构如下图所示：
结构定义如下：
typedef char BTDataType;//数据类型重命名
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;//结构体重命名
三、二叉树的基本实现
🍃创建
因为使用链式结构实现，所以二叉树不需要初始化，只需定义好单个申请节点的函数，每次插入节点调用节点创建函数即可
BTNode* BuyNode(BTDataType x)//申请新节点
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("newnode\n");
exit(1);
}
newnode->data = x;
newnode->left = newnode->right = NULL;
return newnode;
}
二叉树的一般插入意义不大，跟手动插入无异，后面会在搜索二叉树篇章讲解二叉树插入的实现
🍃销毁
递归调用完成销毁，每棵树先释放左孩子和右孩子，再返回去销毁根，因此使用后序遍历的方法最为合适（不需要记录孩子，只需要正常遍历销毁即可）
后序遍历，文章的后面便会介绍，如果不太理解，可以直接点击目录查看遍历部分
调用函数
如果节点为空，直接返回
如果节点非空
- 先调用函数释放左子树
- 再调用函数释放右子树
- 最后释放节点自身
void BinaryTreeDestory(BTNode* root)//后序遍历并销毁
{
if (root== NULL)
return;
BinaryTreeDestory(root->left);//左
BinaryTreeDestory(root->right);//右
free(root);//根
}
四、二叉树的遍历
二叉树的遍历是二叉树的基本操作之一，它指的是按照某种规则访问二叉树中的所有节点，并且每个节点只被访问一次。二叉树的遍历方式有多种，其中最常见的有四种：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）、后序遍历（Post-order Traversal）和层序遍历（Level-order Traversal）。
- 前序遍历（根 左 右）
- 中序遍历（左 根 右）
- 后序遍历（左 右 根)
- 层序遍历（逐层访问）
这里以每次遍历节点打印节点数据为例（指针走到空打印N）
🍃前序遍历
使用递归的方法实现：
- 访问根节点
- 前序遍历左子树
- 前序遍历右子树
接收一个指针（地址）
指针从二叉树的根结点开始遍历
递归的结束条件: 指针指向空，则打印N，return
不满足递归条件，向深处递推:
1. 打印指针指向的节点的数据（相当于访问根节点）
2. 调用函数自己，传递节点左孩子的地址作为参数（相当于访问左子树）
3.调用函数自己，传递节点右孩子的地址作为参数（相当于访问右子树）
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N");
return;
}
printf("%c", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
🍃中序遍历
使用递归的方法实现：
- 中序遍历左子树
- 访问根节点
- 中序遍历右子树
接收一个指针（地址）
指针从二叉树的根结点开始遍历
递归的结束条件:指针指向空，则打印N，return
不满足递归条件，向深处递推:
1. 调用函数自己，传递节点左孩子的地址作为参数（相当于访问左子树）
2.打印本节点的数据（相当于访问根节点）
3.调用函数自己，传递节点右孩子的地址作为参数（相当于访问右子树）
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("N");
return;
}
BinaryTreeInOrder(root->left);
printf("%c", root->data);
BinaryTreeInOrder(root->right);
}
🍃后序遍历
使用递归的方法实现：
- 后序遍历左子树
- 后序遍历右子树
- 访问根节点
接收一个指针（地址）
指针从二叉树的根结点开始遍历
递归的结束条件:指针指向空，则打印N，return
不满足递归条件，向深处递推:
1. 调用函数自己，传递节点左孩子的地址作为参数（相当于访问左子树）
2.调用函数自己，传递节点右孩子的地址作为参数（相当于访问右子树）
3.打印本节点数据（相当于访问根节点）
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c", root->data);
}
🍃层序遍历
层序遍历（Level-order Traversal）
- 从根节点开始，按层次从上到下、从左到右遍历二叉树
通常使用队列（Queue）来实现层序遍历。
如果树不为空，将它的根结点的地址作为数据，入队列
对队列的节点访问:
每次取队首的节点访问，将它的地址记录下来并出队列，同时将它的左右孩子（如果存在的话)入队列
当队列为空时，二叉树的层次遍历完成
层次遍历直接借用了以前已经实现好的队列，详细内容可以参考前置文章
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue queue;
QueueInit(&queue);//队列初始化
if (root)//树的根节点入队列
QueuePush(&queue, root);
while (!QueueEmpty(&queue))//结束条件是队列为空
{
BTNode* tmp = QueueFront(&queue);//取队首元素打印数据并出队列
printf("%c", tmp->data);
QueuePop(&queue);
//左右子树若不为空，入队列
if (tmp->left)
QueuePush(&queue, tmp->left);
if (tmp->right)
QueuePush(&queue, tmp->right);
}
printf("\n");
QueueDestroy(&queue);
}
五、二叉树的扩展功能
🍃求节点个数
两种方式:
方式一:计数器方式
这种方式需要考虑的坑比较多——想要求得树的节点个数就得递归调用，所以用局部变量计数不可行（每次调用都会重置变量），静态局部变量也不可行（一次调用可行，多次调用会将值累加）
全局变量可行，但得在外部每次调用的时候对全局变量置零
指针的方式也可行:实参多传递一个变量的地址，形参用指针接收，多次调用也需要重新创建变量或置零
这两种方式的实现思路:
如果节点为空，返回
否则计数器++
再调用函数对左子树求个数
调用函数对右子树求值
函数不需要返回值，会通过全局变量/指针带出
方式一并不推荐，实现复杂容易出错，所以这里就不给出实现代码了、
方式二: 递归方式（推荐）
- 递归调用相加对于给定的二叉树节点，如果节点为空（NULL），则返回0（表示没有节点）。
- 否则，返回1（表示当前节点本身）加上左子树和右子树的节点数（递归调用）
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
🍃求叶子节点个数
解决方式与求二叉树的节点数量类似，同样使用递归实现，只是细节略有差异:
递归调用:
- 对于给定的二叉树节点，如果节点为空（NULL），则返回0（表示没有节点）。
- 如果节点左右孩子都为空，返回1（表示当前节点为叶子节点）
- 如果上面两个return都没有执行，说明该节点既不为空也不是叶子节点，返回左子树+右子树的叶子节点数（递归调用）
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
🍃求第K层节点个数
实现思路:
用递归的思路将问题分解
假设根结点为第一层，那么对于第一层，要求的是第k层；对于第二层，要求的是第k-1层……逐层分解，对于第k层，求的就是第一层
具体实现逻辑：
- 递归调用函数，参数有两个，分别是节点地址和k
- 如果节点为空，返回0
- 上述判断不成立，再判断如果k==1，返回1
- 如果上述都没有执行，说明节点既不为空，也不是第k层
- 递归调用函数，返回该节点的左孩子的k-1层的节点数+右孩子的k-1层的节点数（如果下一层k==1，则直接返回结果；如果不是，还会继续递归调用）
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)//走到这里，说明节点不为空
return 1;
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
🍃求二叉树的高度
二叉树的高度（或深度）是指从根节点到最远叶子节点的最长路径上的节点数。一个空树的高度定义为0
对于非空二叉树，其高度可以通过递归的方式计算：
- 如果树是空的，那么高度是0。
- 否则，高度是左子树和右子树高度的最大值加1（加1是因为要算上根节点）。
不过这里有一个坑要避免一下:
如果用三目操作符完成return语句，即:return（ root-＞left)＞（root-＞right)？（ root-＞left)+1:（root-＞right)+1
在树比较大时，时间会出现极端的增长
原因是第一次计算的结果没有被记录下来，每次都要重复计算两次，但第一层计算两次，第二层就多计算2*2次，第三层计算2*2*2次，以此类推，将会是一个非常恐怖的计算量
解决方式也很简单:
如果树是空的，那么高度是0。否则，先求得左右孩子的高度记录并记录下来，两个值比较，将较大的值+1返回
//求树的高度
int BinaryHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = BinaryHeight(root->left);
int rightHeight = BinaryHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
🍃查找值为X的节点
实现思路:
递归遍历二叉树，查找值为x的节点
但有一个关键且容易被忽略的点，就是如何在递归调用的过程中，将查找到的节点的地址通过返回值带出来（因为是递归调用，所以必须让函数的第一层带出返回值）
实现方法：
递归调用函数
如果节点为空，返回NULL
上述未执行，再判断节点的值是否为x，如果是的话，返回该节点的地址（注意此处返回只能返回给上一层，不能跳出整个函数）
如果上述都未执行，再进一步判断:
调用函数获取左子树返回的值，如果该值不为空，说明获得了值为x的节点的地址，将该值返回给上一层
如果调用左子树未返回值，再调用函数获取右子树返回的值，如果改值不为空，说明获得了值为x的节点的地址，将该值返回给上一层
上述表达式都未返回结果，说明查不到值为X的节点，返回NULL
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* n1 = BinaryTreeFind(root->left, x);
if (n1)
return n1;
BTNode* n2 = BinaryTreeFind(root->right, x);
if (n2)
return n2;
return NULL;
}
- 点赞
- 收藏
- 关注作者
评论（0）