數(shù)據(jù)結(jié)構(gòu)基本知識(shí)二叉樹遍歷備課講稿課件

數(shù)據(jù)結(jié)構(gòu)基本知識(shí)二叉樹遍歷3.二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)按滿二叉樹的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使用二叉鏈表存儲(chǔ)，通過(guò)指針指向左右子樹。typedefcharElemType;typedefstructBiTNode{

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;BiTreebt;lchilddatarchild

4.樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋遍歷——按一定規(guī)律走遍樹的各個(gè)結(jié)點(diǎn)，且使每一結(jié)點(diǎn)僅被訪問(wèn)一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹中所有結(jié)點(diǎn)的一個(gè)線性排列。常用方法先序遍歷：先訪問(wèn)根結(jié)點(diǎn),然后分別先序遍歷左子樹、先序遍歷右子樹。中序遍歷：先中序遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹。后序遍歷：先后序遍歷左、后序遍歷右子樹，然后訪問(wèn)根結(jié)點(diǎn)5.2二叉樹的遍歷

二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。ADBC根左右A根左右根左右>B>>D>>C根左右先序遍歷序列：ABDC先序遍歷:ABDC先序遍歷:算法過(guò)程描述如下：1.若二叉樹為空，則返回2.否則依次執(zhí)行①訪問(wèn)根結(jié)點(diǎn)②先序遍歷左子樹

③先序遍歷右子樹voidPreOrder(BiTreeT){if(T!=NULL){

printf("%3c",T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);}}typedefstructBiTNode{

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;1.voidpre(BiTreeT)2.{if(T!=NULL)3.{printf("%3c",T->data);4.pre(T->L);5.pre(T->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例：對(duì)如下二叉樹進(jìn)行前序遍歷的結(jié)果為ABDCEFFCADEGBABDECFFCADBEG左根右B左根右左根右>A>>D>>C左根右中序遍歷序列：BDAC中序遍歷:ADBCBDAC中序遍歷:算法過(guò)程描述如下：1.若二叉樹為空，則返回2.否則依次執(zhí)行①中序遍歷左子樹②訪問(wèn)根結(jié)點(diǎn)③中序遍歷右子樹voidInOrder(BiTreeT){if(T!=NULL){

}}InOrder(T->lchild);printf("%3c",T->data);InOrder(T->rchild);typedefstructBiTNode{

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;例：對(duì)如下二叉樹進(jìn)行中序遍歷的結(jié)果為ABDCEFFCADEGBDBEAFCACBDFEGADBC左右根左右根左右根>A>>D>>C左右根后序遍歷序列：DBCA后序遍歷:BDBCA后序遍歷:算法過(guò)程描述如下：1.若二叉樹為空，則返回2.否則依次執(zhí)行①后序遍歷左子樹②后序遍歷右子樹③訪問(wèn)根結(jié)點(diǎn)voidPostOrder(BiTreeT){if(T!=NULL){

}}PostOrder(T->lchild);PostOrder(T->rchild);printf("%2c",T->data);例：對(duì)如下二叉樹進(jìn)行后序遍歷的結(jié)果為ABDCEFFCADEGBDEBFCAABDCGEF-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef例1：已知一棵二叉樹的先序序列為CEDBA，中序序列為DEBAC，試構(gòu)造該二叉樹。基本思想：在先序序列中找根，在中序序列中分左右。DEBA先序序列為：中序序列為：CEDABDEBCAECBABDA練習(xí)先序序列為：ABDECFHG中序序列為：DBEAHFCG構(gòu)造一棵二叉樹。答案DEGFBCAH例2：已知一棵二叉樹的后序序列為DABEC，中序序列為DEBAC，試構(gòu)造該二叉樹?；舅枷耄涸诤笮蛐蛄兄姓腋?，在中序序列中分左右。DEBA后序序列為：中序序列為：DABCEDEBCAECBABDA練習(xí)后序序列為：DEBHFGCA中序序列為：DBEAHFCG構(gòu)造一棵二叉樹。答案DEGFBCAH2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹先序遍歷的非遞歸算法(1)先序遍歷的非遞歸算法令p指向根結(jié)點(diǎn)。若p不為空，訪問(wèn)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。2.二叉樹先序遍歷的非遞歸算法ABCDEFGpiP->A(1)訪問(wèn)：AABCDEFGpiP->AP->B(2)訪問(wèn)：ABABCDEFGpiP->AP->BP->C(3)訪問(wèn)：ABCABCDEFGpiP->AP->B(4)訪問(wèn)：ABCABCDEFGiP->AP->DP->E訪問(wèn)：ABCDEp(7)p=NULLABCDEFGiP->A(5)訪問(wèn)：ABCp=NULLABCDEFGiP->AP->D(6)訪問(wèn)：ABCDABCDEFGiP->AP->D訪問(wèn)：ABCDEp(8)ABCDEFGiP->AP->F訪問(wèn)：ABCDEGFp(12)ABCDEFGiP->AP->DP->G訪問(wèn)：ABCDEGp(9)ABCDEFGiP->A訪問(wèn)：ABCDEGp(11)ABCDEFGiP->AP->D訪問(wèn)：ABCDEGp(10)ABCDEFGiP->A訪問(wèn)：ABCDEGFp(13)ABCDEFGi訪問(wèn)：ABCDEGFp=NULL(14)2.二叉樹先序遍歷的非遞歸算法(2)中序遍歷的非遞歸算法令p指向根結(jié)點(diǎn)。若p不為空，將p壓入棧中。若p為空，轉(zhuǎn)4。將p所指結(jié)點(diǎn)的左孩子壓入棧，轉(zhuǎn)2。從棧中彈出棧頂結(jié)點(diǎn)，訪問(wèn)所彈出結(jié)點(diǎn)，令p指向所彈出結(jié)點(diǎn)的右孩子；轉(zhuǎn)2。2.二叉樹中序遍歷的非遞歸算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問(wèn)：C(4)pABCDEFGiP->A訪問(wèn)：CB(5)ABCDEFGiP->AP->D訪問(wèn)：CBp(6)ABCDEFGiP->AP->DP->E訪問(wèn)：CBp(7)ABCDEFGiP->AP->D訪問(wèn)：CBEp(8)ABCDEFGiP->AP->DP->G訪問(wèn)：CBEP=NULL(9)ABCDEFGiP->A訪問(wèn)：CBEGDp(11)ABCDEFGiP->AP->F訪問(wèn)：CBEGDp(12)ABCDEFGiP->AP->D訪問(wèn)：CBEGp(10)ABCDEFGiP->A訪問(wèn)：CBEGDFp=NULL(13)ABCDEFGi訪問(wèn)：CBEGDFAp(14)遍歷算法應(yīng)用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：ABCDEGF求二叉樹深度算法ABCDEFG統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)算法3.二叉樹的層次遍歷4.樹和森林的遍歷樹的遍歷先根（序）遍歷：先訪問(wèn)樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問(wèn)根結(jié)點(diǎn)按層次遍歷：先訪問(wèn)第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，……第n層的結(jié)點(diǎn)ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGC