非遞迴遍歷二叉樹

遍歷二叉樹的非遞迴演算法

編寫的方法：根據樹中結點的遍歷規律及順序直接寫出其非遞迴演算法。

先序非遞迴演算法

【思路】

假設：t是要遍歷樹的根指標，若t!=null

對於非遞迴演算法，引入棧模擬遞迴工作棧，初始時棧為空。

問題：如何用棧來儲存資訊，使得在先序遍歷過左子樹後，能利用棧頂資訊獲取t的右子樹的根指標？

方法1：訪問t->data後，將t入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為t，出棧，再先序遍歷t的右子樹。

方法2：訪問t->data後，將t->rchild入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為t->rchild，出棧，遍歷以該指標為根的子樹。

【演算法1】

voidpreorder(bitreet,status(*visit)(elemtypee))

if(!stackempty(s))}}

【演算法2】

voidpreorder(bitreet,status(*visit)(elemtypee))

if(!stackempty(s))}}

進一步考慮：對於處理流程中的迴圈體的直到型、當型+直到型的實現。

中序非遞迴演算法

【思路】

t是要遍歷樹的根指標，中序遍歷要求在遍歷完左子樹後，訪問根，再遍歷右子樹。

問題：如何用棧來儲存資訊，使得在中序遍歷過左子樹後，能利用棧頂資訊獲取t指標？

方法：先將t入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為t，出棧，訪問t->data，再中序遍歷t的右子樹。

【演算法】

voidinorder(bitreet,status(*visit)(elemtypee))

if(!stackempty(s))}}

進一步考慮：對於處理流程中的迴圈體的直到型、當型+直到型的實現。

後序非遞迴演算法

【思路】

t是要遍歷樹的根指標，後序遍歷要求在遍歷完左右子樹後，再訪問根。需要判斷根結點的左右子樹是否均遍歷過。

可採用標記法，結點入棧時，配乙個標誌tag一同入棧(0：遍歷左子樹前的現場保護，1：遍歷右子樹前的現場保護)。

首先將t和tag(為0)入棧，遍歷左子樹；返回後，修改棧頂tag為1，遍歷右子樹；最後訪問根結點。

typedefstructstackelementstackelemtype;

【演算法】

voidpostorder(bitreet,status(*visit)(elemtypee))

while(!stackempty(s)&&gettoptag(s)==1)

if(!stackempty(s))elsebreak;}}

最易懂的二叉樹的遞迴和非遞迴實驗建立一顆用作實驗的二叉樹 1 先根序遍歷 2 中根序遍歷 4 後根序遍歷 5 測試主函式 7 當然，這是最笨的一種生成特定二叉樹的方法所謂先根遍歷，也就是從先遍歷根節點，然後遍歷左子樹，最後右子樹。遞迴的非常簡單遞迴呼叫看起來並沒什麼難點，接下來就...

二叉樹先根序後根序中根序遍歷的速演算法解題技巧經過研究我找出了一種不用畫圖，由先後根序遍歷和中根序遍歷迅速確定遍歷結果的辦法。謹以此文獻給智商與我同級而又不得不研究演算法的朋友。抽象思維太差，用例子來說明吧。下面這個是後根遍歷的演算法。例1 已知某二叉樹的先根序遍歷為abcdefg,中根...

飛機票訂票系統二一四年六月二叉數的遍歷 1 問題陳述二叉樹的中序前序後序的遞迴非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。限1 人完成二叉樹的前序後序的遞迴非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。先序遍歷二叉樹演算法若二叉樹為...