第6章樹和二叉樹2課件

2.鏈?zhǔn)酱鎯Y(jié)構(gòu)*結(jié)點組成：lchilddatarchild從二叉樹的定義得知：二叉樹的節(jié)點由一個數(shù)據(jù)元素和分別指向其左右子樹的兩個分支構(gòu)成。這樣二叉樹的鏈表中至少有三個域其中：data為數(shù)據(jù)域；lchild為左指針域，放左子樹的地址；rchild為右指針域，放右子樹的地址；有時，為了便于找到結(jié)點的雙親，則還可在結(jié)點結(jié)構(gòu)中增加一個指向其雙親結(jié)點的指針域。lchilddataparentrchild*帶雙親的結(jié)點：.ABCDEFGABCDEFG^^^^^^^^BT：名字，根，入口.typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;*二叉鏈表的結(jié)構(gòu)定義：.三叉鏈表typedefstructnode{datatypedata;structnode*lchild,*rchild,*parent;}TT;lchilddataparentrchild*結(jié)點組成：*三叉鏈表的結(jié)構(gòu)定義：.ABCDEFGABCDEFG^^^^^^^^^.6.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹遍歷——按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列.有二叉樹的定義可知：二叉樹有三個基本單元組成：根結(jié)點，左子樹，右子樹。所以遍歷二叉樹就得依次遍歷這三個部分。.二叉樹的結(jié)構(gòu)：DLRLDR、LRD、DLRRDL、RLD、DRL方法：先序遍歷：先訪問根結(jié)點,然后分別遍歷左子樹、右子樹中序遍歷：先遍歷左子樹，然后訪問根結(jié)點，再遍歷右子樹后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點按層次遍歷：從上到下、從左到右訪問各結(jié)點*限定先左后右的次序.ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC1.先序遍歷:.ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC2.中序遍歷:.ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA3.后序遍歷:B.4.層次遍歷:ABCDEHIFGK層次遍歷的序列:ABCDEFGHIK.算法實現(xiàn)（遞歸算法）1.先序遍歷（DLR）算法實現(xiàn)：voidpreorder(BT*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}若二叉樹為空，遍歷結(jié)束。否則，1）訪問根結(jié)點2）先序遍歷左子樹3）先序遍歷右子樹.遞歸過程：voidpreorder(BT*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}主程序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.2.中序遍歷（LDR）算法實現(xiàn)：voidinorder(BT*bt){if(bt!=NULL){inorder(bt->lchild);printf("%d\t",bt->data);inorder(bt->rchild);}}若二叉樹為空，遍歷結(jié)束。否則，1）中序遍歷左子樹2）訪問根結(jié)點3）中序遍歷右子樹.3.后序遍歷（LRD）算法實現(xiàn)：voidpostorder(BT*bt){if(bt!=NULL){postorder(bt->lchild);postorder(bt->rchild);printf("%d\t",bt->data);}}若二叉樹為空，遍歷結(jié)束。否則，1）后序遍歷左子樹2）后序遍歷右子樹3）訪問根結(jié)點.遍歷二叉樹的非遞歸算法1.先序遍歷的非遞歸算法*提高運算效率基于棧先序遍歷的非遞歸算法：*引入棧保存每個結(jié)點的右指針?biāo)惴ǎ?）訪問結(jié)點2）結(jié)點的右指針入棧3）若結(jié)點的左指針不空，遍歷左子樹4）右指針出棧5）若結(jié)點的右指針不空，遍歷右子樹.遍歷二叉樹的非遞歸算法2.中序遍歷的非遞歸算法*引人棧保存每個結(jié)點及右指針，由于知道結(jié)點的指針便可知結(jié)點和其右指針，故只須結(jié)點的指針入棧算法：1）結(jié)點指針入棧2）若結(jié)點的左指針不空，遍歷左子樹3）指針出棧4）訪問結(jié)點，若結(jié)點的右指針不空，遍歷右子樹.算法實現(xiàn)：voidinorderse(BT*bt){inti=0;//棧的初始化BT*p,*s[M];//保存每個結(jié)點的指針的棧//p=bt;do{while(p!=NULL){s[i++]=p;//結(jié)點的指針入棧//p=p->lchild;//進入左子樹//}//左子樹為空，退出//if(i>0){p=s[--i];printf("%d\t",p->data);p=p->rchild;}}while(i>0||p!=NULL);//右子樹為空同時?？眨Y(jié)束//}.非遞歸算法棧操作圖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)ABCDEFGi訪問：CBEGDFAp=NULL(15).按層次遍歷須設(shè)隊列依次記錄結(jié)點的左孩子，右孩子結(jié)點的指針?biāo)惴ǎ?）根結(jié)點入隊2）根結(jié)點出隊訪問；若根結(jié)點的左，右指針非空，則依次入隊；3）重復(fù)，直至隊空.算法實現(xiàn)：voidlevelorder(BT*bt){intｉ，ｊ；//隊頭，隊尾//BT*bt，*q[MAXLEN]；p=bt；if(p!=NULL){i=1；q[i]=p；j=2；}while(i!=j)//隊空//{p=q[i];printf("%d\t",p->data);if(p->lchild!=NULL){q[j]=p->lchild;j++;}if(p->rchild!=NULL){q[j]=p->rchild;j++;}i++;}}.遍歷二叉樹的時間和空間復(fù)雜度無論哪一種遍歷方法都需要對所有的結(jié)點訪問，所以時間復(fù)雜度為O（n）,空間復(fù)雜度為棧的最大容量，即樹的深度。最壞的情況為O（n）。.舉例：試寫出二叉樹的先序遍歷，中序遍歷，后序遍歷序列前綴表達式-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef中綴表達式后綴表達式.BT*crt_bt_pre(BT*bt){charch;scanf("%c",&ch);if(ch=='')bt=NULL;else{bt=(BT*)malloc(sizeof(BT));bt->data=ch;bt->lchild=crt_bt_pre(bt->lchild);bt->rchild=crt_bt_pre(bt->rchild);}return(bt);}二叉樹的應(yīng)用ABCDEFGA^B^C^D^E^F^^G^1.建立二叉樹的二叉鏈表，已知先序序列為:ABCDEGFbtbtbtbt^bt^btbtbt^btbt^bt^btbt^bt^bt^bt遍歷算法的基本應(yīng)用.ABCDEFGA^B^C^D^E^F^^G^2.統(tǒng)計二叉樹中葉子結(jié)點個數(shù)算法算法:1）若二叉樹結(jié)點的左子樹和右子樹都為空，則該為葉子，計數(shù)器加1；2）遞歸統(tǒng)計左子樹上葉子的個數(shù)；3）遞歸統(tǒng)計右子樹上葉子的個數(shù)。.voidcountleaf(BT*bt){if(bt!=NULL){if((bt->lchild==NULL)&&(bt->rchild==NULL))count++;countleaf(bt->lchild);countleaf(bt->rchild);}}A^B^C^D^E^F^^G^算法實現(xiàn)：.3.求二叉樹深度算法A^B^C^D^E^F^^G^算法：1）若二叉樹空，則返回0，否則2）遞歸統(tǒng)計左子樹的深度；3）遞歸統(tǒng)計右子樹的深度；遞歸結(jié)束，返回其中大的值。.算法實現(xiàn)：A^B^C^D^E^F^^G^voidtreedepth(BT*bt){intldep,rdep;if(bt==NULL)return0；else{ldep=treedepth(bt->lchild);rdep=treedepth(bt->rchild);if(ldep>rdep)returnldep+1;else returnrdep+1;}}.4.求二叉樹結(jié)點數(shù)A^B^C^D^E^F^^G^算法：1）若二叉樹根結(jié)點不為空，則計數(shù)器加1；2）遞歸統(tǒng)計左子樹上結(jié)點個數(shù)；3）遞歸統(tǒng)計右子樹上結(jié)點個數(shù)。.算法實現(xiàn)：A^B^C^D^E^F^^G^voidnodenum(BT*bt){if(bt){count++；nodenum(bt->lchild);nodenum(bt->rchild);}}.ABCDEFGA^B^C^D^E^F^^G^5.查找數(shù)據(jù)元素算法:1）若二叉樹根結(jié)點為x，則返回該結(jié)點的指針，否則：2）遞歸在bt->lchild為根結(jié)點二叉樹上查找；3）遞歸在bt->rchild為根結(jié)點二叉樹上查找。.Voidsearch(BT*bt,elemtypex,BIT&p){if(bt){if(bt->data==x)p=bt；//p輸出的是先序序列中最后一個xsearch(bt->lchild,x,p);search(bt->rchild,x,p);}}//引用此函數(shù),初始p=NULLA^B^C^D^E^E^^G^算法實現(xiàn)：typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT,*BIT;.BTsearch(BT*bt,elemtypex){if(bt){if(bt->data==x)returnbt;if(bt->lchild!=null)returnsearch(bt->lchild,x);

if(bt->lchild!=null)retrunsearch(bt->rchild,x);}}算法實現(xiàn)：.6.3.2線索二叉樹從以上的討論可以得到：遍歷二叉樹是以一定的規(guī)則將二叉樹中的結(jié)點排列成一個線性序列。對二叉樹的遍歷可得到三種序列：先序、中序、后序序列。均為線性序列。結(jié)點至多有一個直接前趨和后繼。在二叉鏈表中找孩子結(jié)點容易，但找直接前趨和后繼結(jié)點不行。只有在遍歷的動態(tài)過程中才能得到。利用二叉鏈表中的空指針域，存儲直接前趨和后繼的指針（為區(qū)別起見此時指針稱為線索）；帶有線索的二叉樹稱為線索二叉樹。對二叉樹以某種次序遍歷改變空指針域為線索，使其變?yōu)榫€索二叉樹的過程稱為線索化。n個結(jié)點的二叉鏈表中的空指針域有n+1個。1.線索二叉樹.2.線索化二叉樹的方法同理，對二叉樹的不同遍歷可得到三種序列的線索二叉樹：先序線索二叉樹、中序線索二叉樹（用得多）、后序線索二叉樹。typedefstructnode{intdata;intlt,rt;structnode*lc,*rc;}BT;在線索二叉樹的結(jié)點中增加兩個標(biāo)志域lt:若lt=0,lc域為指針指向左孩子；若lt=1,lc域為線索指向其前驅(qū)(左)rt:若rt=0,rc域為指針指向右孩子；

若rt=1,rc域為線索指向其后繼(右)1)結(jié)點定義：lcltdatartrc.ABCDEABDCET先序序列：ABCDE先序線索二叉樹00001111^112)先序線索二叉樹.ABCDEABDCET中序序列：BCAED中序線索二叉樹00001111^11^3)中序線索二叉樹.ABCDEABDCET后序序列：CBEDA后序線索二叉樹0000111111^4)后序線索二叉樹.ABCDE頭結(jié)點：lt=0,lc指向根結(jié)點rt=1,rc指向頭結(jié)點遍歷序列中第一個結(jié)點的lc域和最后一個結(jié)點的rc域都指向頭結(jié)點ABDCET中序序列：BCAED中序線索二叉樹00001111^11^5)中序線索二叉樹0A01B00D11C11E1T中序序列：BCAED帶頭結(jié)點的中序線索二叉樹01.如何進行二叉樹的線索化，由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)和后繼的信息只有在遍歷時才能得到，所以線索化的過程即為在遍歷的過程中修改空指針的過程。為了方便，仿照線性表的存儲結(jié)構(gòu)，在二叉樹的線索鏈表上也添加一個頭結(jié)點，頭結(jié)點的Lchild域指向根結(jié)點，而rchild指向遍歷的最后一個結(jié)點。.按中序線索化二叉樹算法實現(xiàn)ABCDEt

