導航:首頁 > 編程語言 > java二叉樹求深度的非遞歸演算法

java二叉樹求深度的非遞歸演算法

發布時間:2023-02-16 17:21:39

㈠ 用JAVA語言實現二叉樹的層次遍歷的非遞歸演算法及查找演算法。

先序非遞歸演算法
【思路】
假設:T是要遍歷樹的根指針,若T != NULL
對於非遞歸演算法,引入棧模擬遞歸工作棧,初始時棧為空。
問題:如何用棧來保存信息,使得在先序遍歷過左子樹後,能利用棧頂信息獲取T的右子樹的根指針?
方法1:訪問T->data後,將T入棧,遍歷左子樹;遍歷完左子樹返回時,棧頂元素應為T,出棧,再先序遍歷T的右子樹。
方法2:訪問T->data後,將T->rchild入棧,遍歷左子樹;遍歷完左子樹返回時,棧頂元素應為T->rchild,出棧,遍歷以該指針為根的子樹。
【演算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基於方法一
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【演算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基於方法二
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
進一步考慮:對於處理流程中的循環體的直到型、當型+直到型的實現。

中序非遞歸演算法
【思路】
T是要遍歷樹的根指針,中序遍歷要求在遍歷完左子樹後,訪問根,再遍歷右子樹。
問題:如何用棧來保存信息,使得在中序遍歷過左子樹後,能利用棧頂信息獲取T指針?
方法:先將T入棧,遍歷左子樹;遍歷完左子樹返回時,棧頂元素應為T,出棧,訪問T->data,再中序遍歷T的右子樹。
【演算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
進一步考慮:對於處理流程中的循環體的直到型、當型+直到型的實現。

後序非遞歸演算法
【思路】
T是要遍歷樹的根指針,後序遍歷要求在遍歷完左右子樹後,再訪問根。需要判斷根結點的左右子樹是否均遍歷過。
可採用標記法,結點入棧時,配一個標志tag一同入棧(0:遍歷左子樹前的現場保護,1:遍歷右子樹前的現場保護)。
首先將T和tag(為0)入棧,遍歷左子樹;返回後,修改棧頂tag為1,遍歷右子樹;最後訪問根結點。 [Page]
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【演算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 設置棧頂標記
T = GetTopPointer(S); // 取棧頂保存的指針
T = T->rchild;
}else break;
}
}

閱讀全文

與java二叉樹求深度的非遞歸演算法相關的資料

熱點內容
哪個編程的電動積木好 瀏覽:420
java的編譯程序是什麼意思 瀏覽:530
ps抽出工具安裝 瀏覽:555
溫州銀行網貸在哪個app 瀏覽:307
qq郵箱怎麼把文件另存 瀏覽:489
不加qq怎麼發文件 瀏覽:183
征途app安裝包在哪裡 瀏覽:291
做網站有哪些公司 瀏覽:332
為什麼win10系統刪除不了文件夾里 瀏覽:367
華為網站打不開是什麼原因 瀏覽:335
為什麼編程時大腦空空 瀏覽:36
電腦上怎麼保存ppt文件 瀏覽:907
男性董事總人數怎麼獲得數據 瀏覽:475
java矩陣特徵分解 瀏覽:98
gxworks2怎麼給plc編程 瀏覽:6
文件編輯器怎麼安裝軟體 瀏覽:256
嘉興長沙少兒編程培訓班哪個好 瀏覽:701
win10我的文檔圖標不見了 瀏覽:306
處理linux虛擬機亂碼 瀏覽:745
python開發編程軟體如何升級程序 瀏覽:53

友情鏈接