数据结构(C++)——二叉树的遍历：先序,后序,中序,层次遍历

迷南。 2022-05-18 11:16 205阅读 0赞

递归式遍历

![70][]

1.先序遍历

template <typename T, typename VST>     //元素类型、操作器
    void travPre_R(BinNodePosi(T) x, VST& visit)   {   //二叉树先序遍历算法
        if (!x) return;
        visit( x->data);
        travPre_R(x->lChild, visit);
        travPre_R(x->rChild, visit);
    }

![70 1][]

2.后序遍历

template <typename T, typename VST>     //元素类型、操作器
    void travPre_R(BinNodePosi(T) x, VST& visit)   {   //二叉树后序遍历算法
        if (!x) return;
        travPre_R(x->lChild, visit);
        travPre_R(x->rChild, visit);
        visit( x->data );
    }

![70 2][]

3.中序遍历

template <typename T, typename VST>     //元素类型、操作器
    void travPre_R(BinNodePosi(T) x, VST& visit)   {   //二叉树中序遍历算法
        if (!x) return;
        travPre_R(x->lChild, visit);
        visit( x->data );
        travPre_R(x->rChild, visit);    
    }

![70 3][]

层次遍历

在所谓广度优先遍历或层次遍历(level-order traversal)中,确定节点访问次序的原则可概括为“先上后下、先左后右”——先访问树根,再依次是左孩子、右孩子、左孩子的左孩子、左孩子的右孩子、右孩子的左孩子、右孩子的右孩子、...,依此类推。

![70 4][]

迭代版层次遍历需要使用与栈对称的**队列**结构

二叉树层次遍历算法：

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); //右孩子入队
        } 
    }

![70 5][]

\*补充

完全二叉树

![70 6][]

满二叉树

![70 7][]

[70]: /images/20220518/87538fc87bbb4bce8d2ce9667b5a00bd.png
[70 1]: /images/20220518/f43d239272d04142a76deadba014e6a9.png
[70 2]: /images/20220518/9354f16332194f99b6f445fb28c58fd0.png
[70 3]: /images/20220518/59ce249f9336452da0126c7c112d3083.png
[70 4]: /images/20220518/e2e3cf0295b34dc9bd52a6d542f31f47.png
[70 5]: /images/20220518/b9be01fc7e0742d18b1392da2a386255.png
[70 6]: /images/20220518/0644df5966a64f06b374dc52e2f4c3e5.png
[70 7]: /images/20220518/7dabb18fb6a54aa686cc3cf2cc647eb2.png