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

網站建設、成都網站建設的開發，更需要了解用戶，從用戶角度來建設網站，獲得較好的用戶體驗。成都創新互聯公司多年互聯網經驗，見的多，溝通容易、能幫助客戶提出的運營建議。作為成都一家網絡公司，打造的就是網站建設產品直銷的概念。選擇成都創新互聯公司，不只是建站，我們把建站作為產品，不斷的更新、完善，讓每位來訪用戶感受到浩方產品的價值服務。

    棧的特點（后進先出）

    非遞歸實現二叉樹的前序遍歷：

    原理如圖所示：

    參考代碼如下：

    void _PrevOrder(Node* root)//非遞歸實現前序遍歷

    {

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);

    }

        }

    }

    非遞歸實現二叉樹的中序遍歷

    原理：

   先從二叉樹的最左邊進行遍歷（1、2、3），且一邊遍歷，一邊入棧，當當到達結點3時，因為3的左右子樹都為空，此時需彈出結點3，棧頂元素變為2，再遍歷2的右子樹的左結點，因為4的左右子樹都為空，此時需彈出2，壓人4，左子樹已遍歷結束，彈出4，再彈出1，依照遍歷左子樹，遍歷右子樹。

    參考代碼如下：

    void _InOrder(Node* root)//非遞歸實現中序遍歷

    {

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;

        }

    }

    非遞歸實現二叉樹的后序遍歷

    步驟：

    1、借助棧實現后序遍歷，先找到最左邊且為最下邊的結點3（一邊找，一邊入棧）

    2、若3沒有右子樹，則彈出3且打印結點3，還需要引入一個指向當前彈出結點的指針prev

    3、若3有右子樹，則需要遍歷右子樹，遍歷結束才可以打印并彈出結點3，重復此三步驟可完成后序遍歷。

    參考代碼如下：

    void _PosOrder(Node* root)//非遞歸實現后序遍歷

    {

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;

}

}

    }

另外有需要云服務器可以了解下創新互聯scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

本文名稱：非遞歸實現二叉樹的遍歷（前序、中序、后序）-創新互聯
地址分享：http://vcdvsql.cn/article4/ieioe.html

成都網站建設公司_創新互聯，為您提供網站改版、網站內鏈、企業網站制作、云服務器、關鍵詞優化、建站公司

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