數據結構基本知識二叉樹遍歷樹()是n(n0)個結點的有限集T，其中：有且僅有一個特定的結點，稱為樹的根()當n>1時，其余結點可分為m(m>0)個互不相交的有限集T12,……，其中每一個集合本身又是一棵樹，稱為根的子樹()。回顧上節課主要內容二叉樹是n(n0)個結點的有限集，它或為空樹(n=0)，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成。順序存儲結構按滿二叉樹的結點層次編號，依次存放二叉樹中的數據元素鏈式存儲結構使用二叉鏈表存儲，通過指針指向左右子樹。;{;*,*},*;;lchilddatarchildACBED樹ABCDE二叉樹A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對應存儲存儲解釋解釋遍歷——按一定規律走遍樹的各個結點，且使每一結點僅被訪問一次，即找一個完整而有規律的走法，以得到樹中所有結點的一個線性排列。常用方法先序遍歷：先訪問根結點,然后分別先序遍歷左子樹、先序遍歷右子樹。中序遍歷：先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹。后序遍歷：先后序遍歷左、后序遍歷右子樹，然后訪問根結點5.2二叉樹的遍歷二叉樹是n(n0)個結點的有限集，它或為空樹(0)，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成。ADBC根左右A根左右根左右>B>>D>>C根左右先序遍歷序列：ABDC先序遍歷:ABDC先序遍歷:算法過程描述如下：1.若二叉樹為空，則返回①訪問根結點②先序遍歷左子樹③先序遍歷右子樹(T){(){("%3c">);(>);(>);}}{;*,*},*;1.(T)2.{()3.{("%3c">);4.(>L);5.(>R);6.}7.}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC例：對如下二叉樹進行前序遍歷的結果為ABDCEFFCADEGBABDECFFCADBEG左根右B左根右左根右>A>>D>>C左根右中序遍歷序列：BDAC中序遍歷:ADBCBDAC中序遍歷:算法過程描述如下：1.若二叉樹為空，則返回①中序遍歷左子樹②訪問根結點③中序遍歷右子樹(T){(){

}}(>);("%3c">);(>);{;*,*},*;例：對如下二叉樹進行中序遍歷的結果為ABDCEFFCADEGBDBEAFCACBDFEGADBC左右根左右根左右根>A>>D>>C左右根后序遍歷序列：DBCA后序遍歷:BDBCA后序遍歷:算法過程描述如下：1.若二叉樹為空，則返回①后序遍歷左子樹②后序遍歷右子樹③訪問根結點(T){(){

}}(>);(>);("%2c">);例：對如下二叉樹進行后序遍歷的結果為ABDCEFFCADEGBDEBFCAABDCGEF-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef例1：已知一棵二叉樹的先序序列為，中序序列為，試構造該二叉樹。基本思想：在先序序列中找根，在中序序列中分左右。先序序列為：中序序列為：CEDABDEBCAECBDA練習先序序列為：ABDECFHG中序序列為：DBEAHFCG構造一棵二叉樹。答案DEGFBCAH例2：已知一棵二叉樹的后序序列為，中序序列為，試構造該二叉樹。基本思想：在后序序列中找根，在中序序列中分左右。后序序列為：中序序列為：DABCEDEBCAECBDA練習后序序列為：DEBHFGCA中序序列為：DBEAHFCG構造一棵二叉樹。答案DEGFBCAH(1)先序遍歷的非遞歸算法令p指向根結點。若p不為空，訪問p所指結點，并將p壓入棧中。若p為空，轉4。將p所指結點的左孩子壓入棧，轉2。從棧中彈出棧頂結點，令p指向所彈出結點的右孩子；轉2。ABCDEFGpiP->A(1)訪問：AABCDEFGpiP->AP->B(2)訪問：ABABCDEFGpiP->AP->BP->C(3)訪問：ABCABCDEFGpiP->AP->B(4)訪問：ABCABCDEFGiP->AP->DP->E訪問：ABCDEp(7)p=NULLABCDEFGiP->A(5)訪問：ABCp=NULLABCDEFGiP->AP->D(6)訪問：ABCDABCDEFGiP->AP->D訪問：ABCDEp(8)ABCDEFGiP->AP->F訪問：ABCDEGFp(12)ABCDEFGiP->AP->DP->G訪問：ABCDEGp(9)ABCDEFGiP->A訪問：ABCDEGp(11)ABCDEFGiP->AP->D訪問：ABCDEGp(10)ABCDEFGiP->A訪問：ABCDEGFp(13)ABCDEFGi訪問：ABCDEGFp=NULL(14)(2)中序遍歷的非遞歸算法令p指向根結點。若p不為空，將p壓入棧中。若p為空，轉4。將p所指結點的左孩子壓入棧，轉2。從棧中彈出棧頂結點，訪問所彈出結點，令p指向所彈出結點的右孩子；轉2。ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問：C(4)pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)ABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)ABCDEFGiP->AP->D訪問：CBEGp(10)ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)遍歷算法應用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：ABCDEGF求二叉樹深度算法ABCDEFG統計二叉樹中葉子結點個數算法4.樹和森林的遍歷樹的遍歷先根（序）遍歷：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結點按層次遍歷：先訪問第一層上的結點，然后依次遍歷第二層，……第n層的結點ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIG