C 语言二叉树构建与遍历全解析（递归与非递归）

二叉树节点定义

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

1. 先序序列构建二叉树（' ' 表示空）

int idx = 0;
BiTree Create(BiTree T, const char *str) {
    char ch = str[idx++];
    if (ch == ' ') return NULL;
    T = (BiTree)malloc(sizeof(BiTNode));
    T->data = ch;
    T->lchild = Create(T->lchild, str);
    T->rchild = Create(T->rchild, str);
    return T;
}

输入示例："abc de f g " 对应树形：

       a
      / \
     b   e
    /   / \
   c   f   g
  / \
 d   (空)

2. 递归遍历（三种次序）

void PreOrder(BiTree T)  { if (T) { putchar(T->data); PreOrder(T->lchild); PreOrder(T->rchild); } }
void InOrder (BiTree T)  { if (T) { InOrder(T->lchild); putchar(T->data); InOrder(T->rchild); } }
void PostOrder(BiTree T) { if (T) { PostOrder(T->lchild); PostOrder(T->rchild); putchar(T->data); } }

3. 非递归遍历：栈模拟

前序（根-左-右）

void PreOrderIter(BiTree T) {
    BiTree st[100], p = T; int top = -1;
    while (top >= 0 || p) {
        while (p) { putchar(p->data); st[++top] = p; p = p->lchild; }
        p = st[top--]->rchild;
    }
}

中序（左-根-右）

void InOrderIter(BiTree T) {
    BiTree st[100], p = T; int top = -1;
    while (top >= 0 || p) {
        while (p) { st[++top] = p; p = p->lchild; }
        p = st[top--]; putchar(p->data); p = p->rchild;
    }
}

后序（左-右-根）—— 双栈法或单栈+标记法

// 单栈 + tag 数组：0=左子树未访问，1=右子树未访问
void PostOrderIter(BiTree T) {
    BiTree st[100], p = T; int tag[100], top = -1;
    do {
        while (p) { st[++top] = p; tag[top] = 0; p = p->lchild; }
        if (top >= 0) {
            if (!tag[top]) { p = st[top]->rchild; tag[top] = 1; }
            else { putchar(st[top--]->data); p = NULL; }
        }
    } while (p || top >= 0);
}

4. 层序遍历（广度优先，队列）

void LevelOrder(BiTree T) {
    BiTree q[100]; int front = 0, rear = 0;
    if (T) q[rear++] = T;
    while (front < rear) {
        BiTree p = q[front++];
        putchar(p->data);
        if (p->lchild) q[rear++] = p->lchild;
        if (p->rchild) q[rear++] = p->rchild;
    }
}

5. 完整可运行示例

#include <stdio.h>
#include <stdlib.h>

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

int idx = 0;
BiTree Create(BiTree T, const char *str) {
    char ch = str[idx++];
    if (ch == ' ') return NULL;
    T = (BiTree)malloc(sizeof(BiTNode));
    T->data = ch; T->lchild = T->rchild = NULL;
    T->lchild = Create(T->lchild, str);
    T->rchild = Create(T->rchild, str);
    return T;
}
// ... 上述遍历函数 ...

int main() {
    const char *str = "abc  de f  g    ";
    BiTree root = Create(NULL, str);
    printf("Pre:  "); PreOrderIter(root);  puts("");
    printf("In:   "); InOrderIter(root);   puts("");
    printf("Post: "); PostOrderIter(root); puts("");
    printf("Level:"); LevelOrder(root);    puts("");
    return 0;
}

输出：

Pre:  abcde fg
In:   cdbaefg
Post: cdbfgea
Level: abecdfg

6. 常见面试变体

• 销毁树（后序释放）
• 求树高、节点数、叶子数
• 判断两树同构/镜像
• 最近公共祖先（LCA）
• 序列化与反序列化

总结

二叉树是树形结构的基础。递归代码简洁但受栈深度限制；非递归显式栈/队列可控、通用。建议熟练掌握四种遍历的非递归写法，并能手写销毁、求高、LCA 等常考操作。理解“栈模拟系统调用栈”、“队列模拟层序”两大核心思想，举一反三应对 N 叉树、图遍历亦不在话下。