一、二叉树结构基础
一般而言,对于一棵普通二叉树是通过链式结构定义,即每个节点包含三个部分:
- 数据域(data):用于存储节点的值
- 左指针(left):用于指向左子节点
- 右指针(right):用于指向右子节点
普通二叉树遍历包括前序、中序、后序及层序四种方式。前序、中序、后序通常采用递归实现,遵循根左右、左根右、左右根的顺序。层序遍历需借助队列完成自上而下、自左向右的访问。文章提供节点结构定义、创建示例及完整 C 语言代码,并通过练习题巩固根据遍历序列还原二叉树的能力。

一般而言,对于一棵普通二叉树是通过链式结构定义,即每个节点包含三个部分:
- 数据域(data):用于存储节点的值
- 左指针(left):用于指向左子节点
- 右指针(right):用于指向右子节点
typedef int BTDataType;
struct BinaryTree {
BTDataType data;
struct BinaryTree* left;
struct BinaryTree* right;
};
在学习二叉树的基本操作前,需先创建一棵二叉树。可以通过手动快速创建一棵简单的二叉树。

代码实现如下:
BTNode* BuyNode(int x) {
BTNode* root = (BTNode *)malloc(sizeof(BTNode));
if (root == NULL) {
perror("malloc fail");
return NULL;
}
root->data = x;
root->left = NULL;
root->right = NULL;
return root;
}
BTNode* TreeCreate() {
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;
node2->right = node6;
node4->left = node5;
return node1;
}
A. 若此棵树为空树,即根节点为 NULL,不进行任何操作。 B. 若此棵树不为空,即根节点不为 NULL,进行如下操作:
所以前序遍历可简记为:根 左 右 的顺序进行遍历。具体逻辑可通过递归函数形式实现。

前序遍历的结果如下图所示:

如果不省略空节点的打印即为:1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL 如果省略空节点的打印即为:1 2 3 4 5 6
// 前序遍历
void PrevOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}

A. 若此棵树为空树,即根节点为 NULL,不进行任何操作。 B. 若此棵树不为空,即根节点不为 NULL,进行如下操作:
所以中序遍历可简记为:左 根 右 的顺序进行遍历。

中序遍历的结果如下图所示:

如果不省略空节点的打印即为:NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL 如果省略空节点的打印即为:3 2 1 5 4 6
// 中序遍历
void InOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}

A. 若此棵树为空树,即根节点为 NULL,不进行任何操作。 B. 若此棵树不为空,即根节点不为 NULL,进行如下操作:
所以后序遍历可简记为:左 右 根 的顺序进行遍历。

后序遍历的结果如下图所示:

如果不省略空节点的打印即为:NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1 如果省略空节点的打印即为:3 2 5 6 4 1
// 后序遍历
void PostOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}

进行层次遍历时需要借助一个队列,层次遍历的核心思想为:上一层的节点出队,带入下一层的节点入队。

下图为二叉树的层次遍历,即按照箭头所指的方向,按照自上而下,自左向右的顺序对二叉树的各个结点进行逐层访问。
可以得到下图二叉树的层次遍历序列为:1 2 3 4 5 6

// 层序遍历
// 上一层节点出队,带入下一层节点入队
void TreeLevelOrder(BTNode* root) {
Queue q;
QueueInit(&q);
if (root) QueuePush(&q, root);
while (!QueueEmpty(&q)) {
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if (front->left) QueuePush(&q, front->left);
if (front->right) QueuePush(&q, front->right);
}
QueueDestroy(&q);
}
二叉树的前序(先序)遍历为:EFHIGJK,二叉树的中序遍历:HFIEJKG,则二叉树为?
核心思路:由前序遍历确定根,中序遍历确定左右子树。 前序遍历的特点:根 左子树 右子树 中序遍历的特点:左子树 根 右子树 所以对于前序遍历而言,从左往右进行的过程就是相当于对根的遍历,而通过根的确定,对中序序列进行分割左右子树。
二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树的形状为?
核心思路:由后序遍历确定根,中序遍历确定左右子树。 后序遍历的特点:左子树 右子树 根 中序遍历的特点:左子树 根 右子树 对于后序序列从右往左的过程,就相当于对根进行确定,而通过根的确定,对中序序列进行分割左右子树。
二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF,则按层次输出(同一层从左到右)的序列。
核心思路:由后序遍历确定根,中序遍历确定左右子树。 后序遍历的特点:左子树 右子树 根 中序遍历的特点:左子树 根 右子树 对于后序序列从右往左的过程,就相当于对根进行确定,而通过根的确定,对中序序列进行分割左右子树。
故而:层序遍历的结果为:FEDCBA
完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH,则该完全二叉树的前序序列为?
由层序遍历的特性:自上而下,自左到右。
故而前序遍历的结果为:ABDHECFG

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online