考研笔记

板子：非递归遍历（中序、前序、后序）

用栈模拟递归：一路向左，边走边入栈；走到空，就弹出一个结点，转向它的右子树。中序和前序只差 visit 的位置；后序多一个指针 r，记住「上一个访问的结点」。

代码

void InOrder2(BiTree T) {                    // 中序非递归 ★★★
    BiTNode *st[MaxSize];                    // 栈里存结点指针
    int top = -1;
    BiTNode *p = T;
    while (p != NULL || top != -1) {         // 还有没走到的结点，或者栈里还有结点
        if (p != NULL) {                     // 一路向左，边走边入栈
            st[++top] = p;
            p = p->lchild;
        } else {                             // 左边走到头了
            p = st[top--];                   // 弹出一个：它的左子树已经处理完
            visit(p);                        // 中序：出栈时访问
            p = p->rchild;                   // 转向右子树
        }
    }
}
 
void PreOrder2(BiTree T) {                   // 前序非递归：和中序只差 visit 的位置
    BiTNode *st[MaxSize];
    int top = -1;
    BiTNode *p = T;
    while (p != NULL || top != -1) {
        if (p != NULL) {
            visit(p);                        // 前序：入栈时访问
            st[++top] = p;
            p = p->lchild;
        } else {
            p = st[top--];
            p = p->rchild;
        }
    }
}
 
void PostOrder2(BiTree T) {                  // 后序非递归
    BiTNode *st[MaxSize];
    int top = -1;
    BiTNode *p = T, *r = NULL;               // r：上一个访问的结点
    while (p != NULL || top != -1) {
        if (p != NULL) {                     // 一路向左
            st[++top] = p;
            p = p->lchild;
        } else {
            p = st[top];                     // 只读栈顶、先不出栈：它的右子树可能还没走
            if (p->rchild != NULL && p->rchild != r)
                p = p->rchild;               // 右子树存在且还没访问过：先去右子树
            else {                           // 右子树为空，或者刚从右子树回来：可以访问根了
                top--;
                visit(p);
                r = p;                       // 记下刚访问的结点
                p = NULL;                    // 必须置空：下一轮直接看新的栈顶，不能再往左走
            }
        }
    }
}

复杂度：时间 ，空间 （栈的深度不超过树高）。

关键边界（后序）

代码为什么
p = st[top] 只读不出栈从左子树回来时右子树还没走，根要继续留在栈里
p->rchild != r用来判断「刚从右子树回来」：右孩子正好是上一个访问的结点
访问后 p = NULL访问完根，下一步应该回到它的双亲。不置空的话，下一轮会把 p 再次入栈，陷入死循环

后序非递归的一个性质

访问某个结点时，栈里从底到顶正好是它的所有祖先（从根往下排）。找「值为 的结点的所有祖先」「根到某个结点的路径」都可以利用这一点，见 找祖先与最近公共祖先。

易错点

  • 循环条件是 p != NULL || top != -1，两个条件缺一不可。刚开始时栈是空的但 p 不空；中途 p 为空但栈不空。
  • 栈里存的是结点指针 BiTNode *，不是 int。
  • 前序非递归有另一种写法：根入栈，每次弹出一个结点后先压右孩子、再压左孩子。两种都对，这里的写法和中序统一，更好记。

链接

反向链接