普通二叉树遍历包括前序、中序、后序及层序四种方式。前序、中序、后序通常采用递归实现，遵循根左右、左根右、左右根的顺序。层序遍历需借助队列完成自上而下、自左向右的访问。文章提供节点结构定义、创建示例及完整 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