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