第6章 樹和二叉樹2-遍歷二叉樹

1、嘉應(yīng)學(xué)院嘉應(yīng)學(xué)院數(shù)學(xué)系數(shù)學(xué)系數(shù)據(jù)結(jié)構(gòu)講義 遍歷二叉樹l二叉樹的遍歷方法l先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹。l中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹。l后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點。l按層次遍歷：從上到下、從左到右訪問各結(jié)點。DLRLDR、LRD、DLRRDL、RLD、DRLADBCD L RAD L RD L RBDCD L R先序遍歷序列：A B D C先序遍歷:ADBCL D RBL D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:ADBC L R DL R DL R DADCL R D后序遍歷序列： D

2、 B C A后序遍歷:B-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：-+ a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e fvoid preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D

3、);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C 非遞歸算法實現(xiàn)中序遍歷ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問：C(4)pABCDEFGiP-A訪問：C B(5)ABCDEFGiP-AP-D訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：C Bp(7)ABCDEFGiP-AP-D訪問：C B Ep(8)ABCDEFGiP-AP-

4、DP-G訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：C B E Gp(10)ABCDEFGiP-A訪問：C B E G D Fp=NULL(13)ABCDEFGi訪問：C B E G D F Ap(14)ABCDEFGi訪問：C B E G D F Ap=NULL(15)后序遍歷非遞歸算法l遍歷算法應(yīng)用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為： A B C D E G F ABCDEFG A B C D E F G 二叉樹的建立演示二叉樹的建立

5、演示l可使用一個順序存儲的隊列q100,存放還沒有處理的子樹的根結(jié)點的地址。注意,隊首和隊尾指針分別指向隊首結(jié)點和下次進(jìn)隊結(jié)點的存放位置。1) 首先把根節(jié)點入隊。2) 然后訪問隊頭的一個結(jié)點，再把該結(jié)點非空的左右子樹入隊。3) 如果隊列不空，重復(fù)2)。ch6_traverse.cl 當(dāng)用棧非遞歸實現(xiàn)樹的先序遍歷時，寫出遍歷右邊所表示的樹的全過程。像講義中那樣，寫出遍歷每一步棧中的數(shù)據(jù)。不是寫具體的實現(xiàn)代碼。ABCDEFGl按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為(表示空格)：ABCDEGF。并寫一個函數(shù)treenodes()統(tǒng)計該二叉樹的節(jié)點個數(shù)。如果有可能，寫一個輸出函數(shù)treeprint()用樹