《六章树和二叉树.PPT》由会员分享，可在线阅读，更多相关《六章树和二叉树.PPT（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、六章树和二叉树 Still waters run deep.流静水流静水深深,人人静心静心深深 Where there is life,there is hope。有生。有生命命必有必有希望希望1.树(Tree)：是n(n0)个结点的有限集。在任意一棵非空树中(1)有且只有一个称为根(Root)的结点。(2)其余的结点被分为m(m0)个互不相交的有限集，其中每个集合本身又是一棵树，称为根(Root)结点的子树(Sub_Tree)。6.1 树的定义和基本术语 6.1.1 基本术语树的定义本身是递归的。递归定义和递归操作在树和二叉树中应用是比较广泛的，应注意领会递归的实质。2.树的表示法：有图示法
2、、集合表示法、广义表表示法和缩进表示法，见图6.1。(A(B(E,F(L),G),C(H,I(M,N),D(J,K)(b)广义表表示法ACEFGHJKLNMBID(a)图示法 ADBCIMNHGEFLKJ(c)集合表示法 ABEFLGCHIMNDKJ(d)缩进表示法图4.1 树的几种表示法 3.结点的分类：从计算机的角度来分，可以分为终端结点和非终端结点；以树的特征来分，可以分根结点、分支结点和叶子结点；用族谱的关系来分，可以分为双亲结点和孩子结点、祖先结点和子孙结点、兄弟结点和堂兄弟结点。4.度：分为结点的度和树的度两种。结点的度是指与该结点相连接的孩子结点的数目。树的度是指该棵树中所有结点
3、的度中的最大值。5.深度：树是一种分层结构，根结点作为第一层。结点的层次(或称深度)就是指从根结点开始的层次数。树的深度(或层数)是指该树中所有结点的层次中的最大值。用图示法表示的二叉树中，边的数目(或称分支数，用e表示)恰好比结点数目(用n表示)少一个，即e=n-1。这是树状结构中最重要的一个结论。6.有序树与无序树：如果将树中结点的各棵子树看成是从左到右有次序的(即不能互换),则称该树为有序树，否则称为无序树。7有向树与无向树：如果树的每个分支都是从一个结点到另一个结点有方向的，则称该树为有向树，否则称为无向树。8.n元树：树的度为n的有向树。9.位置树：是一棵有向树。如果树中结点的每个孩
4、子结点位置是不能被改变的(改变则不是原树)，则称该树为位置树。如某结点可能没有第一个孩子结点，但却可能会有第二个、第三个孩子结点。10.m叉树：是树的度为m的有向位置树，即m元位置树。11.森林：是m(m0)棵互不相交的树的集合。对于树中的每个结点而言，其子树的集合就是森林。因此，森林和树是密切相关的。森林中的树也可以有顺序关系和位置关系。树状结构也是用于存储数据的，我们也要对其中的数据进行加工处理。总体上，树的基本操作有如下几种：InitTree(T)构造一棵空树T。ClearTree(T)将已经存在的树T清空。TreeEmpty(T)判断树T是否为空树。TreeDepth(T)计算树T的深
5、度。InsertChild(T,p,i,c)插入子树c为树T中p指向结点的第i棵子树。DeleteChild(T,p,i)删除树T中p所指结点的第i棵子树。TraverseTree(T)按某种次序对树T中的所有结点进行访问，每个结点仅访问一次。6.1.2 树的基本操作二叉树(Binary Tree)是一种特殊的有向树，也称二元位置树。它的特点是每个结点至多有两棵子树，即二叉树中的每个结点至多有两个孩子结点，且每个孩子结点都有各自的位置关系。或者说，二叉树的子树有左右之分，其次序不能任意颠倒。给二叉树下个更加确切的定义，就是：二叉树或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互
6、不相交的二叉树组成。6.2 二叉树6.2.1 二叉树的定义可以看出，二叉树的定义是递归的，前面提到的树的定义也是递归的。这说明树状结构在处理数据时很多操作是可以通过递归来完成的。图6.2 二叉树的五种基本形态 (a)空二叉树(b)仅有根结点(c)右子树为空(d)左子树为空(e)左右子树均非空根据二叉树的定义，可以总结出二叉树有如图6.2所示的五种形态：【例6.1】列举出只有两个结点、三个结点的二叉树的所 有形态 1.只有两个结点的二叉树的形态有两种，如图6.3所示 图6.3 只有两个结点的二叉树的所有形态2.只有三个结点的二叉树的形态有五种，如图6.4所示 图6.4 只有三个结点的二叉 树的所
7、有形态6.2.2 二叉树的性质与结论 性质1：在二叉树的第i(i1)层上至多有2i-1个结点。(该性质证明利用归纳法很容易实现，留给读者自己去思考)性质2：深度为k(k1)的二叉树上至多有2k-1个结点。(该性质证明直接利用性质1即可，留给读者自己去思考)性质3：任意一棵二叉树中，叶子结点的数目(用n0表示)总比度为2的结点的数目(用n2表示)多一个，即n0=n2+1。证明：设结点总数为n，度为1的结点数目为n1，则有 n=n0+n1+n2 (6-1)由于二叉树中除根之外的每个结点都带有一个向上的分支，设分支总数为e，则 e=n-1 (6-2)由于这些分支不是度为1的结点射出的分支，就是度为2
8、的结点射出的分支,则e=1n1+2n2 (6-3)由(6-2)式和(6-3)式，得n-1=n1+2n2 (6-4)由(6-1)式和(6-4)式，得1=n0-n2 即 n0=n2+1 证毕。两种特殊形态的二叉树 满二叉树:除叶子结点外的任何结点均有两个孩子结点，且所有的叶子结点都在同一层上的二叉树。特点是每一层上的结点数都是最大的。完全二叉树:除去最底层结点后的二叉树是一棵满二叉树，且最底层结点均靠左对齐的二叉树。在这里，靠左对齐的含义是左边是满的，即没有空隙再放入任何一个结点。423167891011125 6.5(b)如图6.5(a)是一棵深度为4的满二叉树，而图6.5(b)是一棵深度为4的
9、完全二叉树。实质上，满二叉树是完全二叉树的一个特例4231678910111213141556.5(a)证明：设具有n个结点的完全二叉树的深度为k，则由性质2可知2k-1-1n2k-1则 2k-1n2k 取以2为底的对数，得 k-1log2nk log2n处于两个连续的整数k-1和k之间 k-1=log2n即 k=log2n+1 证毕。性质4：具有n个结点的完全二叉树的深度为log2n+1。性质5：对有n个结点的完全二叉树中的任一结点i(1in)，有(1)其双亲结点编号为i/2(1in)。(2)其左孩子结点的编号为2i(1in/2)。(3)其右孩子结点的编号为2i+1(1i(n-1)/2)证明
10、：设树中分支数为e，则根据树的定义可知：e=n-1。若n为偶数，则分支数e为奇数，根据完全二叉树的定义可知，在完全二叉树中仅有一个度为1的结点。同理，若n为奇数时，则分支数e为偶数，所以在完全二叉树中没有度为1的结点。证毕。性质6：当结点个数n为偶数时，完全二叉树中有且仅有一个度为1的结点；当结点个数n为奇数时，完全二叉树中没有度为1的结点证明：(1)当n为偶数时，由性质6可知：完全二叉树中有一个度为1的结点，即 n1=1,由性质3可知，n0=n2+1，即 n0=n2+n1 (6-5)又结点总数为 n=n0+n1+n2 (6-6)由(6-5)和(6-6)式，得 n0=n2+n1=n/2=n/2
11、 即，当n为偶数时，编号大于n/2的结点均为叶子结点。(2)当n为奇数时，由性质6可知：完全二叉树中没有度为1的结点，即n1=0,由性质3可知，n0=n2+1 (6-7)又结点总数为 n=n0+n1+n2，即 n=n0+n2 (6-8)由(6-7)式和(6-8)式，得n=2n2+1 即 n1+n2=(n-1)/2=n/2 所以，当n为奇数时，编号大于n/2的结点均为叶子结点。性质7：在完全二叉树中编号大于n/2的结点均为叶子结点。【例6.2】已知一棵完全二叉树中有234个结点，问(1)树的高度是多少？(2)第7层和第8层上各有多少个结点？(3)树中有多少个叶子结点？多少个度为2的结点？多少个度
12、为1的结点？注意:一般二叉树的性质可用于完全二叉树；反之，完全二叉树的性质和结论是不能用于一般二叉树中的。解:(1)由性质4可知该完全二叉树的高度(k)为：k=log2234+1=log227+1=8 即该二叉树的高度为8层。(2)由性质1可知第7层上的结点数为：27-1=26=64(个)。由性质2可知第8层上的结点数为：234-(27-1)=107(个)。(3)由性质7可知树中叶子结点个数为：234-234/2=117(个)。由性质2可知度为2的结点个数为：117-1=116(个)。由性质6可知度为1的结点个数为：1(个)。6.2.3 二叉树的存储结构6.2.3.1 二叉树的顺序存储结构将二
13、叉树上的结点值按从上至下、从左至右的顺序存储到一个线性结构(常为数组)中,数组中的下标为0的单元可用于存放二叉树中结点的个数或二叉树的深度,虚结点可以用一个特殊的标志来识别。11ABcFED12489105637121314150000FE000DC0BA15141312111098765432100图6.6void leveltree(SqBitTree bt)/*按满二叉树输出*/int i=1,j;while(i=bt0)/*按层扫描*/for(j=i;j2*i;j+)/*扫描第i层结点*/if(btj=VirNode)printf(*);/*若是虚结点，则输出一个“*”号*/else
14、printf(%d ,btj);printf(n);i=2*i;/*跳到下一层*/【例6.3】按层输出二叉树中的所有结点的值。void exchangetree(SqBitTree bt)/*该二叉树应添加若干虚结点变为满二叉树*/int k=2,i,j;TelemType t;/*第1层只一个结点，所以从第二层开始进行*/while(k=bt0)for(i=k,j=2*k-1;ij;i+,j-)/*同一层结点值逆置即可完成交换*/t=bti;bti=btj;btj=t;k=2*k;【例6.4】交换二叉树中所有结点的左右子树。void searchtree(SqBitTree bt,TElem
15、Type x,TElemType*pa,TElemType*lc,TElemType*rc)int i=1,k=1;while(k=bt0)while(i2*k&bti!=x)i+;if(i1)*pa=bti/2;else printf(“该结点为根结点!”);if(2*i=bt0)*lc=bt2*i;else printf(“该结点为叶子 结点!”);if(2*i+1data);/*访问根结点*/PreOrderTraverse(bt-lchild);/*遍历左子树*/PreOrderTraverse(bt-rchild);/*遍历右子树*/2.遍历二叉树的递归算法(3)后序遍历二叉树的递归
16、算法void PostOrderTraverse(BitTree bt)if(bt!=NULL)PostOrderTraverse(bt-lchild);PostOrderTraverse(bt-rchild);printf(%d ,bt-data);(2)中序遍历二叉树的递归算法void InOrderTraverse(BitTree bt)if(bt!=NULL)InOrderTraverse(bt-lchild);printf(%d ,bt-data);InOrderTraverse(bt-rchild);3.二叉树的建立算法因为在含有n个结点的二叉链表中一定有n+1个空指针域，所以在输
17、出数据时一定要给出n+1个空指针值。对于数值型数据一般以“-1”代替空指针，对于字符型数据一般以空格“”代替空指针。BitTree CreateBiTree(void)BitTree CreateBiTree(void)BitTree bt;TelemType x;BitTree bt;TelemType x;scanf(%d,&x);/*scanf(%d,&x);/*读入数据读入数据*/*/if(x=-1)bt=NULL;/*if(x=-1)bt=NULL;/*安排空指针安排空指针*/*/elseelse bt=(BitTree)malloc(sizeof(BitNode);bt=(BitT
18、ree)malloc(sizeof(BitNode);bt-data=x;/*bt-data=x;/*生成新结点生成新结点*/*/bt-lchild=CreateBiTree();/*bt-lchild=CreateBiTree();/*建立左子树建立左子树*/*/bt-rchild=CreateBiTree();/*bt-rchild=CreateBiTree();/*建立右子树建立右子树*/*/return bt;/*return bt;/*返回根结点的指针返回根结点的指针*/*/若输入如下数据：124-1-1-1357-1-18-1-16-1-1，则建立的二叉树如图6.13所示，其中-1
19、用来安排空指针。若data域为字符型，则输入如下数据：12435786,也可以建立如图4.13所示的二叉树，其中“”表示空格符，用来安排空指针。需要注意的是n个结点的二叉树中一定有n+1个空指针，所以要输入n+1个“-1”或空格“”。1 12 24 43 35 58 87 76 6图6.13二叉树递归遍历应用举例【例6.10】统计二叉树中叶子结点的个数。int n=0;/*定义一个全局变量用来存放叶子结点的个数*/void leafcount(BitTree bt)if(bt!=NULL)if(bt-lchild=NULL&bt-rchild=NULL)n+;/*将访问换成统计个数的语句*/l
20、eafcount(bt-lchild);leafcount(bt-rchild);【例6.11】交换二叉树中所有结点的左右子树。BitTree exchangetree(BitTree bt)BitTree t;if(bt!=NULL)if(bt-lchild!=NULL|bt-rchild!=NULL)/*将访问换成交换指针的语句*/t=bt-lchild;bt-lchild=bt-rchild;bt-rchild=t;bt-lchild=exchangetree(bt-lchild);bt-rchild=exchangetree(bt-rchild);【例6.12】求二叉树的高度。int
21、hightree(BitTree bt)int H,H1,H2;if(bt=NULL)H=0;/*树空，则高度为0*/else H1=hightree(bt-lchild);/*否则，分别计算左右子树的高度*/H2=hightree(bt-rchild);H=(H1H2?H1:H2)+1;/*取左右子树高度的最大值再加1(根结点)作为树的高度*/return H;【例6.13】查找值为x的结点。找到带回该结点的指针，否则带回空指针。int find=0;/*设置查找标记：0表示未找到，1表示找到*/void searchtree(BitTree bt,TElemType x,BitTree*p
22、)if(bt!=NULL&!find)if(bt-data=x)find=1;*p=bt;/*若找到，则通过p带回该结点的指针*/else *p=NULL;/*未找到，通过p带回空指针*/searchtree(bt-lchild,x,p);searchtree(bt-rchild,x,p);【例6.14】删除值为x的结点，使得其左右子树的安排仍然满足原来的中序遍历序列。分析：为了保持中序遍历序列不变，对于找到的结点p可以分为四种情况考虑：若结点p为叶子结点，则只需将该结点的双亲结点(f)的左指针或右指针置为空即可；若结点p的左子树为空，则只需将该结点(p)的双亲结点(f)的左指针或右指针指向该
23、结点(p)的右孩子结点即可；若结点p的左子树非空，则只需找到结点p的左子树中最右下的结点s(s的右指针必为空)，将该结点(s)的左子树接到该结点(s)的双亲结点(q)上，再用该结点(s)中的数据替换结点(p)中的数据即可；若结点p为根结点(bt)且该结点左子树为空，则只需将根结点的指针(bt)移到结点p的右子树上即可，如图6.14。为此需重新设计查找算法如下：(b)P PF Ff fp pP PF Ff fp pQ QS Ss sq q(c)图6.14在二叉树中删除p结点int find=0;int find=0;searchtree(BitTree bt,TElemType x,BitTre
24、e*p,searchtree(BitTree bt,TElemType x,BitTree*p,BitTree*f)BitTree*f)if(bt!=NULL&!find)if(bt!=NULL&!find)if(bt-data=x)if(bt-data=x)find=1;*p=bt;find=1;*p=bt;else else *f=bt;*f=bt;searchtree(bt-lchild,x,p,f);searchtree(bt-lchild,x,p,f);*f=bt;*f=bt;searchtree(bt-rchild,x,p,f);searchtree(bt-rchild,x,p,f
25、);删除值为x结点的算法如下：void deltree(BitTree bt,TElemType x)void deltree(BitTree bt,TElemType x)BitTree p,f,q,s,;p=f=NULL;BitTree p,f,q,s,;p=f=NULL;searchtree(bt,x,&p,&f);searchtree(bt,x,&p,&f);if(p!=NULL)if(p-lchild!=NULL)if(p!=NULL)if(p-lchild!=NULL)q=p-lchild;s=q;q=p-lchild;s=q;while(s-rchild!=NULL)while(
26、s-rchild!=NULL)q=s;s=s-rchild;q=s;s=s-rchild;if(s!=q)q-rchild=s-lchild;if(s!=q)q-rchild=s-lchild;else p-lchild=q-lchild;else p-lchild=q-lchild;p-data=s-data;free(s);p-data=s-data;free(s);else if(f!=NULL)else if(f!=NULL)if(p=f-lchild)f-lchild=p-rchild;if(p=f-lchild)f-lchild=p-rchild;else f-rchild=p-r
27、child;else f-rchild=p-rchild;else bt=bt-rchild;free(p);else bt=bt-rchild;free(p);else printf(else printf(结点结点x x在二叉树中不存在在二叉树中不存在!n);n);二叉树的非递归遍历1.二叉树的先序非递归遍历算法先将根结点的指针进栈，算法如下：先将根结点的指针进栈，算法如下：PreOrderBiTree(BitTree T)PreOrderBiTree(BitTree T)stack S;BitTree p;stack S;BitTree p;InitStack(S);/*InitStac
28、k(S);/*初始化一个栈初始化一个栈*/*/push(S,T);/*push(S,T);/*根结点指针进栈根结点指针进栈*/*/while(!EmptyStack(S)/*while(!EmptyStack(S)/*栈为空时算法结束栈为空时算法结束*/*/p=pop(S);/*p=pop(S);/*弹栈，弹栈，p p指向指向(子树子树)根结点根结点*/*/while(p)printf(%d ,p-data);/*while(p)printf(%d ,p-data);/*访问根结点访问根结点*/*/if(p-rchild)push(S,p-rchild);/*if(p-rchild)push(
29、S,p-rchild);/*非空的右指针进栈非空的右指针进栈*/*/p=p-lchild;/*p=p-lchild;/*沿着左指针访问，直到左指针为空沿着左指针访问，直到左指针为空*/*/2.2.二叉树的中序非递归遍历算法二叉树的中序非递归遍历算法InOrderBitree(BitTree T)InOrderBitree(BitTree T)stack S;BitTree p;stack S;BitTree p;Initstack(S);/*Initstack(S);/*初始化一个栈初始化一个栈*/*/p=T;/*pp=T;/*p指向根结点指向根结点*/*/while(p|!EmptyStac
30、k(S)/*while(p|!EmptyStack(S)/*当当p p为空且栈为空时算法结束为空且栈为空时算法结束*/*/while(p)while(p)push(S,p);push(S,p);p=p-lchild;p=p-lchild;/*/*沿左指针走，沿途经过的沿左指针走，沿途经过的(子树子树)根结点指针进栈根结点指针进栈*/*/p=pop(S);p=pop(S);printf(%d printf(%d,p-data);/*,p-data);/*当当左左指指针针为为空空时时弹弹栈栈并并访访问问该该结结点点(子子树树根根结结点点)*/)*/p=p-rchild;/*p=p-rchild;/
31、*向右跳一步到右子树上继续进行遍历过程向右跳一步到右子树上继续进行遍历过程*/*/3.3.二叉树的后序非递归遍历算法二叉树的后序非递归遍历算法 PostOrderBiTree(BitTree T)PostOrderBiTree(BitTree T)stack S;BitTree p,q;InitStack(S);p=T;q=NULL;stack S;BitTree p,q;InitStack(S);p=T;q=NULL;while(p|!EmptyStack(S)while(p|!EmptyStack(S)if(p!=q)while(p)if(p!=q)while(p)push(S,p);pu
32、sh(S,p);/*p /*p非空时，压栈非空时，压栈*/*/if(p-lchild)p=p-lchild;/*if(p-lchild)p=p-lchild;/*沿左指针下移，若左指针为空，沿左指针下移，若左指针为空，*/*/else p=p-rchild;/*else p=p-rchild;/*则沿右指针下移则沿右指针下移*/*/if(EmptyStack(S)break;if(EmptyStack(S)break;/*/*若栈空，则结束若栈空，则结束*/*/q=gettop(S);/*q=gettop(S);/*取栈顶指针送取栈顶指针送q q，*/*/if(q-rchild=p)/*if(
33、q-rchild=p)/*若若q q的右指针为空的右指针为空(p p为空时为空时)或指向刚刚访问过的结点或指向刚刚访问过的结点*/*/p=pop(S);/*p=pop(S);/*则弹栈并访问该结点则弹栈并访问该结点*/*/printf(%d,p-data);printf(%d,p-data);else p=q-rchild;else p=q-rchild;/*/*否则，沿否则，沿q q的右指针继续遍历访问的右指针继续遍历访问*/*/在此，安排了一个指针(q)指向栈顶元素，目的是观察其右子树是否已经访问过了。若确实已访问过了，则该指针一定是指向刚刚访问过的(子树)根结点(p结点)，即q=p，否则
34、，再对其右子树进行压栈处理，直到右指针为空。然后再取出新的栈顶元素送q，观察其是否被访问过了。若未访问过(q-rchild=p)，则弹栈并访问之，否则，再沿其右指针下移，如此进行，直到所有结点均被访问过为止。后序遍历的非递归算法也可以类似于先序遍历的非递归算法一样，只是从右子树到左子树再到根结点进行遍历搜索，将沿途经过的结点依次依次进栈，最后再统一出栈完成遍历的过程。这种方法需要栈的空间较大，不太适用 6.3.2 线索二叉树线索二叉树的定义 遍历二叉树实质上是对一个非线性结构进行的线性化操作，使每个结点(除第一个结点和最后一个结点外)均有惟一的一个直接前驱和直接后继。但是，二叉树本身并不是线性
35、关系的结构，如果进行线性化的处理，那么在动态的遍历过程中如何保存这种前驱和后继的关系就成为关键所在。为此，对二叉链表作以改进，增加两个标志域来记录这种线性化的信息。其类型定义为：typedef struct BiThrNodetypedef struct BiThrNode TElemType data;TElemType data;int ltag,rtag;/*int ltag,rtag;/*增加左指针及右指针的信息标志增加左指针及右指针的信息标志*/*/struct BiThrNode*lchild,*rchild;struct BiThrNode*lchild,*rchild;BiTh
36、rNode,*BiThrTree;BiThrNode,*BiThrTree;其中 0 lchild指针指向该结点的左孩子结点 ltag=1 lchild指针指向该结点的直接前驱结点 0 rchild指针指向该结点的右孩子结点 rtag=1 rchild指针指向该结点的直接后继结点lchildlchildltagltagdatadatartagrtagrchildrchild这种结构中结点构成为：以这种结点结构构成的二叉链表作为二叉树的存储结构，就称为线索链表。指向前驱和后继的指针称为线索，加上线索的二叉树称为线索二叉树(Threaded Binary Tree)。对二叉链表以某种次序遍历使之成
37、为线索二叉树的过程称为线索化处理。按先序遍历得到的线索二叉树称为先序线索二叉树，按中序遍历得到的线索二叉树称为中序线索二叉树，按后序遍历得到的线索二叉树称为后序线索二叉树。其中，还可以分出先序(中序、后序)前驱线索二叉树和先序(中序、后序)后继线索二叉树等等。【例6.15】已知一棵二叉树如图6.15(a)所示，试画出其三种线索二叉树。(a)已 知 二 叉树 NULL(b)先序线索二叉树NULL (c)中序线索二叉树(d)后序线索二叉树图6.15 二叉树与三种线索二叉树NULL NULL线索化处理算法 1.先序线索化处理算法BiThrTree pre;/*BiThrTree pre;/*中序与后
38、序也要定义该变量中序与后序也要定义该变量,用以记录遍历时的前驱结点用以记录遍历时的前驱结点*/*/BiThrTree PreOrderThreading(BiThrTree T)BiThrTree PreOrderThreading(BiThrTree T)BiThrTree Thrt;Thrt=(BiThrTree)malloc(sizeof(BiThrNode);BiThrTree Thrt;Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt-ltag=0;Thrt-rtag=1;Thrt-rchild=Thrt;Thrt-ltag=0;Thrt-r
39、tag=1;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;/*if(!T)Thrt-lchild=Thrt;/*则头结点自身构成一个循环链表则头结点自身构成一个循环链表*/*/else /*else /*头结点中的左指针指向根结点头结点中的左指针指向根结点*/*/Thrt-lchild=T;pre=Thrt;/*Thrt-lchild=T;pre=Thrt;/*且记录根结点的前驱结点指针且记录根结点的前驱结点指针pre*/pre*/PreThreading(T);/*PreThreading(T);/*对二叉树进行线索化处理对二叉树进行线索化处理*/*/pre
40、-rchild=Thrt;pre-rtag=1;/*pre-rchild=Thrt;pre-rtag=1;/*序列中最后一个结点与头结点相互连接序列中最后一个结点与头结点相互连接*/*/Thrt-rchild=pre;Thrt-rchild=pre;void PreThreading(BiThrTree p)void PreThreading(BiThrTree p)if(p)if(!p-lchild)if(p)if(!p-lchild)p-ltag=1;p-lchild=pre;/*p-ltag=1;p-lchild=pre;/*若左指针为空，则安排前驱线索若左指针为空，则安排前驱线索*/*
41、/else p-ltag=0;if(!pre-rchild)else p-ltag=0;if(!pre-rchild)pre-rtag=1;pre-rchild=p;/*pre-rtag=1;pre-rchild=p;/*若右指针为空，则安排后继线索若右指针为空，则安排后继线索*/*/else p-rtag=0;pre=p;/*else p-rtag=0;pre=p;/*前驱结点指针前驱结点指针*/*/if(p-ltag=0)PreThreading(p-lchild);/*if(p-ltag=0)PreThreading(p-lchild);/*左子树线索化处理左子树线索化处理*/*/Pre
42、Threading(p-rchild);PreThreading(p-rchild);/*/*右子树线索化处理右子树线索化处理*/*/为便于处理，与线性链表类似，可以在线索二叉链表中增加一个头结点Thrt，其左指针指向根结点，右指针可以指向序列中的最后一个结点。2.中序线索化处理算法BiThrTree InOrderThreading(BiThrTree T)BiThrTree InOrderThreading(BiThrTree T)BiThrTree Thrt;Thrt=(BiThrTree)malloc(sizeof(BiThrNode);BiThrTree Thrt;Thrt=(BiT
43、hrTree)malloc(sizeof(BiThrNode);Thrt-ltag=0;Thrt-rtag=1;Thrt-rchild=Thrt;Thrt-ltag=0;Thrt-rtag=1;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;pre-rtag=1;Thrt-rchild=pre;pre-rchild=
44、Thrt;pre-rtag=1;Thrt-rchild=pre;void InThreading(BiThrTree p)void InThreading(BiThrTree p)if(p)pre=p;InThreading(p-lchild);if(p)pre=p;InThreading(p-lchild);if(!p-lchild)p-ltag=1;p-lchild=pre;if(!p-lchild)p-ltag=1;p-lchild=pre;else p-ltag=0;else p-ltag=0;if(pre-rchild)pre-rtag=1;pre-rchild=p;if(pre-r
45、child)pre-rtag=1;pre-rchild=p;else pre-rtag=0;else pre-rtag=0;InThreading(p-rchild);InThreading(p-rchild);3.后序线索化处理算法BiThrTree PostOrderThreading(BiThrTree T)BiThrTree PostOrderThreading(BiThrTree T)BiThrTree Thrt;Thrt=(BiThrTree)malloc(sizeof(BiThrNode);BiThrTree Thrt;Thrt=(BiThrTree)malloc(sizeof(
46、BiThrNode);Thrt-ltag=0;Thrt-rtag=1;Thrt-rchild=Thrt;Thrt-ltag=0;Thrt-rtag=1;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;PostThreading(T);else Thrt-lchild=T;pre=Thrt;PostThreading(T);pre-rchild=Thrt;pre-rtag=1;Thrt-rchild=pre;pre-rchild=Thrt;pre-rtag=1;T
47、hrt-rchild=pre;void PostThreading(BiThrTree p)void PostThreading(BiThrTree p)if(p)PostThreading(p-lchild);if(p)PostThreading(p-lchild);PostThreading(p-rchild);PostThreading(p-rchild);if(!p-lchild)p-ltag=1;p-lchild=pre;if(!p-lchild)p-ltag=1;p-lchild=pre;else p-ltag=0;else p-ltag=0;if(pre-rchild)pre-r
48、tag=1;pre-rchild=p;if(pre-rchild)pre-rtag=1;pre-rchild=p;else pre-rtag=0;pre=p;else pre-rtag=0;pre=p;【例6.16】编制算法对中序线索二叉树进行中序后继线索遍历。inorderthread1(BiThrTree Thrt)inorderthread1(BiThrTree Thrt)BiThrTree p=Thrt-lchild;BiThrTree p=Thrt-lchild;while(p!=Thrt)while(p!=Thrt)while(p-ltag=0)p=p-lchild;while(p
49、-ltag=0)p=p-lchild;printf(%d ,p-data);printf(%d ,p-data);while(p-rtag=1&p-rchild!=Thrt)while(p-rtag=1&p-rchild!=Thrt)p=p-rchild;printf(%d ,p-data);p=p-rchild;printf(%d ,p-data);p=p-rchild;p=p-rchild;【例6.17】编制算法对中序线索二叉树进行中序前驱线索遍历。inorderthread2(BiThrTree Thrt)inorderthread2(BiThrTree Thrt)BiThrTree p
50、=Thrt-rchild;BiThrTree p=Thrt-rchild;while(p!=Thrt)while(p!=Thrt)while(p-rtag=0)p=p-rchild;while(p-rtag=0)p=p-rchild;printf(%d ,p-data);printf(%d ,p-data);while(p-ltag=1&p-lchild!=Thrt)while(p-ltag=1&p-lchild!=Thrt)p=p-lchild;printf(%d ,p-data);p=p-lchild;printf(%d ,p-data);p=p-lchild;p=p-lchild;6.4