【文章內(nèi)容簡介】 (T)。 (()。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 1 . 先根遍歷操作的非遞歸實現(xiàn) 基本步驟： ③ 對當前訪問結(jié)點的非空左孩子結(jié)點相繼依次訪問，并將當前訪問結(jié)點的非空右孩子結(jié)點壓入棧內(nèi)； ④ 重復(fù)執(zhí)行步驟②和③，直到棧為空為止。 While(T!=null) { } if (()!=null) (()。 if (()!=null) (()。 T=()。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 先根遍歷的非遞歸算法 (書 P161算法 ) LinkStack S=new LinkStack()。 T=(BiTreeNode)()。 (T)。 (()。 while(T!=null) { } if (()!=null) (()。 if (()!=null) (()。 T=()。 while(!()) { } public void preRootTraverse() { BiTreeNode T=root。 } if (T! =null) { } 時間復(fù)雜度： O(n) 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 2 . 中根遍歷操作的非遞歸實現(xiàn) 方法： 借助一個棧 來記載遍歷截長過程中所經(jīng)歷的而未被訪問的所有結(jié)點 主要思想： 從 非空 二叉樹的根結(jié)點出發(fā)，沿著該結(jié)點的左子樹向下搜索， 在搜索過程中將所遇到的每一個結(jié)點依次壓棧，直到二叉樹中最左下的結(jié)點壓棧為止，然后從棧中彈出棧頂結(jié)點并對其進行訪問，訪問完后再進入該結(jié)點的右子樹并用上述同樣的方法去遍歷該結(jié)點的右子樹，依此類推，直到二叉樹中所有的結(jié)點都被訪問為止。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 2 . 中根遍歷操作的非遞歸實現(xiàn) 基本步驟： ① 創(chuàng)建一個棧對象，根結(jié)點入棧； ② 若棧 頂結(jié)點 非空，則將棧頂結(jié)點的非空左孩子相繼進棧； LinkStack S=new LinkStack()。 while( ()!=null ) { } (T)。 ((BiTreeNode)().getLchild())。 ()。 //空結(jié)點出棧 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 2 . 中根遍歷操作的非遞歸實現(xiàn) 基本步驟： ③ 棧頂結(jié)點出棧并訪問非空棧頂 結(jié)點， 再 使該棧頂結(jié)點的非空右孩子結(jié)點入棧； ④ 重復(fù)執(zhí)行步驟②和③，直到棧為空為止。 if (!()) { } T=(BiTreeNode)()。 (())。 (())。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 中根遍歷的非遞歸算法 (書 P162算法 ) LinkStack S=new LinkStack()。 (T)。 while(!()) { } public void inRootTraverse() { BiTreeNode T=root。 } if (T! =null) { } while( ()!=null ) { } ((BiTreeNode)().getLchild())。 ()。 if (!()) { } T=(BiTreeNode)()。 (())。 (())。 時間復(fù)雜度： O(n) 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 3 . 后根遍歷操作的非遞歸實現(xiàn) 方法： 借助一個棧 來記載遍歷截長過程中所經(jīng)歷的而未被訪問的所有結(jié)點 。 引進 一個訪問標志變量 flag和一個結(jié)點指針 p。 其中： flag用來標記當前棧頂結(jié)點是否被訪問，當值為 true時，表示棧頂結(jié)點已被訪問；當值為 false時，表示當前棧頂結(jié)點未被訪問，指針p指向當前遍歷過程中最后一個被訪問的結(jié)點。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 3 .后根遍歷操作的非遞歸實現(xiàn) 基本步驟： ① 創(chuàng)建一個棧對象，根結(jié)點入棧 ， p賦初始值 null； ② 若棧 頂結(jié)點 非空，則將棧頂結(jié)點的非空左孩子相繼進棧； LinkStack S=new LinkStack()。 while( ()!=null ) { } (T)。 ((BiTreeNode)().getLchild())。 ()。 BiTreeNOde p=null。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 ③ 若棧非空，查看棧頂結(jié)點，若棧頂結(jié)點的右孩子為空，或者與 p相等，則將棧頂結(jié)點彈出棧并訪問它，同時使 p指向該結(jié)點，并置 flag值為 true；否則，將棧頂結(jié)點的右孩子壓入棧，并置 flag值為 false。 if (()==null ||()==p) { } else { } (())。 (())。 T=(BiTreeNode)()。 p=T。 flag=true。 flag=flase。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 3 . 后根遍歷操作的非遞歸實現(xiàn) 基本步驟： ④ 若 flag值為 true，則重復(fù)執(zhí)行步驟③；否則，重復(fù)執(zhí)行步驟②和③，直到棧為空為止。 while( !()) { ② while( !()) { ③ if (!flag) break。 } } 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 后根遍歷的非遞歸算法 (書 P163算法 ) public void postRootTraverse() { BiTreeNode T=root。 } if (T! =null) { } ① while( !()) { ② while( !()) { ③ if (!flag) break。 } } 時間復(fù)雜度：O(n) 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 4 . 層次遍歷操作的非遞歸實現(xiàn) 方法： 借助一個隊列 。 在遍歷開始時，首先將根結(jié)點入隊，然后每次從隊列中取出隊首元素進行處理，每處理一個結(jié)點，都是先訪問該結(jié)點，再按從左到右的順序把它的孩子結(jié)點依次入隊 。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 4 . 層次遍歷操作的非遞歸實現(xiàn) 基本步驟： ① 創(chuàng)建一個 鏈 隊列對象，根結(jié)點入隊； LinkStack L=new LinkQueue()。 (T)。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 4 . 層次遍歷操作的非遞歸實現(xiàn) 基本步驟： ② 若隊列非空， 重復(fù) 將隊首結(jié)點出隊并訪問該結(jié)點，再將該結(jié)點的非空左、右孩子結(jié)點依次入隊 ， 直到隊列為空為止。 while( !()) { } T=(BiTreeNode)()。 (())。 if (()!=null) (()。 if (()!=null) (()。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 層次遍歷的非遞歸算法 (書 P166算法 ) public void levelTraverse() { BiTreeNode T=root。 } if (T! =null) { } LinkStack L=new LinkQueue()。 (T)。 while( !()) { } T=(BiTreeNode)()。 (())。 if (()!=null) (()。 if (()!=null) (()。 時間復(fù)雜度： O(n) 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 二叉樹遍歷算法的應(yīng)用舉例 建立二叉樹 二叉樹的遍歷 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷應(yīng)用舉例 1. 在二叉樹上的查找某個結(jié)點 2. 計算二叉樹中結(jié)點的個數(shù) 3. 求二叉樹的深度 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 1. 在二叉樹上的查找某個結(jié)點 要求： 實現(xiàn)方法： 在以 T為根結(jié)點的二叉樹中查找值為x的結(jié)點，若找到，則返回該結(jié)點；否則，返回空值。 可在 先根 遍歷過程中進行查找，并將先根遍歷算法中的“ 訪問結(jié)點 ”的操作改為： 將根結(jié)點的值與 x進行比較 的操作 。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 1. 在二叉樹上的查找某個結(jié)點 實現(xiàn)步驟： 1)若二叉樹為空，則不存在這個結(jié)點，返回空值； 否則 ，將根結(jié)點的值與 x進行比較，若相等，則返回該結(jié)點 ； 2) 否則 在左子樹中進行查找，若找到，則返回找到的結(jié)點； 3) 否則 返回在右子樹中進行查找的結(jié)果。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 1. 在二叉樹上的查找某個結(jié)點 實現(xiàn)算法 (書 P166算法 )： public BiTreeNode searchNode(BiTreeNode T, Object x){ } if (T! =null) { } if (().equals(x)) return T。 else { } BiTreeNode lresult=searchNOde((),x)。 return lresult!=null?lresult:searchNOde((),x)。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷應(yīng)用舉例 1. 在二叉樹上的查找某個結(jié)點 2. 計算二叉樹中結(jié)點的個數(shù) 3. 求二叉樹的深度 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 要求： 實現(xiàn)方法 : 計算 以 T為根結(jié)點的二叉樹