0

1prpiP->AABDCEbt^^^^^^0000000000BT*zxxsh(BT*bt){BT*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}p.BT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}ABCDEABDCEbt^^^^^^t

0

1prpiP->AP->B0000000000.Ch5_20.cABCDEABDCEbt^^^^^^t

0

1prP=NULLiP->AP->BBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000000000p.Ch5_20.cABCDEABDCEbt^^^^^^t

0

1prPiP->A輸出:BBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;}if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00000000001.Ch5_20.cABCDEABDCEbt^^^^^t

0

1prP輸出:BiP->ABT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;}if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100000.Ch5_20.cABCDEABDCEbt^^^^^t

0

1prP輸出:BiP->AP->CBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;}if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100000.Ch5_20.cABCDEABDCEbt^^^^^t

0

1prP=NULLiP->AP->C輸出:BBT*zxxsh(BT*bt){BT*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100000P.Ch5_20.cABCDEABDCEbt^^^^^t

0

1prPiP->A輸出:BCBT*zxxsh(JD*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00001000001P->C.Ch5_20.cABCDEABDCEbt^^^^t

0

1prP=NULLiP->A輸出:BC

BT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100010.Ch5_20.cABCDEABDCEbt^^^^t

0

1prPi輸出:BCABT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00001000101P->A.Ch5_20.cABCDEABDCEbt^^^t

0

1P輸出:BCA

priP->DBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000101010.Ch5_20.cABCDEABDCEbt^^^t

0

1Pi輸出:BCA

prP->DBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000101010.Ch5_20.cABCDEABDCEbt^^^t

0

1P輸出:BCA

priP->DP->EBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000101010P=NULL.Ch5_20.cABCDEABDCEbt^^^t

0

1P=NULL輸出:BCA

priP->DP->EBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000101010P.Ch5_20.cABCDEABDCEbt^^^t

0

1Pi輸出:BCAEprP->DBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00001010101.Ch5_20.cABCDEABDCEbt^^t

0

1P=NULLi輸出:BCAE

prP->DBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000101011.Ch5_20.cABCDEABDCEbt^^t

0

1Pi輸出:BCAEDprBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00001010111P->D.Ch5_20.cABCDEABDCEbt^t

0

1i輸出:BCAED

prBT*zxxsh(BT*bt){BT*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00001011111P=NULL便于按前驅(qū)遍歷.建立中序線索化鏈表的算法Statuszxb(BTbt){if(bt){Zxb(bt->lc);If(!bt->lc){bt->lt=1;bt->lc=pre;}If(!pre->rc){pre->rt=1;pre->rc=bt;}Pre=bt;Zxb(bt->rc);}

0A01B00D11C11E1中序序列：BCAED帶頭結(jié)點的中序線索二叉樹.遍歷中序線索二叉樹的算法按中序線索化二叉樹遍歷中序線索二叉樹在中序線索二叉樹中用找結(jié)點后繼的方法遍歷：（1）若右鏈為線索rt=1,則rc域直接指向其后繼（2）若右鏈為指針rt=0,則結(jié)點的后繼應(yīng)是其右子樹的左鏈尾（lt=1)的結(jié)點在中序線索二叉樹中用找結(jié)點前驅(qū)的方法遍歷：（1）若lt=1,則lc域直接指向其前驅(qū)（2）若lt=0,則結(jié)點的前驅(qū)應(yīng)是其左子樹的右鏈尾（rt=1)的結(jié)點ABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結(jié)點的中序線索二叉樹01.voidzxblxss(BT*t){BT*p;p=t->lc;do{while(p->lt==0) p=p->lc;//最左的結(jié)點// printf("%c",p->data); while((p->rt==1)&&(p->rc!=t)) {p=p->rc;//為線索且不是中序的尾結(jié)點，P直接指向后繼// printf("%c",p->data); } p=p->rc;//P指向右子樹//}while(p!=t);}0A01B00D11C11E1t中序序列：BCAED帶頭結(jié)點的中序線索二叉樹01PPPPPPP.6.4樹和森林討論樹的表示及遍歷，并建立森林與二叉樹的關(guān)系。6.4.1樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)有多種形式，介紹常用的三種鏈表結(jié)構(gòu).1.雙親表示法typedefstructptnode{datatypedata;intparent;}ptnode;Typedetstruct{ptnodenoses[100]Intr,n;}ptreeabcdefhgiacdefghib01223555196012345789dataparent0號單元不用或存結(jié)點個數(shù).雙親表示法實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本身信息雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置(利用每個結(jié)點只有一個雙親的性質(zhì)，根除外)特點：找雙親容易，找孩子難.孩子表示法由于樹中的每個節(jié)點可能有多棵子樹，則可以用多重鏈表。即每個節(jié)點有多個指針域，其中每個指針指向一顆子樹的根結(jié)點。多重鏈表：a.結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度D特點：浪