導航:首頁 > 編程語言 > 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二叉樹求深度的非遞歸演算法相關的資料

熱點內容
wps打開顯示文件轉換格式 瀏覽:186
coreldrawx4led排孔工具 瀏覽:682
表示文件路徑用什麼字元隔開 瀏覽:549
word2010宏安全性設置 瀏覽:820
win7硬碟密碼設置 瀏覽:240
電腦有沒有這個文件在哪裡查 瀏覽:340
金蘋果內容摘要 瀏覽:580
網站怎麼對接qq在線客服 瀏覽:437
solidworks曲面建模教程 瀏覽:69
數控編程和計算機有什麼區別 瀏覽:541
jsp與webservice 瀏覽:659
k歌的數據包括什麼 瀏覽:300
寬頻wifi怎麼查看網站 瀏覽:97
vlog網頁編程怎麼樣 瀏覽:598
自助下單網站多少錢搭建 瀏覽:130
國外裝修都用什麼app 瀏覽:326
qq同步助手修改密碼 瀏覽:850
電腦與電腦傳輸文件 瀏覽:403
處理網路數據應用哪個好 瀏覽:229
萬靈召喚最新版本 瀏覽:566

友情鏈接