樹(shù)的定義本是遞歸定義，所以采用遞歸的方法實(shí)現(xiàn)遍歷算法，更加讓人理解，且代碼簡(jiǎn)單方便。若采用非遞歸的方法實(shí)現(xiàn)，須得利用棧模擬實(shí)現(xiàn)。

創(chuàng)新互聯(lián)建站2013年開(kāi)創(chuàng)至今，先為寧強(qiáng)等服務(wù)建站，寧強(qiáng)等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為寧強(qiáng)企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。

    棧的特點(diǎn)（后進(jìn)先出）

    非遞歸實(shí)現(xiàn)二叉樹(shù)的前序遍歷：

    原理如圖所示：

    參考代碼如下：

    void _PrevOrder(Node* root)//非遞歸實(shí)現(xiàn)前序遍歷

    {

stack<Node*> s;

if(root == NULL)

    return;

s.push(root);

while (!s.empty())

{

    root = s.top();

    cout<<root->_data<<" ";

    s.pop();

    if (root->_right)

    {

s.push(root->_right);

    }

    if(root->_left)

    {

        s.push(root->_left);

    }

        }

    }

    

    非遞歸實(shí)現(xiàn)二叉樹(shù)的中序遍歷

    原理：

    先從二叉樹(shù)的最左邊進(jìn)行遍歷（1、2、3），且一邊遍歷，一邊入棧，當(dāng)當(dāng)?shù)竭_(dá)結(jié)點(diǎn)3時(shí)，因?yàn)?的左右子樹(shù)都為空，此時(shí)需彈出結(jié)點(diǎn)3，棧頂元素變?yōu)?，再遍歷2的右子樹(shù)的左結(jié)點(diǎn)，因?yàn)?的左右子樹(shù)都為空，此時(shí)需彈出2，壓人4，左子樹(shù)已遍歷結(jié)束，彈出4，再?gòu)棾?，依照遍歷左子樹(shù)，遍歷右子樹(shù)。  

    參考代碼如下：

    void _InOrder(Node* root)//非遞歸實(shí)現(xiàn)中序遍歷

    {

stack<Node*> s;

Node* cur = root;

while (cur || !s.empty())

{

    while (cur)

    {

        s.push(cur);

cur = cur->_left;

    }

    Node* top = s.top();

    cout<<top->_data<<" ";

    s.pop();

    cur = top->_right;

        }

    }

    非遞歸實(shí)現(xiàn)二叉樹(shù)的后序遍歷

    步驟：

    1、借助棧實(shí)現(xiàn)后序遍歷，先找到最左邊且為最下邊的結(jié)點(diǎn)3（一邊找，一邊入棧）

    2、若3沒(méi)有右子樹(shù)，則彈出3且打印結(jié)點(diǎn)3，還需要引入一個(gè)指向當(dāng)前彈出結(jié)點(diǎn)的指針prev

    3、若3有右子樹(shù)，則需要遍歷右子樹(shù)，遍歷結(jié)束才可以打印并彈出結(jié)點(diǎn)3，重復(fù)此三步驟可完成后序遍歷。      

    參考代碼如下：

    void _PosOrder(Node* root)//非遞歸實(shí)現(xiàn)后序遍歷 

    {

Node* cur = root;

Node* prev = NULL;

stack<Node*> s;

if(root == NULL)

return;

while (cur || !s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

cur = s.top();

if(cur->_right == NULL || cur->_right == prev)

{

cout<<cur->_data<<" ";

s.pop();

prev = cur;

cur = NULL;

}

else

{

cur = cur->_right;

}

}

    }

網(wǎng)站題目：非遞歸實(shí)現(xiàn)二叉樹(shù)的遍歷（前序、中序、后序）
瀏覽路徑：http://aaarwkj.com/article20/gpejco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、網(wǎng)站維護(hù)、微信公眾號(hào)、軟件開(kāi)發(fā)、網(wǎng)頁(yè)設(shè)計(jì)公司、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)