二叉树的遍历

1. 先序遍历（PreOrder）—— 根 → 左 → 右

void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);              // 访问根结点
        PreOrder(T->lchild);   // 遍历左子树
        PreOrder(T->rchild);   // 遍历右子树
    }
}

2. 中序遍历（InOrder）—— 左 → 根 → 右

void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);    // 遍历左子树
        visit(T);              // 访问根结点
        InOrder(T->rchild);    // 遍历右子树
    }
}

3. 后序遍历（PostOrder）—— 左 → 右 → 根

void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);  // 遍历左子树
        PostOrder(T->rchild);  // 遍历右子树
        visit(T);              // 访问根结点
    }
}

4. 层序遍历（LevelOrder）—— 从上到下、从左到右

void LevelOrder(BiTree T) {
    Queue Q;
    InitQueue(&Q);
    EnQueue(&Q, T);
    while (!QueueEmpty(Q)) {
        BiTNode *p;
        DeQueue(&Q, &p);
        visit(p);
        if (p->lchild) EnQueue(&Q, p->lchild);
        if (p->rchild) EnQueue(&Q, p->rchild);
    }
}

           A
         /   \
        B     C
       / \     \
      D   E     F
         /
        G

1. 非递归中序遍历

void InOrderNonRec(BiTree T) {
    SqStack S;
    InitStack(&S);
    BiTNode *p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            Push(&S, p);       // 一路向左，边走边入栈
            p = p->lchild;
        } else {
            Pop(&S, &p);       // 出栈
            visit(p);          // 访问
            p = p->rchild;     // 转向右子树
        }
    }
}

2. 非递归先序遍历

void PreOrderNonRec(BiTree T) {
    SqStack S;
    InitStack(&S);
    BiTNode *p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            visit(p);          // 与中序唯一的区别：入栈前先访问
            Push(&S, p);
            p = p->lchild;
        } else {
            Pop(&S, &p);
            p = p->rchild;
        }
    }
}

3. 非递归后序遍历（最复杂）

需要用 r 记录上一个访问过的结点，以区分「右子树还没走」和「右子树刚走完」：

void PostOrderNonRec(BiTree T) {
    SqStack S;
    InitStack(&S);
    BiTNode *p = T, *r = NULL;  // r 记录上次访问的结点
    while (p || !StackEmpty(S)) {
        if (p) {
            Push(&S, p);
            p = p->lchild;
        } else {
            GetTop(S, &p);                       // 只看栈顶，不弹出
            if (p->rchild && p->rchild != r)     // 右子树未访问
                p = p->rchild;
            else {
                Pop(&S, &p);
                visit(p);
                r = p;                            // 记录刚访问的结点
                p = NULL;                         // 防止重复向左
            }
        }
    }
}

例 1：由先序 + 中序构造

先序：A B D E C F　中序：D B E A F C

1. 先序第一个 A 是根；
2. 中序中 A 左边 D B E 是左子树（3 个结点），右边 F C 是右子树（2 个结点）；
3. 左子树先序 B D E、中序 D B E → B 是根，D 左、E 右；
4. 右子树先序 C F、中序 F C → C 是根，F 是左孩子。

         A
       /   \
      B     C
     / \   /
    D   E F

例 2：由后序 + 中序构造

后序：D E B F C A　中序：D B E A F C

1. 后序最后一个 A 是根；
2. 中序中 A 左边 D B E、右边 F C；
3. 左子树后序 D E B → B 是根（后序末位），D 左、E 右；
4. 右子树后序 F C → C 是根，F 是左孩子。

得到与例 1 完全相同的树 ✓

例 3：非递归中序遍历栈模拟

         A
       /   \
      B     C
     / \
    D   E