第6章树和二叉树2课件

2.链式存储结构*结点组成：lchilddatarchild从二叉树的定义得知：二叉树的节点由一个数据元素和分别指向其左右子树的两个分支构成。这样二叉树的链表中至少有三个域其中：data为数据域；lchild为左指针域，放左子树的地址；rchild为右指针域，放右子树的地址；有时，为了便于找到结点的双亲，则还可在结点结构中增加一个指向其双亲结点的指针域。lchilddataparentrchild*带双亲的结点：.ABCDEFGABCDEFG^^^^^^^^BT：名字，根，入口.typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;*二叉链表的结构定义：.三叉链表typedefstructnode{datatypedata;structnode*lchild,*rchild,*parent;}TT;lchilddataparentrchild*结点组成：*三叉链表的结构定义：.ABCDEFGABCDEFG^^^^^^^^^.6.3遍历二叉树和线索二叉树6.3.1遍历二叉树遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列.有二叉树的定义可知：二叉树有三个基本单元组成：根结点，左子树，右子树。所以遍历二叉树就得依次遍历这三个部分。.二叉树的结构：DLRLDR、LRD、DLRRDL、RLD、DRL方法：先序遍历：先访问根结点,然后分别遍历左子树、右子树中序遍历：先遍历左子树，然后访问根结点，再遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点*限定先左后右的次序.ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC1.先序遍历:.ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC2.中序遍历:.ADBCLRDLRDLRD>A>>D>>CLRD后序遍历序列：DBCA3.后序遍历:B.4.层次遍历:ABCDEHIFGK层次遍历的序列:ABCDEFGHIK.算法实现（递归算法）1.先序遍历（DLR）算法实现：voidpreorder(BT*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}若二叉树为空，遍历结束。否则，1）访问根结点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）算法实现：voidinorder(BT*bt){if(bt!=NULL){inorder(bt->lchild);printf("%d\t",bt->data);inorder(bt->rchild);}}若二叉树为空，遍历结束。否则，1）中序遍历左子树2）访问根结点3）中序遍历右子树.3.后序遍历（LRD）算法实现：voidpostorder(BT*bt){if(bt!=NULL){postorder(bt->lchild);postorder(bt->rchild);printf("%d\t",bt->data);}}若二叉树为空，遍历结束。否则，1）后序遍历左子树2）后序遍历右子树3）访问根结点.遍历二叉树的非递归算法1.先序遍历的非递归算法*提高运算效率基于栈先序遍历的非递归算法：*引入栈保存每个结点的右指针算法：1）访问结点2）结点的右指针入栈3）若结点的左指针不空，遍历左子树4）右指针出栈5）若结点的右指针不空，遍历右子树.遍历二叉树的非递归算法2.中序遍历的非递归算法*引人栈保存每个结点及右指针，由于知道结点的指针便可知结点和其右指针，故只须结点的指针入栈算法：1）结点指针入栈2）若结点的左指针不空，遍历左子树3）指针出栈4）访问结点，若结点的右指针不空，遍历右子树.算法实现：voidinorderse(BT*bt){inti=0;//栈的初始化BT*p,*s[M];//保存每个结点的指针的栈//p=bt;do{while(p!=NULL){s[i++]=p;//结点的指针入栈//p=p->lchild;//进入左子树//}//左子树为空，退出//if(i>0){p=s[--i];printf("%d\t",p->data);p=p->rchild;}}while(i>0||p!=NULL);//右子树为空同时栈空，结束//}.非递归算法栈操作图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).按层次遍历须设队列依次记录结点的左孩子，右孩子结点的指针算法：1）根结点入队2）根结点出队访问；若根结点的左，右指针非空，则依次入队；3）重复，直至队空.算法实现：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++;}}.遍历二叉树的时间和空间复杂度无论哪一种遍历方法都需要对所有的结点访问，所以时间复杂度为O（n）,空间复杂度为栈的最大容量，即树的深度。最坏的情况为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);}二叉树的应用ABCDEFGA^B^C^D^E^F^^G^1.建立二叉树的二叉链表，已知先序序列为:ABCDEGFbtbtbtbt^bt^btbtbt^btbt^bt^btbt^bt^bt^bt遍历算法的基本应用.ABCDEFGA^B^C^D^E^F^^G^2.统计二叉树中叶子结点个数算法算法:1）若二叉树结点的左子树和右子树都为空，则该为叶子，计数器加1；2）递归统计左子树上叶子的个数；3）递归统计右子树上叶子的个数。.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^算法实现：.3.求二叉树深度算法A^B^C^D^E^F^^G^算法：1）若二叉树空，则返回0，否则2）递归统计左子树的深度；3）递归统计右子树的深度；递归结束，返回其中大的值。.算法实现：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.求二叉树结点数A^B^C^D^E^F^^G^算法：1）若二叉树根结点不为空，则计数器加1；2）递归统计左子树上结点个数；3）递归统计右子树上结点个数。.算法实现：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.查找数据元素算法:1）若二叉树根结点为x，则返回该结点的指针，否则：2）递归在bt->lchild为根结点二叉树上查找；3）递归在bt->rchild为根结点二叉树上查找。.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);}}//引用此函数,初始p=NULLA^B^C^D^E^E^^G^算法实现：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);}}算法实现：.6.3.2线索二叉树从以上的讨论可以得到：遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列。对二叉树的遍历可得到三种序列：先序、中序、后序序列。均为线性序列。结点至多有一个直接前趋和后继。在二叉链表中找孩子结点容易，但找直接前趋和后继结点不行。只有在遍历的动态过程中才能得到。利用二叉链表中的空指针域，存储直接前趋和后继的指针（为区别起见此时指针称为线索）；带有线索的二叉树称为线索二叉树。对二叉树以某种次序遍历改变空指针域为线索，使其变为线索二叉树的过程称为线索化。n个结点的二叉链表中的空指针域有n+1个。1.线索二叉树.2.线索化二叉树的方法同理，对二叉树的不同遍历可得到三种序列的线索二叉树：先序线索二叉树、中序线索二叉树（用得多）、后序线索二叉树。typedefstructnode{intdata;intlt,rt;structnode*lc,*rc;}BT;在线索二叉树的结点中增加两个标志域lt:若lt=0,lc域为指针指向左孩子；若lt=1,lc域为线索指向其前驱(左)rt:若rt=0,rc域为指针指向右孩子；

若rt=1,rc域为线索指向其后继(右)1)结点定义：lcltdatartrc.ABCDEABDCET先序序列：ABCDE先序线索二叉树00001111^112)先序线索二叉树.ABCDEABDCET中序序列：BCAED中序线索二叉树00001111^11^3)中序线索二叉树.ABCDEABDCET后序序列：CBEDA后序线索二叉树0000111111^4)后序线索二叉树.ABCDE头结点：lt=0,lc指向根结点rt=1,rc指向头结点遍历序列中第一个结点的lc域和最后一个结点的rc域都指向头结点ABDCET中序序列：BCAED中序线索二叉树00001111^11^5)中序线索二叉树0A01B00D11C11E1T中序序列：BCAED带头结点的中序线索二叉树01.如何进行二叉树的线索化，由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱和后继的信息只有在遍历时才能得到，所以线索化的过程即为在遍历的过程中修改空指针的过程。为了方便，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，头结点的Lchild域指向根结点，而rchild指向遍历的最后一个结点。.按中序线索化二叉树算法实现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便于按前驱遍历.建立中序线索化链表的算法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带头结点的中序线索二叉树.遍历中序线索二叉树的算法按中序线索化二叉树遍历中序线索二叉树在中序线索二叉树中用找结点后继的方法遍历：（1）若右链为线索rt=1,则rc域直接指向其后继（2）若右链为指针rt=0,则结点的后继应是其右子树的左链尾（lt=1)的结点在中序线索二叉树中用找结点前驱的方法遍历：（1）若lt=1,则lc域直接指向其前驱（2）若lt=0,则结点的前驱应是其左子树的右链尾（rt=1)的结点ABCDE0A01B00D11C11E1T中序序列：BCAED带头结点的中序线索二叉树01.voidzxblxss(BT*t){BT*p;p=t->lc;do{while(p->lt==0) p=p->lc;//最左的结点// printf("%c",p->data); while((p->rt==1)&&(p->rc!=t)) {p=p->rc;//为线索且不是中序的尾结点，P直接指向后继// printf("%c",p->data); } p=p->rc;//P指向右子树//}while(p!=t);}0A01B00D11C11E1t中序序列：BCAED带头结点的中序线索二叉树01PPPPPPP.6.4树和森林讨论树的表示及遍历，并建立森林与二叉树的关系。6.4.1树的存储结构树的存储结构有多种形式，介绍常用的三种链表结构.1.双亲表示法typedefstructptnode{datatypedata;intparent;}ptnode;Typedetstruct{ptnodenoses[100]Intr,n;}ptreeabcdefhgiacdefghib01223555196012345789dataparent0号单元不用或存结点个数.双亲表示法实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置(利用每个结点只有一个双亲的性质，根除外)特点：找双亲容易，找孩子难.孩子表示法由于树中的每个节点可能有多棵子树，则可以用多重链表。即每个节点有多个指针域，其中每个指针指向一颗子树的根结点。多重链表：a.结点同构：结点的指针个数相等，为树的度D特点：浪