二叉树遍历
二叉树遍历
在计算机程序中，遍历（traversal）本身是一个线性操作，所以遍历同样具有线性结构的数组或链表是一件轻而易举的事情。
反观二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的结点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。
二叉树的遍历方式分为4种：
-
前序遍历（pre-order）：访问根结点，遍历左子树，遍历右子树。
-
中序遍历（in-order）：遍历左子树，访问根结点，遍历右子树。
-
后序遍历（post-order）：遍历左子树，遍历右子树，访问根结点。
-
层次遍历（level-order）：按照从根结点到叶子结点的层次关系，一层一层横向遍历。
以下代码使用结点的data、left和right字段。Java的Node与遍历方法放在同一个类中；C的非递归中序遍历和层次遍历使用结点总数n，为指针栈或队列分配空间。
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t {
int data;
struct node_t *left;
struct node_t *right;
} node_t;前序遍历
二叉树的前序遍历，首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果结点为空则返回。
前序遍历：根 → 左 → 右
解锁完整互动实验、进阶解析与精选参考答案。
前序遍历
void pre_order(node_t *node) {
if (node == NULL) {
return;
}
printf("%d\n", node->data);
pre_order(node->left);
pre_order(node->right);
}中序遍历
二叉树的中序遍历，首先遍历左子树，然后访问根结点，最后遍历右子树，如果结点为空则返回。
中序遍历：左 → 根 → 右
解锁完整互动实验、进阶解析与精选参考答案。
中序遍历
void in_order(node_t *node) {
if (node == NULL) {
return;
}
in_order(node->left);
printf("%d\n", node->data);
in_order(node->right);
}后序遍历
二叉树的后序遍历，首先遍历左子树，然后遍历右子树，最后访问根结点，如果结点为空则返回。
后序遍历：左 → 右 → 根
解锁完整互动实验、进阶解析与精选参考答案。
后序遍历
void post_order(node_t *node) {
if (node == NULL) {
return;
}
post_order(node->left);
post_order(node->right);
printf("%d\n", node->data);
}二叉树遍历非递归实现
绝大多数可以用递归解决的问题，其实都可以用栈来解决，因为递归和栈都有回溯的特性。
以二叉树的中序遍历为例。当遇到一个结点时，就把它入栈，并去遍历它的左子树。当左子树遍历结束后，从栈顶弹出这个结点并访问它，然后按其右指针再去中序遍历该结点的右子树。
栈实现中序遍历
解锁完整互动实验、进阶解析与精选参考答案。
中序遍历（非递归）
void in_order_iterative(node_t *node, size_t n) {
if (node == NULL) {
return;
}
node_t **stack = malloc(n * sizeof(node_t *));
if (stack == NULL) {
fprintf(stderr, "Error: memory allocation failed.\n");
return;
}
size_t top = 0;
while (node != NULL || top > 0) {
while (node != NULL) {
stack[top++] = node;
node = node->left;
}
node = stack[--top];
printf("%d\n", node->data);
node = node->right;
}
free(stack);
}层次遍历
二叉树同一层次的结点之间是没有直接关联的，需要队列来辅助完成层序遍历。
层次遍历从根结点开始首先将根结点入队，然后开始循环执行以下操作直到队列为空：结点出队、访问该结点、其左右儿子入队。
队列实现层次遍历
解锁完整互动实验、进阶解析与精选参考答案。
层次遍历
void level_order(node_t *node, size_t n) {
if (node == NULL) {
return;
}
node_t **queue = malloc(n * sizeof(node_t *));
if (queue == NULL) {
fprintf(stderr, "Error: memory allocation failed.\n");
return;
}
size_t front = 0, rear = 0;
queue[rear++] = node;
while (front < rear) {
node = queue[front++];
printf("%d\n", node->data);
if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
free(queue);
}知识测验
知识测验
用四种顺序遍历同一棵树
写出前序、中序、后序、层次遍历结果。再用显式栈做中序遍历，说明第一次输出2前哪些结点入栈，以及输出4后为什么进入6。