1

樹的遍歷遍歷——按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結點的一個線性排列常用方法先根（序）遍歷：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結點按層次遍歷：先訪問第一層上的結點，然后依次遍歷第二層，……第n層的結點訪問：含義很廣，可以是對結點的各種處理，如修改結點數(shù)據(jù)、輸出結點數(shù)據(jù)。第二講遍歷二叉樹和線索二叉樹ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO2二叉樹的遍歷

二叉樹由根、左子樹、右子樹三部分組成二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹

如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？？令：L：遍歷左子樹

D：訪問根結點

R：遍歷右子樹

有六種遍歷方法：

DLR，LDR，LRD，

DRL，RDL，RLD

D

A

F

G

E

C

B

約定先左后右,有三種遍歷方法：DLR、LDR、LRD

，分別稱為

先序遍歷、中序遍歷、后序遍歷方法

先序遍歷（TLR）若二叉樹非空

（1）訪問根結點；（2）先序遍歷左子樹；

（3）先序遍歷右子樹；中序遍歷（LTR）若二叉樹非空

（1）中序遍歷左子樹

（2）訪問根結點（3）中序遍歷右子樹后序遍歷（LRT）若二叉樹非空

（1）后序遍歷左子樹

（2）后序遍歷右子樹（3）訪問根結點

D

A

F

G

E

C

BADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef算法遞歸算法ADBC先序遍歷序列：ABDC中序遍歷序列：BDAC后序遍歷序列：DBCA先序遍歷中序遍歷后序遍歷voidpreorder(JD*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非遞歸算法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)后序遍歷非遞歸算法遍歷算法應用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：

ABCDEGF求二叉樹深度算法ABCDEFGA^B^C^D^E^F^^G^統(tǒng)計二叉樹中葉子結點個數(shù)算法3線索二叉樹定義：前驅與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結點互稱為~線索：指向前驅或后繼結點的指針稱為~線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫~線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫~實現(xiàn)在有n個結點的二叉鏈表中必定有n+1個空鏈域在線索二叉樹的結點中增加兩個標志域lt:若lt=0,lc域指向左孩子；若lt=1,lc域指向其前驅rt:若rt=0,rc域指向右孩子；若rt=1,rc域指向其后繼結點定義：typedefstructnode{intdata;intlt,rt;structnode*lc,*rc;}JD;lcltdatartrcABCDEABDCET先序序列：ABCDE先序線索二叉樹00001111^11ABCDEABDCET中序序列：BCAED中序線索二叉樹00001111^11^ABCDEABDCET后序序列：CBEDA后序線索二叉樹0000111111^ABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結點的中序線索二叉樹

0

1頭結點：lt=0,lc指向根結點rt=1,rc指向遍歷序列中最后一個結點遍歷序列中第一個結點的lc域和最后一個結點的rc域都指向頭結點ABDCET中序序列：BCAED中序線索二叉樹00001111^11^算法按中序線索化二叉樹ABCDEt

0

1prpiP->AJD*zxxsh(JD*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(JD*)malloc(sizeof(JD));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);}ABDCEbt^^^^^^0000000000算法按中序線索化二叉樹ABCDEABDCEbt^^^^^^t

0

1prpiP->AP->BJD*zxxsh(JD*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(JD*)malloc(sizeof(JD));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);}0000000000算法按中序線索化二叉樹ABCDEABDCEbt^^^^^^t

0

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

t=(JD*)malloc(sizeof(JD));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);}0000000000算法按中序線索化二叉樹ABCDEABDCEbt^^^^^^t

0

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

t=(JD*)malloc(sizeof(JD));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算法按中序線索化二叉樹ABCDEABDCEbt^^^^^t

0

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

t=(JD*)malloc(sizeof(JD));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算法按中序線索化二叉樹ABCDEABDCEbt^^^^^t

0

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

t=(JD*)malloc(sizeof(JD));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算法按中序線索化二叉樹ABCDEABDCEbt^^^^^t

0

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

t=(JD*)malloc(sizeof(JD));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);}00001000001算法按中序線索化二叉樹ABCDEABDCEbt^^^^t

0

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

t=(JD*)malloc(sizeof(JD));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算法按中序線索化二叉樹ABCDEABDCEbt^^^^t

0

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

t=(JD*)malloc(sizeof(JD));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);}00001000101算法按中序線索化二叉樹ABCDEABDCEbt^^^t

0

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

t=(JD*)malloc(sizeof(JD));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算法按中序線索化二叉樹ABCDEABDCEbt^^^t

0

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

t=(JD*)malloc(sizeof(JD));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算法按中序線索化二叉樹ABCDEABDCEbt^^^t

0

1P=NULLi輸出:BCAprP->DP->EJD*zxxsh(JD*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(JD*)malloc(sizeof(JD));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算法按中序線索化二叉樹ABCDEABDCEbt^^^t

0

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

t=(JD*)malloc(sizeof(JD));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算法按中序線索化二叉樹ABCDEABDCEbt^^t

0

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

t=(JD*)malloc(sizeof(JD));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算法按中序線索化二叉樹ABCDEABDCEbt^^t

0

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

t=(JD*)malloc(sizeof(JD));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=b