探秘二叉树：高效操作与遍历技巧大揭秘
探秘二叉树：高效操作与遍历技巧大揭秘
凤年徐
发布于 2025-08-28 13:42:15
发布于 2025-08-28 13:42:15
代码可运行
运行总次数：0
代码可运行
探秘二叉树：高效操作与遍历技巧大揭秘
前言
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二 叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树 操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
二叉树结构创建
// 定义二叉树节点存储的数据类型
typedef int BTDataType;
// 二叉树节点结构体
typedef struct BinaryTreeNode
{
BTDataType data; // 节点存储的数据
struct BinaryTreeNode* left; // 指向左子节点的指针
struct BinaryTreeNode* right; // 指向右子节点的指针
} BTNode;
// 创建新节点辅助函数
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if(node == NULL) {
perror("malloc fail");
exit(EXIT_FAILURE);
}
node->data = x; // 设置节点数据
node->left = NULL; // 初始化左子节点为空
node->right = NULL;// 初始化右子节点为空
return node;
}typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 创建新节点辅助函数
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if(node == NULL) {
perror("malloc fail");
exit(EXIT_FAILURE);
}
node->data = x; // 设置节点数据
node->left = NULL; // 初始化左子节点为空
node->right = NULL;// 初始化右子节点为空
return node;
}
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}手动创建二叉树
// 手动创建二叉树的示例函数
BTNode* CreatBinaryTree()
{
// 创建6个节点
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
// 构建树结构
node1->left = node2; // 1的左子节点是2
node1->right = node4; // 1的右子节点是4
node2->left = node3; // 2的左子节点是3
node4->left = node5; // 4的左子节点是5
node4->right = node6; // 4的右子节点是6
return node1; // 返回根节点
}注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。 再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：
1.空树
2.非空：根结点，根结点的左子树、根结点的右子树组成的。
在这里插入图片描述
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
二叉树的遍历
前序、中序以及后序遍历 学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉 树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历 是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
在这里插入图片描述
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
- 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 由于被访问的结点必是某子树的根，所以**N(Node）、L(Left subtree）和R(Right subtree）**又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
在这里插入图片描述
拿前序来解释一下：1跟(2 3 N N N)以及(4 5 N N 6 N N)组成 根 左子树 右子树 结构
同时2跟(3 N N)以及(N )也组成这样的结构 最后3和N以及N组成一个这样的结构
同样4跟(5 N N)以及(6 N N)也组成这样的结构
遍历类型 | 访问顺序 | 应用场景 |
|---|---|---|
前序遍历 | 根节点 → 左子树 → 右子树 | 复制树结构、前缀表达式 |
中序遍历 | 左子树 → 根节点 → 右子树 | 二叉搜索树有序输出 |
后序遍历 | 左子树 → 右子树 → 根节点 | 释放树内存、后缀表达式计算 |
1.前序遍历
// 前序遍历二叉树
void PrevOrder(BTNode* root)
{
// 遇到空节点打印'N'表示空
if(root == NULL)
{
printf("N ");
return;
}
// 1. 先访问当前节点（根节点）
printf("%d ", root->data);
// 2. 递归遍历左子树
PrevOrder(root->left);
// 3. 递归遍历右子树
PrevOrder(root->right);
}示例输出：1 2 3 N N N 4 5 N N 6 N N
2.中序遍历（Inorder Traversal）
// 中序遍历二叉树
void InOrder(BTNode* root)
{
if(root == NULL)
{
printf("N ");
return;
}
// 1. 递归遍历左子树
InOrder(root->left);
// 2. 访问当前节点（根节点）
printf("%d ", root->data);
// 3. 递归遍历右子树
InOrder(root->right);
}示例输出：N 3 N 2 N 1 N 5 N 4 N 6 N
3. 后序遍历（Postorder Traversal）
// 后序遍历二叉树
void PostOrder(BTNode* root)
{
if(root == NULL)
{
printf("N ");
return;
}
// 1. 递归遍历左子树
PostOrder(root->left);
// 2. 递归遍历右子树
PostOrder(root->right);
// 3. 访问当前节点（根节点）
printf("%d ", root->data);
}示例输出：N N 3 N 2 N N 5 N N 6 4 1
二叉树基本操作
1. 计算叶子节点个数
叶子节点：没有子节点的节点
// 计算二叉树的叶子节点数量
int TreeLeafSize(BTNode* root)
{
// 空树没有叶子节点
if(root == NULL)
return 0;
// 当前节点是叶子节点（无左右子节点）
if(root->left == NULL && root->right == NULL)
return 1;
// 递归计算左右子树的叶子节点数之和
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}示例输出：上述二叉树有3个叶子节点（节点3、5、6）
2. 计算二叉树高度
树的高度：从根节点到最深叶子节点的最长路径长度
// 计算二叉树的高度
int TreeHeight(BTNode* root)
{
// 空树高度为0
if(root == NULL)
return 0;
// 递归计算左子树高度
int leftHeight = TreeHeight(root->left);
// 递归计算右子树高度
int rightHeight = TreeHeight(root->right);
// 返回较高的子树高度+1（当前节点高度）
return leftHeight > rightHeight ?
leftHeight + 1 :
rightHeight + 1;
}示例输出：上述二叉树高度为3
3. 查找指定值节点
// 在二叉树中查找值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
// 空树或查找结束
if(root == NULL)
return NULL;
// 当前节点值匹配
if(root->data == x)
return root;
// 在左子树中递归查找
BTNode* ret1 = TreeFind(root->left, x);
if(ret1 != NULL) // 左子树找到
return ret1;
// 在右子树中递归查找
BTNode* ret2 = TreeFind(root->right, x);
if(ret2 != NULL) // 右子树找到
return ret2;
// 整棵树未找到
return NULL;
}4. 计算节点总数
// 计算二叉树的节点总数
int TreeNodeCount(BTNode* root)
{
// 递归终止条件：空节点
if(root == NULL)
return 0;
// 当前节点 + 左子树节点数 + 右子树节点数
return 1 + TreeNodeCount(root->left)
+ TreeNodeCount(root->right);
}5. 销毁二叉树（后序遍历）
// 销毁二叉树（后序遍历方式）
void TreeDestroy(BTNode* root)
{
if(root == NULL)
return;
// 递归释放左子树
TreeDestroy(root->left);
// 递归释放右子树
TreeDestroy(root->right);
// 释放当前节点
free(root);
}二叉树可视化表示
Level 1: [1]
/ \
Level 2: [2] [4]
/ / \
Level 3: [3] [5] [6]前序： 1 → 2 → 3 → 4 → 5 → 6
中序： 3 → 2 → 1 → 5 → 4 → 6
后序： 3 → 2 → 5 → 6 → 4 → 1总结与要点
- 递归本质：二叉树操作大多基于递归实现，因其自然契合"根-左子树-右子树"的结构定义
- 遍历基础：前/中/后序遍历是其他操作的基础，时间复杂度均为O(n)
- 内存管理：
- 创建节点后需初始化指针为NULL
- 销毁树应使用后序遍历避免野指针
- 应用场景：
- 前序遍历：表达式前缀表示、复制树结构
- 中序遍历：二叉搜索树有序输出
- 后序遍历：内存释放、表达式计算
- 效率考量：
- 空间复杂度：递归调用栈深度=树高度（最坏情况O(n)）
- 平衡二叉树可优化操作效率至O(log n)
进阶学习方向：
- 非递归遍历实现（使用栈模拟递归）
- 层序遍历实现（使用队列）
- 根据遍历序列重建二叉树
- 平衡二叉树（AVL树）的实现
- 哈夫曼树及其应用 合"根-左子树-右子树"的结构定义
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-08-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
