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

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

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

二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。遍歷——按一定規(guī)律走遍樹的各個結(jié)點，且使每一結(jié)點僅被訪問一次ADBC根左右A根左右根左右>B>>D>>C根左右先序遍歷序列：ABDC先序遍歷:ABDCADBC根左右A根數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷備課講稿課件先序遍歷:算法過程描述如下：1.若二叉樹為空，則返回2.否則依次執(zhí)行①訪問根結(jié)點②先序遍歷左子樹

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

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

PreOrder(T->lchild);

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

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;先序遍歷:算法過程描述如下：voidPreOrder(Bi1.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);先序序列：ABDC1.voidpre(BiTreeT)主程序Pre(例：對如下二叉樹進(jìn)行前序遍歷的結(jié)果為ABDCEFFCADEGBABDECFFCADBEG例：對如下二叉樹進(jìn)行前序遍歷的結(jié)果為ABDCEFFCADEG左根右B左根右左根右>A>>D>>C左根右中序遍歷序列：BDAC中序遍歷:ADBCBDAC左根右B左根數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷備課講稿課件中序遍歷:算法過程描述如下：1.若二叉樹為空，則返回2.否則依次執(zhí)行①中序遍歷左子樹②訪問根結(jié)點③中序遍歷右子樹voidInOrder(BiTreeT){if(T!=NULL){

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

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;中序遍歷:算法過程描述如下：voidInOrder(BiT例：對如下二叉樹進(jìn)行中序遍歷的結(jié)果為ABDCEFFCADEGBDBEAFCACBDFEG例：對如下二叉樹進(jìn)行中序遍歷的結(jié)果為ABDCEFFCADEGADBC左右根左右根左右根>A>>D>>C左右根后序遍歷序列：DBCA后序遍歷:BDBCAADBC左右數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷備課講稿課件后序遍歷:算法過程描述如下：1.若二叉樹為空，則返回2.否則依次執(zhí)行①后序遍歷左子樹②后序遍歷右子樹③訪問根結(jié)點voidPostOrder(BiTreeT){if(T!=NULL){

}}PostOrder(T->lchild);PostOrder(T->rchild);printf("%2c",T->data);后序遍歷:算法過程描述如下：voidPostOrder(B例：對如下二叉樹進(jìn)行后序遍歷的結(jié)果為ABDCEFFCADEGBDEBFCAABDCGEF例：對如下二叉樹進(jìn)行后序遍歷的結(jié)果為ABDCEFFCADEG-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*例1：已知一棵二叉樹的先序序列為CEDBA，中序序列為DEBAC，試構(gòu)造該二叉樹?；舅枷耄涸谙刃蛐蛄兄姓腋?，在中序序列中分左右。DEBA先序序列為：中序序列為：CEDABDEBCAECBABDA例1：已知一棵二叉樹的先序序列為CEDBA，中序序列為DEB練習(xí)先序序列為：ABDECFHG中序序列為：DBEAHFCG構(gòu)造一棵二叉樹。答案練習(xí)DEGFBCAHDEGFBCAH例2：已知一棵二叉樹的后序序列為DABEC，中序序列為DEBAC，試構(gòu)造該二叉樹。基本思想：在后序序列中找根，在中序序列中分左右。DEBA后序序列為：中序序列為：DABCEDEBCAECBABDA例2：已知一棵二叉樹的后序序列為DABEC，中序序列為DEB練習(xí)后序序列為：DEBHFGCA中序序列為：DBEAHFCG構(gòu)造一棵二叉樹。答案練習(xí)DEGFBCAHDEGFBCAH2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹先序遍歷的非遞歸算法(1)先序遍歷的非遞歸算法令p指向根結(jié)點。若p不為空，訪問p所指結(jié)點，并將p壓入棧中。若p為空，轉(zhuǎn)4。將p所指結(jié)點的左孩子壓入棧，轉(zhuǎn)2。從棧中彈出棧頂結(jié)點，令p指向所彈出結(jié)點的右孩子；轉(zhuǎn)2。2.二叉樹先序遍歷的非遞歸算法(1)先序遍歷的非遞歸算法2.二叉樹先序遍歷的非遞歸算法ABCDEFGpiP->A(1)訪問：AABCDEFGpiP->AP->B(2)訪問：ABABCDEFGpiP->AP->BP->C(3)訪問：ABCABCDEFGpiP->AP->B(4)訪問：ABC2.二叉樹先序遍歷的非遞歸算法ABCDEFGpiP->A(1ABCDEFGiP->AP->DP->E訪問：ABCDEp(7)p=NULLABCDEFGiP->A(5)訪問：ABCp=NULLABCDEFGiP->AP->D(6)訪問：ABCDABCDEFGiP->AP->D訪問：ABCDEp(8)ABCDEFGiP->AP->DP->E訪問：ABCDEp(ABCDEFGiP->AP->F訪問：ABCDEGFp(12)ABCDEFGiP->AP->DP->G訪問：ABCDEGp(9)ABCDEFGiP->A訪問：ABCDEGp(11)ABCDEFGiP->AP->D訪問：ABCDEGp(10)ABCDEFGiP->AP->F訪問：ABCDEGFp(12ABCDEFGiP->A訪問：ABCDEGFp(13)ABCDEFGi訪問：ABCDEGFp=NULL(14)ABCDEFGiP->A訪問：ABCDEGFp(13)ABC2.二叉樹先序遍歷的非遞歸算法(2)中序遍歷的非遞歸算法令p指向根結(jié)點。若p不為空，將p壓入棧中。若p為空，轉(zhuǎn)4。將p所指結(jié)點的左孩子壓入棧，轉(zhuǎn)2。從棧中彈出棧頂結(jié)點，訪問所彈出結(jié)點，令p指向所彈出結(jié)點的右孩子；轉(zhuǎn)2。2.二叉樹先序遍歷的非遞歸算法(2)中序遍歷的非遞歸算法2.二叉樹中序遍歷的非遞歸算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問：C(4)2.二叉樹中序遍歷的非遞歸算法ABCDEFGpiP->A(1pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)pABCDEFGiP->A訪問：CB(5)ABCDEFGiABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)ABCDEFGiP->AP->D訪問：CBEGp(10)ABCDEFGiP->AP->DP->G訪問：CBEP=ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)ABCDEFGiP->A訪問：CBEGDFp=NU遍歷算法應(yīng)用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：ABCDEGF求二叉樹深度算法ABCDEFG統(tǒng)計二叉樹中葉子結(jié)點個數(shù)算法遍歷算法應(yīng)用求二叉樹深度算法ABCDEFG統(tǒng)計二叉樹中葉子結(jié)3.二叉樹的層次遍歷3.二叉樹的層次遍歷4.樹和森林的遍歷樹的遍歷先根（序）遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點按層次遍歷：先訪問第一層上的結(jié)點，然后依次遍歷第二層，……第n層的結(jié)點4.樹和森林的遍歷ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNOABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：4.樹和森林的遍歷森林的遍歷先根（序）遍歷：先訪問第一顆樹的根結(jié)點先根遍歷第一顆樹中根結(jié)點的子樹森林先根遍歷除去第一顆樹之后剩余樹構(gòu)成的森林后根（序）遍歷后跟遍歷第一顆樹的根結(jié)點的子樹森林訪問第一顆樹的根結(jié)點后跟遍歷除去第一顆樹之后剩余樹構(gòu)成的森林4.樹和森林的遍歷此課件下載可自行編輯修改，僅供參考！

感謝您的支持，我們努力做得更好！謝謝此課件下載可自行編輯修改，僅供參考！

感謝您的支持，我們努力數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷3.二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素鏈?zhǔn)酱鎯Y(jié)構(gòu)使用二叉鏈表存儲，通過指針指向左右子樹。typedefcharElemType;typedefstructBiTNode{

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

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

二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。遍歷——按一定規(guī)律走遍樹的各個結(jié)點，且使每一結(jié)點僅被訪問一次ADBC根左右A根左右根左右>B>>D>>C根左右先序遍歷序列：ABDC先序遍歷:ABDCADBC根左右A根數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷備課講稿課件先序遍歷:算法過程描述如下：1.若二叉樹為空，則返回2.否則依次執(zhí)行①訪問根結(jié)點②先序遍歷左子樹

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

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

PreOrder(T->lchild);

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

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;先序遍歷:算法過程描述如下：voidPreOrder(Bi1.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);先序序列：ABDC1.voidpre(BiTreeT)主程序Pre(例：對如下二叉樹進(jìn)行前序遍歷的結(jié)果為ABDCEFFCADEGBABDECFFCADBEG例：對如下二叉樹進(jìn)行前序遍歷的結(jié)果為ABDCEFFCADEG左根右B左根右左根右>A>>D>>C左根右中序遍歷序列：BDAC中序遍歷:ADBCBDAC左根右B左根數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷備課講稿課件中序遍歷:算法過程描述如下：1.若二叉樹為空，則返回2.否則依次執(zhí)行①中序遍歷左子樹②訪問根結(jié)點③中序遍歷右子樹voidInOrder(BiTreeT){if(T!=NULL){

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

ElemTypedata;structBiTNode*lchild,*rchild}BiTNode,*BiTree;中序遍歷:算法過程描述如下：voidInOrder(BiT例：對如下二叉樹進(jìn)行中序遍歷的結(jié)果為ABDCEFFCADEGBDBEAFCACBDFEG例：對如下二叉樹進(jìn)行中序遍歷的結(jié)果為ABDCEFFCADEGADBC左右根左右根左右根>A>>D>>C左右根后序遍歷序列：DBCA后序遍歷:BDBCAADBC左右數(shù)據(jù)結(jié)構(gòu)基本知識二叉樹遍歷備課講稿課件后序遍歷:算法過程描述如下：1.若二叉樹為空，則返回2.否則依次執(zhí)行①后序遍歷左子樹②后序遍歷右子樹③訪問根結(jié)點voidPostOrder(BiTreeT){if(T!=NULL){

}}PostOrder(T->lchild);PostOrder(T->rchild);printf("%2c",T->data);后序遍歷:算法過程描述如下：voidPostOrder(B例：對如下二叉樹進(jìn)行后序遍歷的結(jié)果為ABDCEFFCADEGBDEBFCAABDCGEF例：對如下二叉樹進(jìn)行后序遍歷的結(jié)果為ABDCEFFCADEG-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：-+a*例1：已知一棵二叉樹的先序序列為CEDBA，中序序列為DEBAC，試構(gòu)造該二叉樹。基本思想：在先序序列中找根，在中序序列中分左右。DEBA先序序列為：中序序列為：CEDABDEBCAECBABDA例1：已知一棵二叉樹的先序序列為CEDBA，中序序列為DEB練習(xí)先序序列為：ABDECFHG中序序列為：DBEAHFCG構(gòu)造一棵二叉樹。答案練習(xí)DEGFBCAHDEGFBCAH例2：已知一棵二叉樹的后序序列為DABEC，中序序列為DEBAC，試構(gòu)造該二叉樹。基本思想：在后序序列中找根，在中序序列中分左右。DEBA后序序列為：中序序列為：DABCEDEBCAECBABDA例2：已知一棵二叉樹的后序序列為DABEC，中序序列為DEB練習(xí)后序序列為：DEBHFGCA中序序列為：DBEAHFCG構(gòu)造一棵二叉樹。答案練習(xí)DEGFBCAHDEGFBCAH2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹遍歷的非遞歸算法2.二叉樹先序遍歷的非遞歸算法(1)先序遍歷的非遞歸算法令p指向根結(jié)點。若p不為空，訪問p所指結(jié)點，并將p壓入棧中。若p為空，轉(zhuǎn)4。將p所指結(jié)點的左孩子壓入棧，轉(zhuǎn)2。從棧中彈出棧頂結(jié)點，令p指向所彈出結(jié)點的右孩子；轉(zhuǎn)2。2.二叉樹先序遍歷的非遞歸算法(1)先序遍歷的非遞歸算法2.二叉樹先序遍歷的非遞歸算法ABCDEFGpiP->A(1)訪問：AABCDEFGpiP->AP->B(2)訪問：ABABCDEFGpiP->AP->BP->C(3)訪問：ABCABCDEFGpiP->AP->B(4)訪問：ABC2.二叉樹先序遍歷的非遞歸算法ABCDEFGpiP->A(1ABCDEFGiP->AP->DP->E訪問：ABCDEp(7)p=NULLABCDEFGiP->A(5)訪問：ABCp=NULLABCDEFGiP->AP->D(6)訪問：ABCDABCDEFGiP->AP->D訪問：ABCDEp(8)ABCDEFGiP->AP->DP->E訪問：ABCDEp(ABCDEFGiP->AP->F訪問：ABCDEGFp(12)ABCDEFGiP->AP->DP->G訪問：ABCDEGp(9)ABCDEFGiP->A訪問：ABCDEGp(11)ABCDEFGiP->AP->D訪問：ABCDEGp(10)ABCDEFGiP->AP->F訪問：ABCDEGFp(12ABCDEFGiP->A訪問：ABCDEGFp(13)ABCDEFGi訪問：ABCDEGFp=NULL(14)ABCDEFGiP->A訪問：ABCDEGFp(13)ABC2.二叉樹先序遍歷的非遞歸算法(2)中序遍歷的非遞歸算法令p指向根結(jié)點。若p不為空，將p壓入棧中。若p為空，轉(zhuǎn)4。將p所指結(jié)點的左孩子壓入棧，轉(zhuǎn)2。從棧中彈出棧頂結(jié)點，訪問所彈出結(jié)點，令p指向所彈出結(jié)點的右孩子；轉(zhuǎn)2。2.二叉樹先序遍歷的非遞歸算法(2)中序遍歷的非遞歸算法2.二叉樹中序遍歷的非遞歸算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問：C(4)2.二叉樹中序遍歷的非遞歸算