C++ 数据结构(五)二叉树(6)中序遍历
     发布在:C/C++      浏览:33      评论:0 条评论

上一篇:《C++ 数据结构(五)二叉树(5)先序遍历》

递归

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);
} // T(n) = T(a) + O(1) + T(n-a-1) = O(n)
C++ 数据结构(五)二叉树(6)中序遍历

迭代

观察

C++ 数据结构(五)二叉树(6)中序遍历

思路

从根出发沿左分支下行,直到最深的节点 —— 它就是全局首先被访问者

C++ 数据结构(五)二叉树(6)中序遍历

算法

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_I1(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 -> rChild;  // 再转向其右子树(可能为空,留意处理手法)
    }
}

实例

C++ 数据结构(五)二叉树(6)中序遍历

下一篇:《C++ 数据结构(五)二叉树(7)层次遍历》

Responses