数据结构课件第六章第二讲

1

树的遍历遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列常用方法先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。第二讲遍历二叉树和线索二叉树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^统计二叉树中叶子结点个数算法3线索二叉树定义：前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~线索：指向前驱或后继结点的指针称为~线索二叉树：加上线索的二叉链表表示的二叉树叫~线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~实现在有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