二叉树之先序遍历

墨蓝 2021-11-09 00:32 291阅读 0赞

二叉树不同于列表、链表、栈、队列这些线性结构，也不同于图这种非线性结构，它属于半线性结构。我们在搞二叉树的时候不要从轮子造起，而要善于引用此前的工作成果，转化成以前已经玩烂的线性结构。

根据树根、左娃、右娃的先后顺序，分别有先序遍历(V-L-R)、中序遍历(L-V-R)、后序遍历(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 traverse(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 );
        } 
    }

示意图：

![1705789-20190715085504484-775706869.png][]

先序遍历的迭代实现方法（栈）二：

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->lChild);
            x=x->rChild; 
        }
    }
    
    void traverse(BinNodePosi(T) x, VST &visit )
    {
        stack <BinNodePosi(T)> S;
        while(true){  //以右子树为单位，逐批访问节点 
            visitAlongLeftBranch(x,visit,S);  //访问子树x的左侧链，右子树入栈 
            if(S.empty()) break;
            x=S.pop();
        }
    }

图示意：

![1705789-20190715091030191-1122927413.png][]

转载于:https://www.cnblogs.com/dynmi/p/11186989.html

[1705789-20190715085504484-775706869.png]: /images/20211108/312227809085434485caeed8626ba835.png
[1705789-20190715091030191-1122927413.png]: /images/20211108/d610fc737c674966931ce3c00e5a6401.png