5.3 遍历二叉树

遍历：按照某种次序访问树中各节点，每个节点被访问恰好一次
T = V ∪ L ∪ R
先序(preorder)遍历：V ｜ L ｜ R
中序(inorder)遍历：L ｜ V ｜ R
后序(postorder)遍历：L ｜ R ｜ V
层次（广度）遍历：自上而下，先左后右

先序遍历递归实现

template <typename T, typename VST> void traverse(BinNodePosi(T) x, VST & visit) {
    if (!x)
        return;
    visit(x -> data);
    traverse(x -> lChild, visit);
    traverse(x -> rChild, visit);
}

迭代实现

template <typename T, typename VST> void travPre(BinNodePosi(T) x, VST & visit) {
    Stack <BinNodePosi(T)> S; // 辅助栈
    if (x)
        S.push(x); // 根节点入栈
    while (!S.empty()) { // 在栈变空前循环
        x = S.pop();
        visit(x -> data); // 弹出并访问当前节点
        if (HasRChild(*x))
            S.push(x -> rChild); // 右子节点先入后出
        if (HasLChild(*x))
            S.push(x -> lChild); // 左子节点后入先出
    }
}

上述方法仅适用于先序遍历，重新设计以适应其它遍历方式

template <typename T, typename VST> static void visitAlongLeftBranch(BinNodePosi(T) x, VST & visit, Stack <BinNodePosi(T)> & S) {
    while (x) {
        visit(x -> data); // 访问当前节点
        S.push(x -> rChild); // 右节点（子树）入栈
        x = x -> lChild; // 沿左侧链下行
    }
}
template <typename T, typename VST> void travPre(BinNodePosi(T) x, VST & visit) {
    Stack <BinNodePosi(T)> S; // 辅助栈
    while (true) { // 以（右）子树为单位，逐批访问节点
        visitAlongLeftBranch(x, visit, S); // 访问子树x的左侧链，右子树入栈缓冲
        if (S.empty())
            break; // 栈空即退出
        x = S.pop(); // 弹出下一子树的根
    }
}

中序遍历递归实现

template <typename T, typename VST> void traverse(BinNodePosi(T) x, VST & visit) {
    if (!x)
        return;
    traverse(x -> lChild, visit);
    visit(x -> data);
    traverse(x -> rChild, visit);
}

中序遍历迭代实现
从根出发沿左分支下行，直至最深节点，即全局最先被访问者

template <typename T> static void goAlongLeftBranch(BinNodePosi(T) x, Stack <BinNodePosi(T) & S) {
    while (x) {
        S.push(X);
        x = x -> lChild; // 反复入栈，沿左分支深入
    }
}
template <typename T, typename V> void travIn(BinNodePosi(T) x, V& visit) {
    Stack <BinNodePosi(T)> S; // 辅助栈
    while (true) {
        goAlongLeftBranch(x, S); // 从当前节点出发，逐批入栈
        if (S.empty())
            break; // 直至所有节点处理完毕
        x = S.pop(); // x左子树或为空，或已遍历
        visit(x -> data); // 访问x
        x = x -> rChild; // 转向x右子树（可能为空）
    }
}

后序遍历递归实现

template <typename T, typename VST> void traverse(BinNodePosi(T) x, VST & visit) {
    if (!x)
        return;
    traverse(x -> lChild, visit);
    traverse(x -> rChild, visit);
    visit(x -> data);
}

后序遍历迭代实现

template <typename T> static void gotoLeftmostLeaf(Stack <BinNodePosi(T) & S) {
    while (BinNodePosi(T) x = S.pop()) { // 自顶而下反复检查栈顶节点
        if (HasLChild(*x)) { // 尽可能向左
            if (HasRChild(*X)) // 若存在右子节点
                S.push(x -> rChild); // 则优先入栈
            S.push(x -> lChild); // 转向左子节点
        } else {
            S.push(x -> rChild);
        }
    }
    S.pop(); // 弹出栈顶空节点
}
template <typename T, typename VST> void travPost(BinNodePosi(T) x, VST & visit) {
    Stack <BinNodePosi(T)> S; // 辅助栈
    if (x)
        S.push(x); // 根节点首先入栈
    while (!S.empty()) { // x始终为当前节点
        if (S.top() != x -> parent) // 若栈顶非x父节点（而为右兄弟节点）
            gotoLeftmostLeaf(S); // 则在其右兄弟子树中递归深入
        x = S.pop(); // 弹出栈顶（即前一节点后继）以更新x
        visit(x -> data); // 访问
    }
}

层次遍历

template <typename T> template <typename VST> void BinNode<T>::travLevel(VST & visit) { // 二叉树层次遍历
    Queue<BinNodePosi(T)> Q; // 辅助队列
    Q.enqueue(this); // 根节点入队
    while (!Q.empty()) { // 在队列再次变空前反复迭代
        BinNodePosi(T) x = Q.dequeue(); // 取出队首节点
        visit(x -> data); // 访问
        if (HasLChild(*x))
            Q.enqueue(x -> lChild); // 左子节点入队
        if (HasRChild(*x))
            Q.enqueue(x -> rChild); // 右子节点入队
    }
}