二叉树 || 三种遍历的非递归实现

思路

• 前序：根 左 右
• 中序：左 根 右
• 后序：左 右 根

无论是前序、中序、后序，遍历二叉树的过程都是基本一致的。
不失一般性，把叶结点的左右子树看成空树。空树没有孩子，到空树返回。
那么对某结点的遍历过程可描述为：

• 走到某结点，先向左看，进入左子树，从左子树返回；
• 回到了这个结点，再向右看，进入右子树，从右子树返回；
• 又回到了这个结点。

任意一个非空结点都路过了三次。
前序：第一次路过时访问。
中序：第二次路过时访问。
后序：第三次路过时访问。

为了能回到之前路过的结点，需要把它存下来，用栈！
因此，可以每个结点增设一个计数已经路过次数的量来实现非递归的遍历是可行的。

参考

• 二叉树的后序遍历--非递归实现
• 详解二叉树的非递归遍历

实现

• 中序

// non-recursive
void in_traverse(Node* root) {
    stack<Node*> ms;
    Node* p = root;
    while(p || !ms.empty()) {
        if(p) {
            ms.push(p);
            p = p->lc;
        } else {
            p = ms.top();
            printf("%d ", p->val);
            ms.pop();
            p = p->rc;
        }
    }
}

• 前序

相比中序的非递归版，只改变了访问结点的时机。

void pre_traverse(Node* root) {
    stack<Node*> ms;
    Node* p = root;
    while(p || !ms.empty()) {
        if(p) {
            printf("%d ", p->val);
            ms.push(p);
            p = p->lc;
        } else {
            p = ms.top();
            ms.pop();
            p = p->rc;
        }
    }
}

• 后序

post_traverse(root);
想办法把 "访问完右子树再访问根结点" 表达出来
关键是确定刚访问过的结点位于当前结点的左子树还是右子树

• 表达方式1
  两个指针 p_curr, p_last_visit
  访问p_curr的条件：p_curr->right==NULL || p_last_visit == p->right

• 表达方式2
  每个结点增设一标记，若访问了它的左子树，tag = left；若访问了它的右子树，tag = right。标记为right才访问。

• 表达方式3
  每个结点push时直接push两遍。

  • 在循环体中，每次弹出一个节点赋给p
  • 如果p仍然等于栈的头结点，说明p的孩子们还没有被操作过，应该把它的孩子们加入栈中；否则，访问p。
    也就是说，第一次弹出，将p的孩子压入栈中，第二次弹出，访问p。