數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷

數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷樹()是n(n0)個結(jié)點(diǎn)的有限集T，其中：有且僅有一個特定的結(jié)點(diǎn)，稱為樹的根()當(dāng)n>1時，其余結(jié)點(diǎn)可分為m(m>0)個互不相交的有限集T12,……，其中每一個集合本身又是一棵樹，稱為根的子樹()?；仡櫳瞎?jié)課主要內(nèi)容二叉樹是n(n0)個結(jié)點(diǎn)的有限集，它或為空樹(n=0)，或由一個根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。順序存儲結(jié)構(gòu)按滿二叉樹的結(jié)點(diǎn)層次編號，依次存放二叉樹中的數(shù)據(jù)元素鏈?zhǔn)酱鎯Y(jié)構(gòu)使用二叉鏈表存儲，通過指針指向左右子樹。;{;*,*},*;;lchilddatarchildACBED樹ABCDE二叉樹A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對應(yīng)存儲存儲解釋解釋遍歷——按一定規(guī)律走遍樹的各個結(jié)點(diǎn)，且使每一結(jié)點(diǎn)僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點(diǎn)的一個線性排列。常用方法先序遍歷：先訪問根結(jié)點(diǎn),然后分別先序遍歷左子樹、先序遍歷右子樹。中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹。后序遍歷：先后序遍歷左、后序遍歷右子樹，然后訪問根結(jié)點(diǎn)5.2二叉樹的遍歷二叉樹是n(n0)個結(jié)點(diǎn)的有限集，它或為空樹(0)，或由一個根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。ADBC根左右A根左右根左右>B>>D>>C根左右先序遍歷序列：ABDC先序遍歷:ABDC先序遍歷:算法過程描述如下：1.若二叉樹為空，則返回①訪問根結(jié)點(diǎn)②先序遍歷左子樹③先序遍歷右子樹(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例：對如下二叉樹進(jìn)行前序遍歷的結(jié)果為ABDCEFFCADEGBABDECFFCADBEG左根右B左根右左根右>A>>D>>C左根右中序遍歷序列：BDAC中序遍歷:ADBCBDAC中序遍歷:算法過程描述如下：1.若二叉樹為空，則返回①中序遍歷左子樹②訪問根結(jié)點(diǎn)③中序遍歷右子樹(T){(){

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

}}(>);(>);("%2c">);例：對如下二叉樹進(jìn)行后序遍歷的結(jié)果為ABDCEFFCADEGBDEBFCAABDCGEF-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef例1：已知一棵二叉樹的先序序列為，中序序列為，試構(gòu)造該二叉樹。基本思想：在先序序列中找根，在中序序列中分左右。先序序列為：中序序列為：CEDABDEBCAECBDA練習(xí)先序序列為：ABDECFHG中序序列為：DBEAHFCG構(gòu)造一棵二叉樹。答案DEGFBCAH例2：已知一棵二叉樹的后序序列為，中序序列為，試構(gòu)造該二叉樹?；舅枷耄涸诤笮蛐蛄兄姓腋谥行蛐蛄兄蟹肿笥?。后序序列為：中序序列為：DABCEDEBCAECBDA練習(xí)后序序列為：DEBHFGCA中序序列為：DBEAHFCG構(gòu)造一棵二叉樹。答案DEGFBCAH(1)先序遍歷的非遞歸算法令p指向根結(jié)點(diǎn)。若p不為空，訪問p所指結(jié)點(diǎn)，并將p壓入棧中。若p為空，轉(zhuǎn)4。將p所指結(jié)點(diǎn)的左孩子壓入棧，轉(zhuǎn)2。從棧中彈出棧頂結(jié)點(diǎn)，令p指向所彈出結(jié)點(diǎn)的右孩子；轉(zhuǎn)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指向根結(jié)點(diǎn)。若p不為空，將p壓入棧中。若p為空，轉(zhuǎn)4。將p所指結(jié)點(diǎn)的左孩子壓入棧，轉(zhuǎn)2。從棧中彈出棧頂結(jié)點(diǎn)，訪問所彈出結(jié)點(diǎn)，令p指向所彈出結(jié)點(diǎn)的右孩子；轉(zhuǎn)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)遍歷算法應(yīng)用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：ABCDEGF求二叉樹深度算法ABCDEFG統(tǒng)計二叉樹中葉子結(jié)點(diǎn)個數(shù)算法4.樹和森林的遍歷樹的遍歷先根（序）遍歷：先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)按層次遍歷：先訪問第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，……第n層的結(jié)點(diǎn)ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIG