遍历
中序、前序和后序遍历。
遍历 是 CoddyKit 上的免费 C Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。
什么是遍历
遍历是一种系统地访问树中每个节点且恰好访问一次的方法。
经典的三种深度优先顺序是中序、先序和后序。它们的区别仅在于相对于子树，当前节点在什么时候被处理。
中序遍历
中序遍历先访问左子树，然后访问节点，最后访问右子树。
对于 BST，它会按升序输出值，因此是搜索树最实用的遍历方式。
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}先序遍历
先序遍历先访问节点，然后访问左子树，最后访问右子树。
由于根节点会在子节点之前输出，这种遍历适合复制树或生成前缀表达式。
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}后序遍历
后序遍历先访问两个子树，最后访问节点本身。
由于子节点会在父节点之前处理，因此释放树时正需要这种顺序，这样子节点被释放后就不会再使用节点。
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}通用模式
三种深度优先遍历共享相同的骨架：NULL 基准情况、递归进入左子节点、递归进入右子节点，以及访问步骤。
只有访问步骤的位置不同，遍历的名称才会不同。
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/中序遍历输出有序结果
此程序构建一个小型 BST 并执行中序遍历，展示输出结果有序这一特性。
无论插入顺序如何，输出值都会从最小到最大排列。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}比较三种顺序
对于根节点为 10、左节点为 5、右节点为 15 的树，输出结果不同：
先序遍历得到 10 5 15。中序遍历得到 5 10 15。后序遍历得到 5 15 10。节点值相同，改变的只有访问时机。
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/层序遍历
广度优先遍历，也称层序遍历，会从上到下逐层访问节点。它并不适合直接使用递归，而是使用队列。
我们先将根节点加入队列，然后反复取出一个节点、输出它，再将其子节点加入队列。
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}遍历驱动实际工作
遍历是所有必须触及每个节点的操作的模板，而不仅仅用于输出。
将访问步骤替换为计算值的总和、查找最大值或复制节点，相同的结构就能完成这些工作。
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}遍历的开销
每种遍历都会访问每个节点一次，因此运行时间与 n 成正比，其中 n 是节点数量。
递归使用的栈空间与树的高度成正比；树平衡时高度为 log(n)，最坏情况下为 n。
三种遍历同时进行
此程序对同一棵树输出先序、中序和后序遍历结果，方便您并排比较。
请注意，只有输出调用的位置发生变化，结果序列就会不同。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}快速检查
为任务选择正确的遍历方式。
回顾
深度优先遍历共享一个递归骨架；访问步骤的位置决定它是先序、中序还是后序。BST 的中序遍历会产生有序输出，而后序遍历是释放节点的安全顺序。
层序遍历属于广度优先遍历，并使用队列。所有遍历都会在 O(n) 时间内访问每个节点一次。
常见问题解答
「遍历」课时是免费的吗？
是的 — 「遍历」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。
「遍历」这节课中我会学到什么？
中序、前序和后序遍历。 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 C Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「遍历」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 C Academy 课中编写并运行代码吗？
能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。