C语言二叉树遍历：递归与非递归实现及栈队列模拟-平芜编程栈

递归和非递归遍历这个话题，我前后给不同水平的读者讲过很多遍。很多人在初学二叉树时，感觉递归版本三五行就搞定，非递归版本却要换个栈绕来绕去，总有一种“能用递归就懒得写非递归”的心态。实际上，递归版本隐藏了函数调用栈的进出过程，而真正理解二叉树的访问顺序，恰恰需要你亲手把那个“隐藏的栈”用代码表达出来。这篇文章我就用C语言把递归和非递归的三种深度优先遍历全部写一遍，再加上层序遍历，顺便把创建二叉树、栈和队列的辅助实现都补齐，让你能直接编译运行，边跑边看结果。

这篇文章适合正在复习数据结构、准备笔试面试的初学者，也适合想快速重拾二叉树遍历细节的开发者。我会从“为什么要区分递归和非递归”讲起，给出完整代码和运行结果，最后分享一些我在调试这类代码时踩过的坑。看完之后，你可以照着代码一步步跟，也可以把它当成一份可复用地的手册，下次遇到树的题目直接查。

1. 二叉树基础与递归遍历

1.1 链式存储与创建方式

C语言里写二叉树，最通用的结构体定义长这样：

typedef struct BiTNode { int data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode, *BiTree;

每个节点只存三种信息：当前节点自己的数据、左孩子指针、右孩子指针。叶子节点的左右孩子指针都指向NULL，这是遍历过程中判断“能不能继续往下走”的关键条件。

有了结构体之后，还得解决“怎么从输入构建一棵树”。我习惯用先序序列配合空标记来创建，输入中遇到特殊字符#就表示这个子树位置为空。比如序列AB#D##C##代表的是一棵特定形状的树，创建函数的逻辑是典型的递归：读到一个非空字符，就创建当前节点，然后递归创建左子树，再递归创建右子树。

BiTree createTree(char **str) { if (**str == '#' || **str == '\0') { (*str)++; return NULL; } BiTree node = (BiTree)malloc(sizeof(BiTNode)); node->data = **str; (*str)++; node->lchild = createTree(str); node->rchild = createTree(str); return node; }

我建议初学者自己动手画一画这棵树，然后对照序列手动模拟一遍递归创建过程。只要这一步理解了，后面理解遍历递归同样会顺畅很多。

1.2 递归遍历：为什么代码能这么短

递归遍历的核心思想非常简单：一棵二叉树本身由“根节点、左子树、右子树”组成，那么遍历一棵树的问题，就能拆成“处理根节点 + 遍历左子树 + 遍历右子树”三个子问题。因为左右子树仍然是二叉树，所以同一个函数可以反复调用自己，直到遇到NULL节点才返回。

先序、中序、后序的唯一区别在于“访问根节点”这个动作放在什么位置。访问动作可以是打印、计数、累加，也可以是其他业务逻辑。下面给出最常见的打印版本：

void preorderRecursive(BiTree root) { if (root == NULL) return; printf("%c ", root->data); // 先访问根 preorderRecursive(root->lchild); preorderRecursive(root->rchild); } void inorderRecursive(BiTree root) { if (root == NULL) return; inorderRecursive(root->lchild); printf("%c ", root->data); // 中序：左、根、右 inorderRecursive(root->rchild); } void postorderRecursive(BiTree root) { if (root == NULL) return; postorderRecursive(root->lchild); postorderRecursive(root->rchild); printf("%c ", root->data); // 后序：左、右、根 }

三份代码唯一的不同就是printf("%c ", root->data)这行代码的位置。很多人背顺序靠口诀“先根左右、中左根右、后左右根”，但我一直觉得单纯背口诀不如理解调用顺序。你只要记住一句话：递归函数在做同样的事，把当前节点当作根来处理，子问题就交给下一层递归，顺序就自然写出来了。

1.3 递归背后的调用栈

递归之所以能跑起来，是因为编译器和运行时系统维护了一个函数调用栈。每次进入preorderRecursive函数，系统会为该次调用分配一块栈帧，里面保存了返回值地址、参数root、局部变量等信息。当函数内部再次调用自身时，新的栈帧压在旧的上面；当前一层的子调用全部返回后，栈帧弹出，程序回到上一层继续执行。

我用一个很简单的例子说明。假设树的结构是：

A / \ B C / \ D E

preorderRecursive(A)执行printf输出A，然后调用preorderRecursive(B)。这时候A这一帧还在栈里等着，B这一帧入栈。B输出B，接着调用preorderRecursive(D)。D输出D，左右子树都是NULL，D函数返回，B函数继续调用preorderRecursive(E)，E输出E后返回，B整个函数执行完毕返回，A再继续调用preorderRecursive(C)，C输出C后结束。所以最终结果是A B D E C。

如果你在调试器里观察函数调用栈，就能看到这种“往下钻、再往回退”的过程。理解了这一步，非递归版本其实就是在用一个我们自己创建的栈来模拟这套行为，只是栈里存的不是函数栈帧，而是树的节点指针。

2. 非递归遍历：为什么要绕开递归

2.1 递归的局限与栈模拟思路

递归代码好写，但不见得总是好用。每次函数调用都会消耗系统栈空间，树的深度过大时，比如一条链状的树有十万个节点，函数调用深度会跟着到十万层，系统栈往往只有几兆到几兆字节，很容易栈溢出。非递归版本手动管理栈，能在堆上分配空间，容量可控，而且逻辑明明白白，不会出现“调用栈爆炸”的问题。

除了稳定性，面试和笔试也特别喜欢考非递归。原因很简单：递归版本谁都会写，但能把递归转换为迭代，说明你真正看懂了“访问顺序到底是怎么形成的”。很多人一遇到非递归就懵，归根到底是没想清楚一个关键问题：栈里应该压什么？什么时机弹出？弹出之后下一步做什么？

以深度优先遍历来说，非递归遍历需要在栈里保存“当前还没处理完的节点”。因为在树上往下走时，我们随时可能要回到之前路过的节点，而栈的后进先出特性刚好合适：后遇到的子树先处理完，先遇到的祖先节点最后处理完。这实际上和递归的函数调用顺序完全一致。

2.2 手写栈的完整实现

为了不依赖操作系统栈，我要自己准备一个栈结构。这里用数组实现，为了简化问题，栈容量先固定为100，足够应付演示场景。实际项目中你可以改成动态扩容版本，逻辑大同小异。

#define MAXSIZE 100 typedef struct { BiTree data[MAXSIZE]; int top; } Stack; void initStack(Stack *s) { s->top = -1; } int isEmpty(Stack *s) { return s->top == -1; } int push(Stack *s, BiTree node) { if (s->top >= MAXSIZE - 1) return 0; s->data[++(s->top)] = node; return 1; } int pop(Stack *s, BiTree *node) { if (isEmpty(s)) return 0; *node = s->data[(s->top)--]; return 1; } int getTop(Stack *s, BiTree *node) { if (isEmpty(s)) return 0; *node = s->data[s->top]; return 1; }

top初始为-1，入栈时先加一再写入，出栈时先取出再减一。这个设计可以把“栈顶指针”理解为指向当前有效元素的索引，而不是下一个空位置，写起来比较直观。我在对照递归过程时用得最多的操作是getTop，因为很多非递归算法的下一步要根据栈顶节点的情况来决定，而并不急着弹出。

2.3 前序和中序非递归的核心区别

先看前序非递归。前序是“根左右”，也就是说每遇到一个节点，第一件事就是访问它，然后再去处理子树。这时候访问完当前节点后，需要先把右子树压栈，再把左子树压栈。因为栈是后进先出，先压右树，下一轮才能先弹出左树，保证左子树先被处理。

void preorderIter(BiTree root) { Stack s; initStack(&s); if (root != NULL) push(&s, root); while (!isEmpty(&s)) { BiTree node; pop(&s, &node); printf("%c ", node->data); if (node->rchild) push(&s, node->rchild); if (node->lchild) push(&s, node->lchild); } }

整个过程可以这样理解：栈顶永远放着“下一个要处理”的节点。弹出时立即打印，打印完把自己的左右子树按“右先左后”压栈，就能保持“先左边后右边”的遍历顺序。

中序非递归就更有意思了。中序是“左根右”，所以不能一遇到节点就打印，得先把左子树整个处理完，才能访问当前节点。实现思路是：从根节点开始，一直沿左子树往下走，沿途经过的节点全部压栈，直到左孩子为NULL；然后弹出栈顶节点，这个节点一定是“左子树已经处理完”的节点，打印它；随后把当前指针移到它的右子树，对右子树重复同样的过程。

void inorderIter(BiTree root) { Stack s; initStack(&s); BiTree cur = root; while (cur != NULL || !isEmpty(&s)) { while (cur != NULL) { push(&s, cur); cur = cur->lchild; } pop(&s, &cur); printf("%c ", cur->data); cur = cur->rchild; } }

这里最容易出错的地方在循环结束条件。很多初学版本只写了while (!isEmpty(&s))，结果当栈空但cur不为NULL时，循环提前退出，导致漏掉节点。正确条件是cur != NULL || !isEmpty(&s)，栈空不能作为唯一结束标志，因为刚弹出最后一个节点后，它的右子树可能还没处理。

我建议你手动拿一棵三个节点的树完整走一遍中序过程。比如树是B为根，B有左孩子A和右孩子C，中序应该是A B C。第一步一直走到最左的A并压栈，然后弹A打印，再移动到A的右子树NULL；此时栈里还有B，弹B打印，移动到C；C入栈，弹C打印。总共执行了A B C，每一步都清晰可见。

2.4 后序非递归：两种易用方案

后序“左右根”是非递归里最麻烦的一个，因为根节点必须等左右子树都处理完之后才能打印。如何在代码里判断“当前节点的左右子树都处理完了”？我在这里给两种比较实用的方案。

方案一：双栈法

双栈法的思路很巧妙。既然后序遍历是“左右根”，那我能不能先求出一个“根右左”的序列，然后反转成“左右根”？前序遍历很容易实现，是“根左右”。只要把前序中压栈的顺序稍微改一下，变成先压左孩子再压右孩子，遍历出来的结果就是“根右左”。把每一次访问到的节点压到第二个栈里，最后把第二个栈全部弹出，顺序就是后序。

void postorderIterTwoStack(BiTree root) { if (root == NULL) return; Stack s1, s2; initStack(&s1); initStack(&s2); push(&s1, root); while (!isEmpty(&s1)) { BiTree node; pop(&s1, &node); push(&s2, node); if (node->lchild) push(&s1, node->lchild); if (node->rchild) push(&s1, node->rchild); } while (!isEmpty(&s2)) { BiTree node; pop(&s2, &node); printf("%c ", node->data); } }

你可能会疑惑：为什么push(&s1, node->lchild)和push(&s1, node->rchild)的顺序和前序正好相反？因为s1弹出某个节点后，会把左右子树入栈，而栈的后进先出会让下一次优先弹出后压入的那一个。先压左再压右，弹出的顺序就是先右后左，于是s2中收集到的顺序就成了“根右左”。把s2倒序输出，就得到“左右根”。

方案二：单栈标记法

双栈法逻辑简单，但需要两个栈。如果只想用一个栈，最常用的办法是在栈里给每个节点附带一个状态标记，表示“当前节点的左子树处理完了，还是右子树也处理完了”。

typedef struct { BiTree ptr; int flag; } StackElem; void postorderIterOneStack(BiTree root) { StackElem stack[MAXSIZE]; int top = -1; BiTree cur = root; while (cur != NULL || top != -1) { while (cur != NULL) { stack[++top].ptr = cur; stack[top].flag = 0; cur = cur->lchild; } while (top != -1 && stack[top].flag == 1) { printf("%c ", stack[top--].ptr->data); } if (top != -1) { stack[top].flag = 1; cur = stack[top].ptr->rchild; } } }

这段代码的意思归纳为：先把从当前节点出发的所有左孩子压栈，标记都为0，表示左子树还没处理完。当左子树到底之后，检查栈顶：如果栈顶节点的flag为0，说明左子树已经遍历完，轮到处理右子树，于是把flag改成1，然后把当前指针切换到右子树，继续重复“往左钻”的过程。如果flag为1，说明右子树也已经处理完，这时弹出并打印节点。

单栈法的优势是省空间，但理解起来需要一点时间。我建议第一次接触时先跑双栈版，把结果跑对了，再回头把单栈版和递归调用的函数栈帧对照着看，会更容易接受。

3. 层序遍历与完整测试

3.1 用队列实现层序遍历

深度优先遍历是沿着一条路走到黑，再回头。层序遍历则是按“层级”从上到下、从左到右逐个访问，比如根节点一层、它的左右孩子一层、再下一层。层序遍历不能用栈，得用队列，因为先进来的节点要先被处理，符合“一层一层推进”的逻辑。

队列可以用数组模拟循环队列，也可以用链表。为了和之前的栈代码保持一致，我用数组加front和rear两个指针来实现：

#define QUEUE_MAX 100 typedef struct { BiTree data[QUEUE_MAX]; int front; int rear; } Queue; void initQueue(Queue *q) { q->front = 0; q->rear = 0; } int isQueueEmpty(Queue *q) { return q->front == q->rear; } int enQueue(Queue *q, BiTree node) { if ((q->rear + 1) % QUEUE_MAX == q->front) return 0; q->data[q->rear] = node; q->rear = (q->rear + 1) % QUEUE_MAX; return 1; } int deQueue(Queue *q, BiTree *node) { if (isQueueEmpty(q)) return 0; *node = q->data[q->front]; q->front = (q->front + 1) % QUEUE_MAX; return 1; } void levelOrder(BiTree root) { Queue q; initQueue(&q); if (root != NULL) enQueue(&q, root); while (!isQueueEmpty(&q)) { BiTree node; deQueue(&q, &node); printf("%c ", node->data); if (node->lchild) enQueue(&q, node->lchild); if (node->rchild) enQueue(&q, node->rchild); } }

队列容量这里预留了一个空位来区分队列满和队列空，所以实际能存99个节点。对于演示级别的树完全够用。如果你想处理更大规模的数据，可以把队列改成链式存储，逻辑是一样的。

3.2 创建一棵测试树并验证结果

光看代码不够，直接跑一遍最直观。为了测试所有遍历函数，我写了一个main函数，按先序序列创建一棵固定树。假设树的形状是：

A / \ B C / \ \ D E F

对应的先序序列为ABD##E##C#F##。其中#表示空节点。注意看，C只有右孩子F，所以C后面先是一个#表示左孩子为空，再是F，最后两个#表示F的左右孩子为空。

int main() { char *str = "ABD##E##C#F##"; BiTree root = createTree(&str); printf("先序递归: "); preorderRecursive(root); printf("\n"); printf("中序递归: "); inorderRecursive(root); printf("\n"); printf("后序递归: "); postorderRecursive(root); printf("\n"); printf("先序非递归: "); preorderIter(root); printf("\n"); printf("中序非递归: "); inorderIter(root); printf("\n"); printf("后序非递归(双栈): "); postorderIterTwoStack(root); printf("\n"); printf("后序非递归(单栈): "); postorderIterOneStack(root); printf("\n"); printf("层序遍历: "); levelOrder(root); printf("\n"); return 0; }

编译运行后的输出应该是：

先序递归: A B D E C F 中序递归: D B E A C F 后序递归: D E B F C A 先序非递归: A B D E C F 中序非递归: D B E A C F 后序非递归(双栈): D E B F C A 后序非递归(单栈): D E B F C A 层序遍历: A B C D E F

我特别想提醒你注意几个对应关系：先序递归和非递归输出完全相同，这验证了迭代版只是把递归的调用栈换成了显式栈；中序同样如此；两种后序非递归方法的结果也都一致，说明两个不同思路实际上描述的是同一种遍历顺序。层序遍历按层输出，根A、第二层B C、第三层D E F，顺序清晰。

如果你的运行结果和这个不一致，多半是入栈顺序写反，或者输入序列里的#数量不对。这时候不要急着改代码，先在纸上画出树，再手动模拟一遍，往往比干瞪眼找bug快很多。

4. 常见问题与避坑经验

4.1 代码运行常见的坑

栈容量不够

前面写的固定大小为100的栈，处理几十个节点的树没问题。但如果树的节点数超过容量，压栈函数会返回0，而我在演示代码里没有检查返回值，结果就是元素丢失，遍历结果莫名其妙。正式写代码时要么在push里处理扩容，要么在调用处判断返回值，缺一不可。

空树处理

很多遍历函数对空树返回的顺序很敏感。比如preorderIter在root为NULL时，栈为空，循环不执行，函数自然结束，这没问题。但单栈后序写法里，如果cur初始为NULL且栈为空，while (top != -1 && stack[top].flag == 1)内部不会弹任何节点，主循环判断条件cur != NULL || top != -1也很快退出，输出为空。看起来输出空结果正确，但如果你把空树的root传入某些没有初始化的函数，可能访问野指针。建议在所有遍历函数开头先判断root == NULL，直接返回空结果。

中序非递归循环条件写错

我刚学的时候，中序写成while (!isEmpty(&s))，遍历一个完整树时经常少打印右子树节点。原因前面提过，栈空时cur可能还指向右子树，必须把cur != NULL纳入判断。这个错误非常隐蔽，因为如果树刚好是完全二叉树，可能结果碰巧是对的；但只要右子树还有更深的节点，漏节点问题就暴露了。

后序单栈法搞混flag含义

我见过很多人在单栈法里把flag=0当作“右子树处理完”，然后打印时机完全反了。要记住一个简单约定：flag=0表示这个节点刚刚入栈，左子树还没处理；flag=1表示左子树已处理完，接下来要处理右子树；等右子树也处理完，即遇到flag=1且再次回到该节点时，才允许打印。所以正确逻辑是：初始入栈flag=0；出循环时遇到flag=0就改成flag=1并转到右子树；遇到flag=1就打印并弹出。次序反了，输出就会变成“根左右”之类的前序遍历。

4.2 怎么验证自己真的懂了

我自己的经验是，验证理解程度的最好办法不是默写代码，而是拿着一个至少四层的树，手动模拟每一步栈的变化。准备一张纸，左边写树，右边画栈，每执行一步就把栈里从底到顶的元素列出来。

举个例子，中序遍历中，第一次while (cur != NULL)会一直压左孩子压到最底层。这时候栈里从底到顶是根、根的左孩子、左孩子的左孩子……你会看到栈底永远是最早的祖先节点，栈顶是最新到达的节点。然后弹出栈顶并打印，再切到它的右子树。这个过程模拟几轮以后，自然就理解了“左根右”是怎么通过栈实现的。

如果用手动模拟太慢，我建议你在代码里临时加一个打印函数，在每次入栈、出栈时输出当前栈内容。比如在inorderIter里，压入一个节点后打印push: node->data，弹出时打印pop: node->data，运行结果就是完整的栈操作日志，对照日志看代码会清楚很多。