,第六章 树与二叉树学习导读,树型结构 Tree 是一类重要的非线性数据结构。其中以树和二叉树最为常见，树是以分支关系定义的层次结构。人类社会的族谱和各种社会组织机构都可用树来形象表示。编译程序中，可用树来表示源程序的语法结构。数据库系统中，树型结构也是信息的重要组织形式之一。本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树的转换关系，最后介绍一个典型的应用例子：哈夫曼树和哈夫曼编码。,1. 树的定义和根本术语 2.二叉树,3.遍历二叉树和线索二叉树,4.树与森林,5.赫夫曼树及其应用,6.1 树的定义和根本术语,1、树(Tree)的定义 树是nn0 个结点的有限集。在任意一棵非空树中：,1有且仅有一个特殊的称为根(Root)的结点 ； 2当n1时，其余结点可分成mm 0个互不相交的有限集T1,T2, ,T m，,其中每一个集合本身又是一棵树，并 且称为根的子树Sub Tree。,如图6.1：A为根结点;B，E，F、,C，G，H，J，K，L，M、,D，I分别为根结点A的三棵子树。,B，C，D分别为三棵子树的根结点。,显然这是一个递归定义。,图6.1 树的示意图,A,B C D,E F G H I,J K L M,Root,A,B C D,E F G H I,J K L M,Root,上述树的定义加上树的一组根本操作构成抽象数据类型树的定义:,ADT Tree,数据对象D:D是具有相同特性的数据对象的集合。,数据关系R:假设D为空集，那么称为空树；,假设D仅含一个数据元素，那么R为空集，否那么R=H，H是如下二元关系：,在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；,假设D-root ，那么存在D-root的一个划分D1，D2，Dmm0，对任意jk1j，km有DjDk =，且对任意的i1i m，唯一存在数据元素xiDi，有root，xiH；,对应于D-root 的划分，H-root，x1 ， root，xm 有唯一的一个划分H1，H2， ，Hmm 0，对任意jk1j，km有Hj Hk =，且对任意的i1i m，Hi是Di上的二元关系，Di，Hi,是一棵符合本定义的树，称为根root的子树。,根本操作P：15个。 P119, ADT Tree,A,B C D,E F G H I,J K L M,Root,(A(,B,(,E,F,(,I,J,),C,D,(,G,H,),第一层,第二层,第三层,第四层,高度=4,A,B,C,D,E,G,H,I,F,J,J,I,H,G,F,E,D,C,B,A,A,B,E,F,I,J,C,D,G,H,E,广义表表示法,树形表示法,嵌套集合表示法,凹入表表示法,树的各种表示法,I,J,2、树中结点的度(Degree)与树的度,树中每个结点的分枝数称为该结点的度。例如图6.1,中根结点A的度为3。B的度为2。G的度为4。而E，F，,H，I，J，K，L，M的度全为零。树的度是树中结点的最,大度数。所以图6.1的度为4。在实际应用中我们称度为零,的结点为叶子(Leaf)结点，,称度不为零的结点为分枝结,点。如图6.1中E，F ，H，I,，J，K，L，M都是叶子结,点，B，C，D，G都是分枝,结点。从树中我们知道度为,4,的树中结点的度有0，1，2，,3，4,五,种。因而可推知度为,m,的树中结点的度有,m+1,种。,A,B C D,E F G H I,J K L M,Root,3、孩子(Child)结点与双亲(Parent)结点,树中结点的子树的根结点称为该结点的孩子结点。相反，称,该结点为孩子结点的双亲。例如图6.1中，B，C，D是根结点A的三,个孩子结点。A为B，C，D的双亲。而，B，C，D三个结点又互称为,兄弟(Sibling)结点它们具有同一个双亲 。而E，F，G，H，I,称为堂兄弟它们的双亲称为兄弟结点 。祖先结点是从根结点,到达某结点所经过分枝上的所有结点,通称为该结点的祖先。例如 A，C，G,为结点J，K，L，M的祖先。子孙结点,以某结点为根的子树中的任一结点都,称为该结点的子孙。例如G，H， J，,K，L，M都是C的子孙。,A,B C D,E F G H I,J K L M,图6.1 树的示意图,A,B C D,J K L M,4、树中结点的层数(Level),从根结点开始，根为一层结点，,其孩子结点为二层结点依次类推，,叶子结点为最下层结点。例如:,右图示。这种分层的好处是树中,结点的最大层数称为该树的高度,深度。所以右图用黑数字,所示树的高度深度为4。,实际应用中树也可以以根为0层结点开始，此时，结点的层数为,从根到达该结点的路径长度。如果，知道树中每层结点的个数，,便可计算出对树中所有结点查找一遍所花费的总代价。使用哪种,方式用户可根据系统需要进行选择。,0,.1,1,2,2,E,.,F G H I 3,3.,.4,Root,5、森林Forest) 是 m (m=0)棵互不相交的树的集合可以看成是把一棵树的根结点去掉，所得到的子树构成森林 。例如图6.2为图6.1去掉根结点A，以其三个孩子结点B，C，D为根的三棵子树构成的森林。,6、有序树与无序树,如果树中每个结点的孩子结点规定从左到右是有次序的不许,随意改动那么，称该树为有序树。否那么称为无序树。图6.3为相,同的无序树，不同的有序树。,B C D,E F G H I,J K L M,图6.2 森林,A A,B C C B,B B,A C C A,图6.3,就逻辑结构而言，任何一棵树都是一个二元组,Tree=(Root,F),其中：Root是数据元素，称为树的根结点;F是,m(m=0)棵树的森林,F=(T1,T2,Tm),其中Ti=(ri,Fi),称为根root的第i棵子树;当M!=0时，在树根和其子树,森林之间存在以下关系：,RF =| i= 1,2,m,m0,这个定义将有助于得到森林和树与二叉树之间转换,的递归定义。,6.2 二叉树BinaryTree),二叉树的定义,二叉树是每个结点至多有两个孩子结点的一种树。其中两,个孩子结点分别被称为左孩子结点和右孩子结点。而以左,孩子结点为根的子树称为左子树，以右孩子结点为根的子,树称为右子树。另外，二叉树是有序树，其左右孩子的次,序不能任意颠倒。 P121-122,二叉树的五种根本形态如下：,只有根 只有右子树 有左右子树,空二叉树 只有左子树,6.2.2 二叉树的性质,性质1 在二叉树的第i层上至多有2 个结点i 1。,利用归纳法容易证明该性质。,i=1时，只有一个根结点。2 =2 =1是正确的。,现假设对所有的j ，1 ji，命题成立，第j层上至多有2 个结点。,那么可以证明j=i时命题也成立。,由归纳假设：第i-1层上至多有2 个结点。由于二叉树的每个结点,的度至多为2，故在第i层上的最大结点数为第i-1层的最大结点数的,2倍，即2 * 2 =2 。,性质2 深度为K的二叉树至多有2 - 1个结点k 1。,由性质1可见，深度为K的二叉树的最多结点数,第i层上的最大结点数 = 2 =2 -1=1+2+4+8+ +2,i-1,i-1,0,j-1,i-2,i-2,i -1,k,k,i=1,k,i=1,i-1,k,K-1,性质3,对任何一棵二叉树T，如果其终端即叶子结点数为n0，度为,2的结点数为n2 ，那么 n0=n2 +1。,证明：,设n1为二叉树中度为1的结点数。所以二叉树结点的总个数为,n= n0+n1+n2 6-1,又设B为二叉树的分枝总数，那么B=n-1。又有B =n1+2n2。,于是得,n-1=n1 +2n2,整理得,n= n1 +2n2+1 6-2,把6-1代入6-2得n0+n1+n2 = n1 +2n2+1,整理得 n0 =n2+1,结果得证。,满二叉树,一棵深度为K且含有2 -1个结点的二叉树称为满二叉树 。这种,树的特点是每一层上的结点个数都是最大结点数。如图6.5所示。,对于一棵满二叉树 ，从根结点向下，同层从左到右进行连续编号,又可引出完全二叉树的定义。,完全二叉树,深度为K，具有N个结点的二叉树 ，当且仅当其每一个结点都与,深度为K的满二叉树中编号从1至N的结点完全一一对应即结点的,编号与位置都相同时，称该二叉树为完全二叉树。如图6.6 。,图6.5 满二叉树 图6.6 完全二叉树,1,2 3,4 5 6,8 9,10 11 12,2 3,4 5 6 7,8 9 10 11 12 13 14 15,1,1,7,k,1,上面的两棵 二叉树都不是完全二叉树。,性质4 具有n个结点的完全二叉树的深度为 K = log n +1 。,证明：假设深度为K，那么根据性质2 和完全二叉树的定义有,2 - 1 n 2 -1 或 2 n 2,于是K-1 log n K ， 因为 K是整数 ，所以 K = log n +1,2 3,4 5,6 7,1,2 3,4 5,6 7,7,8 9,K-1,k,K-1,k,2,2,2,性质5 如果一棵有n个结点的完全二叉树其深度为 log n +1的,结点按层编号，那么对任一结点i1 i n，有,如果i =1,那么结点i是二叉树的根，无双亲；如果 i1,那么其双亲PARENT(i)结点是 i/ 2,如果2in，那么结点i无左孩子结点；否那么其左孩子结点,LCHILDi的编号为2i。,3如果2i +1n ，那么结点i无右孩子结点；否那么其右孩子结点RCHILDi的编号为2i+1。,i,/ 2,i i+1,2i 2i+1 2i+2 2i+3,2,思考题,1、一棵完全二叉树中的某个结点，如果没有左孩子,结点，那么其一定没有右孩子。这种说法正确吗？,2、具有N个结点的一棵完全二叉树中，编号最小的,叶子结点的编号是多少？,3、高度为K的一棵完全二叉树中，结点的总个数最,多是多少？最少是多少？,4、设一棵满二叉树中，结点的总个数为20 40间,的一个素数，问满二叉树中共有多少个叶子结点？,5、一棵完全二叉树中结点的总个数是一个偶数，问,该完全二叉树中有多少个度为一的结点？,6、设一棵完全二叉树中结点I的堂兄弟结点的编号,是2i+3，问该堂兄弟结点的双亲结点编号是多少？,6.2.3 二叉树的存储,1、二叉树的顺序存储,对于一棵高度为K的完全二叉树或满二叉树，可以直接用顺,序方式存储。如图6.7示。,#define MAX_TREE_SIZE 100 最大结点数,Typedef TElemType SqBiTreeMAX _TREE_SIZE0号存储根,SqBiTree bt;,序号,地址,图6.7 完全二叉树的顺序存储,1 a,2 b 3 c,4 d 5 e 6 f 7 g,h i j k l,8 9 10 11 12,a b c d e f g h i j k l,1 2 3 4 5 6 7 8 9 101112,0 1 2 3 4 5 6 7 8 9 10 11,bt,一般二叉树的顺序存储,右图为一棵二叉树，,如果要用顺序存储的方式,进行存储，那么，必须对,树中结点按照完全二叉树,或满二叉树的规那么进,行顺序编号。才可以实现,顺序存储。,从图6.8中可以看出对 图6.8一般二叉树,二叉树用顺序存储空间利,用率低。同学们可以考虑,图6.9所示的一般二叉树,用顺序存储计算机应分配,多少存储单元？实际应用,多少个单元？,图6.9一般二叉树,a,2 b c 3,5,d,10,e 11 f,1,1 2 3,4,5,6 7 8 9,1011,12,a b c,0,d,0 0 0 0,e f,1 A,2 B 3 C,6 D 7 E,14 F 15 G,2、二叉树的链式存储结构,由二叉树的定义得知，二叉树的结点有一个数据元素和分别指示其,左、右孩子的两个分枝构成，所以表示二叉树的链表中的结点至少,应含有三个域：数据域和左、右孩子指针域。,如图6.10示。在实际工作中有时需要查找结点的双亲，为此在结点,中还要增加一个指向其双亲结点的指针域。如图6.11示.,图6.10含有两个指针域,图6.11含有三个指针域,data,lchild rchild,lchild,data rchild,lchild data parent rchild,A,B,C D,E F,A,B,C D,E,F, ,A, ,B, C D, E F ,/- 二叉树的二叉链表存储表示 -,typedef struct BiTNode P127,TElemType data;,struct BiTNode *lchild, *rchild; /, BiTNode, *BiTree;,/-地区根本操作的函数原型说明局部-,Status CreateBiTree(BiTree ,/按先序次序输入二叉树结点的值，空格表示空树，构造二叉链表的二叉树T,Status PreOrderTraversa(BiTree T,Status(*Visit)(TElemType e);,/先序遍历二叉树T， Visit是对结点操作的应用函数,Status InOrderTraversa(BiTree T,Status(*Visit)(TElemType e);,/中序遍历二叉树T， Visit是对结点操作的应用函数,Status PostOrderTraversa(BiTree T,Status(*Visit)(TElemType e);,/后序遍历二叉树T， Visit是对结点操作的应用函数,Status LevelOrderTraversa(BiTree T,Status(*Visit)(TElemType e);,/层序遍历二叉树T， Visit是对结点操作的应用函数,6.3 遍历二叉树和线索二叉树,6.3.1 遍历二叉树,1、遍历 Traversing是按照某种规那么对树中每个结点访问,且仅访问一次的过程。我们已经知道二叉树中的每个结点都有,三个域：数据域、左孩子指针域、右孩子指针,域。分别用D、L、R表示。那么遍历二叉树的顺序,就有DLR、LDR，LRD、DRL、RDL、RLD六种方式。,如假设限定先左后右，那么只有前三种。它们分,别称为先根序遍历、中根序遍历 和后根序遍历。,2、三种遍历方式,1先根序遍历(DLR)对于一棵非空的二叉树：,1首先访问根结点；(D),2再按先根序遍历左子树；(L),3最后按先根序遍历右子树；R,按这种方式遍历右图的二叉树所得的顺序为,abdfghce,D,L,R,a,b c,d e,f,g,h,2中根序遍历(LDR) 对于一棵非空的二叉树,1按中根序遍历左子树；(L),2访问根结点；(D),3按中根序遍历右子树；R,按这种方式遍历右图的二叉树所得到的,输出序列为：bfdhgaec.,3) 后根序遍历 对于一棵非空的二叉树有 图6.12,1按后根序遍历左子树；L,2按后根序遍历右子树；R,3访问根结点； D,按这种方式遍历右上图的二叉树所得到的输出序列为：,fhgdbeca,由上面的分析可知对于同一棵二叉树用三种不同的遍历方式,都可以查找到所有结点。,a,d e,h,b c,f g,练习,分别写出按三种遍历方式遍历所给两棵二叉树的,输出序列。,A,D E,* /,c d,B C,F G,_,a + e f,DLR: ABDFCEG,LDR: BFDAEGC,LRD: FDBGECA,DLR: - * a + c d / e f 波兰式,LDR: a*c + d e / f 中缀式,LRD: a c d + * e f / - 逆波兰式,波兰式的运算法那么：一个二元运算符后，假设紧跟着两个运算数，那么立即运算求值。,逆波兰式的运算法那么：两个运算数后，假设紧跟着一个二元运算符，那么立即运算求值。,A * (c + d) e / f,3、把一个算术表达式转换成一棵二叉树的原那么,1运算优先级，从根向下逐层增高。根的运算优先级最低。,2每个运算数形成一个叶子结点；每个运算符形成一个分枝结点。,3一个二元运算符的前项形成其左子树；一个二元运算符的后项形成其右子树。,显然这种转换方式括号不显示，所以不能用中序遍历方式计算求值。,练习：把算术表达式a*b/(c+d)-e/f*(g-h)/i 转换成一棵二叉树，,然后，写出用三种方式遍历它的输出序列。,五、二叉树遍历的算法设计分析,1、递归算法设计分析,递归是指算法自己调用自己称直接递归或通过其他算法,调用该算法间接递归的过程。,1先根序遍历递归算法,Status PreOrderTraverse ( BiTree T, Status(*Vist)(TELemType e) ,/Visit是访问数据元素操作的应用函数。,/先根序遍历递归算法，对每个数据元素凋用函数Visit。,/ 最简单的Visit函数是：,Status PrintElemnt (TELemType e) ,prinrf ( e );,return OK;,if ( T) ,if ( Visit ( T- data),if ( PreOrderTraverse( T- Lchild, Visit),if ( PreOrderTraverse( T-Rchild,Visit) return OK;,return ERROR;, else return OK ;,2中根序遍历递归算法,Status INOrderTraverse ( BiTree T, Status(*Vist)(TELemType e) ,/Visit是访问数据元素操作的应用函数。,/先根序遍历递归算法，对每个数据元素凋用函数Visit。,/ 最简单的Visit函数是：,Status PrintElemnt (TELemType e) ,prinrf ( e );,return OK;,if ( T) ,if (INOrderTraverse( T- Lchild, Visit),if ( Visit ( T- data),if (INOrderTraverse( T-Rchild,Visit) return OK;,return ERROR;, else return OK ;整个遍历结束,3)后根序遍历递归算法,Status PostOrderTraverse ( BiTree T, Status(*Visit)(TELemType e) ,/Visit是访问数据元素操作的应用函数。,/先根序遍历递归算法，对每个数据元素凋用函数Visit。,/ 最简单的Visit函数是：,Status PrintElemnt (TELemType e) ,prinrf ( e );,return OK;,if ( T) ,if ( PostOrderTraverse( T- Lchild, Visit),if ( PosyOrderTraverse( T-Rchild,Visit),if ( Visit ( T- data) return OK ;,return ERROR;, else return OK ;遍历结束,A,B,D,C,E,F,(2)中根序遍历递归算法,void Inorder ( BiTree T) , if ( T) , Inorder( T- Lchild);, printf ( “%c,T- data);, Inorder( T-Rchild,);, , / Inorder,Inorder ( T=&A), printf A,Inorder ( T=&B), printf B,Inorder ( T=&C), printf C,Inorder ( T=&D), printf D,Inorder ( T=&E), printf E,Inorder ( T=&F), printf F,Inorder ( T=NULL), ,Inorder ( T=NULL), ,Inorder ( T=NULL), ,Inorder ( T=NULL), ,Inorder ( T=NULL), ,Inorder ( T=NULL), ,Inorder ( T=NULL), ,中序遍历踪迹示意图,P78图,void Inorder ( BiTree T) , if ( T) , Inorder( T- Lchild);, printf ( “%c”,T- data);, Inorder( T-Rchild,);, , / Inorder,A,B,D,C,E,F,T,2、非递归算法设计分析,我们以中序遍历为例分析一个,递归算法如何转换成一个非递归,算法。对于任何一棵以链表形式,存储的二叉树，其根结点地址是,唯一的地址，遍历从根开始。,即右图中首先找到根结点A，但是，,根据中序遍历的规那么不能马上访问A，,必须首先遍历A的左子树，显然，这时,也不能把A的地址丧失，因为结点A与其右子树,还没有访问。同样，得到结点B也不能访问 B ，,也不能丧失 B 的地址。必须另申请一局部空间,把 那些左子树 没有访问 完的 所遇到 的 所有结点,地址保存起来。如右图所示，把 A，B，D 三个,结点地址保存起来即A，B，D。,A,B,D E,H,I J,C,F,G,(A),(B),(D),A,D E,I J,C,F,G,H,分析中序遍历序列DIGJBEAFHC ，,遍历过程中保存结点的顺序是ABD，,而访问输出的顺序确是DBA ，由此,可知用来保存遍历过程中所遇到的,暂时不能访问的结点地址的辅助空,间的结构应为栈。这就是说要把一 图6.13,个递归算法转换成非一个递归算法时必须设置一个辅助空,间栈，用来保存断点参数包括返回地址与有关数据。,所以非递归算法中必有进栈，退栈操作。,假设，一棵含有N个结点的二叉树，问所需的辅助空,间栈的容量是多少？,B,(树的高度),1)中序遍历的非递归算法 P131算法6.3,Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e),IniStack(S); /置空栈,p = T ; /变量P代替根结点T，起保护根的作用,while ( p | ! StackEmpty(s) /当结点P存在或栈S不空时重复,if (p) Push( S, P ); P = P-Lchild;/P存在将P进栈，遍左,else /P为空,Pop(s, p ) ; /栈不空，退栈,if (! Visit (P-data) return ERROR;/假设P不存在 ，那么错,P = P- rchild ;/得到右孩子结点，遍历右子树,/else, /while,return OK;, / InOrderTraverse,2)后序遍历的非递归算法 (S),在设计算法前，我们先分析一下后序遍历与其它遍历有何,不同。从先、中序遍历过程中可,以看出每个结点都只需进一次栈。,但，后序遍历的过程中每个结点,都必须进两次栈。第一次进栈保,存是为了遍历该结点的左子树；,第二次进栈保存是为了遍历该结,点的右子树；只有结点第二次从,栈中退出时，才能访问该结点。,因而，必须设置能区分结点两次,进栈的标志。设置标志的方法不,是唯一的，在实际应用中一般都,在栈中设置标志位B。,A,B,D E,I J,C,F,G,H,ADR,B,A 0,B 0,D 0,当某结点第一次进栈时，其标志位置0，第二次进栈时，其标志位置1。当从栈中退出某结点时，同时将其标志位的值退出。然后，通过判别从栈中退出的标志位的值是0、还是1，来决定是否能访问当前结点。是1，那么访问该结点。是0，那么再将结点进栈，同时，,将标志为置1。如图6.14D进栈后应遍历其左子树，但D无左孩子。,图6.14,此时将结点D与其标志位值0从栈中退出。经过判别不能访问，那么将,D再次进栈，同时把其标志位置1。然后，遍历D的右子树。,A,B,D E,I J,C,F,G,A 0,B 0,D 0,D 1,B 0,A 0,G 0,I 0,H,后序遍历的非递归算法,Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e),IniStack(S); (置空栈,p = T ; 变量P代替根结点T，起保护根的作用,while ( p ! StackEmpty(s) 当结点P存在或栈S不空时重复,if (p) Push( S, P,B );(P存在将P进栈， B =0),P = P-Lchild;遍历左子树,else P为空,Pop(s, p ,B) ; 栈不空，退栈 ,if( B=0) Push( S, P,B ); ( B = 1),P = P- rchild ; (遍历右子树),else if (! Visit (P-data) return ERROR;假设P不,存在 ，那么错,P=null; while,return OK;, PostorderTraverse,注意：前边各种算法中调用的函数VISIT实际上是一个软接口，用户对结点数据的各种操作要求，通过修改它就可以实现。,3、生成一棵二叉树的算法,构造一棵二叉树的链表存储算法不是唯一的，我们这里采用类似于先序的方式。例如按以下顺序读入字符符号 代表空格字,ABC DE G F ,用下面的算法便可建立相应的二叉树。,Status CreateBiTree(BiTree &T) ,scanf ( 读入一个字符,if (ch = ) T = NULL; ,else 字符为空建立空树),if (!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);,T-data = ch; 生成根结点,CreateBiTree( T- lchild ); 构造左子树,CreateBiTree( T-rchild ); 构造右子树, return OK; P131算法6.4,A,B,C D,E F,A,B,C D,E,F, ,G, G ,作业题,1、T为一棵二叉树的根结点，设计把树中每个结点的左右孩子结点交换的算法。,2、T为一棵二叉树的根结点，设计把树中每个单分支结点，用添加数据值为0的新结点变为双分支结点的算法。,3、T为一棵二叉树的根结点，设计把树中值为X的结点找出，,并将它的两个孩子分别作为根生成两棵子树的算法。,4、T为一棵二叉树的根结点，设计计算该树高度深度的,算法。,5、T为一棵二叉树的根结点，树种结点的数据值都是正整数其中只有一个值是寄数，设计找出该结点的算法。,6、T为一棵二叉树的根结点，设计计算该树中结点总个数的,算法。,7、T为一棵二叉树的根结点，按先序遍历该树的输出序列为,ABDFGHCE，按中序遍历该树的输出序列为BFDHGAEC，要求画出这棵二叉树。,6.3.2 线索二叉树,分析二叉树的链表存储，我们发现有许多结点没有孩子结点，因此这些结点的孩子指针域就白白浪费可以证明含有N个结点的二叉树中共空闲N+1个指针域。如右以下图中共有8个结点，空闲字段共有9个。另外，一棵二叉树从理论上讲可以用不同的6种方式进行遍历即一树共享。但是，在实际系统中只使用一种方式就可以。基于上述两个因素，我们引出新的树线索二叉树。,1线索二叉树 是利用二叉树中结点的空闲字段来记录某种遍历过程的二叉树。,2线索二叉树 构成过程,当用某种遍历方式遍历一棵二叉树时，如果,当前结点P的左孩子指针域为空,P-lchild=null那么用其存放P的遍历前驱,结点地址即在访问结点P之前刚刚访问过,的结点；假设P的右孩子指针域为空,P-rchild= null ，那么用其保存P的遍历,后继结点地址。右图为先序遍历的线索二,叉树红色线代表线索,A,B,E F,C,D,G,H,nil,3线索二叉树的存储,从上分析可知在线索二叉树中左右孩子指针域中存放着两种不同的结点地址号。一种是该结点的左右孩子结点地址；另一种是该结点遍历前驱或遍历后继结点地址。为了区分在应用时，我们在每个结点上增设两个标志位如以下图示 (ltag , rtag ),其中,ltag=,rtag= 0 rchild 域存放结点的右孩子结点地址,1 rchild 域存放结点的遍历后继结点地址,lchild ltag data rtag rchild,0,lchild 域存放结点的左孩子结点地址,1,lchild 域存放结点的遍历前驱地址,线索二叉树的存储表示：,Typedef enm PointerTagLink, Thread ; Link=0, Thread =1,Typedef struct BiThrNode ,TelemType data ;,struct BiThrNode *lchild, * rchild ;左右孩子指针,pointerTag Ltag, Rtag ; 左右标志,BiThrNode, * BiThrTree;,4线索二叉树的建立算法,由前边的讲述可知线索化的实质是利用二叉树中的空指针域存放前驱或后继结点地址，而前驱或后继结点地址只有在遍历树的过程中才能得到，因此线索化的过程即为在遍历中修改空指针域的过程。为此，需设置一个保存遍历前驱的指针变量pre，另外，设thrt为头结点指针，这样建立的线索二叉树为一个双向线索链表。,如图6.11所 示。下面我们以中序遍历为例来分析建立中序线索二叉树的算法。,-,+ *,a * e f,b -,c d,nil,nil,0 1,0 - 0,0 + 0 0 * 0,1 a 1 0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,图6.15 中序遍历线索二叉树的逻辑结构与存储结构,说明 ： 图中黑色箭头线为结构 ；红色箭头线为线索。,4建立中序线索二叉树的算法分析,Status InOrderThreading(BiThrTree & Thrt,BiThrTree T),if (!(Thrt = ( BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW);,Thrt-Ltag = Link; 0,Thrt-Rtag=Thread; 1 建立头结点,Thrt-rchild = Thrt; 右指针回指,if (!T) Thrt-Lchild = Thrt; 假设二叉树为空，那么左指针回指,else ,Thrt-Lchild = T; pre= Thrt；T存在与头结点链接,InThreading(T); 调用中序遍历进行中序线索化P135算法6.7,pre-rchild = Thrt; pre-Rtag = Thread;最后结点线索化),Thrt-rchild = pre; ,return OK;, / InOrderThreading,0 1,T,Thrt,pre,P134算法6.6,Void InThreading(BiThrTree p) 中序线索化过程,if (P) ,InThreading(p- lchild); 左子树线索化,if (! P-lchild)p-Ltag= Thread; p-lchild= pre;,前驱线索,if (!pre-rchild)pre-Rtag=Thread;pre-rchild=p;,后继线索),pre = p; 修改pre指向p的前驱,InThreading( p- rchild); 右子树线索化, InThreading,其他次序的线索二叉树的建立过程与上述中序线索二叉树的建,立完全类似。同学可自己编写算法。这里不再一一讲述。,P135算法6.7,0 - 0,0 + 0 0 * 0,1 a 1 0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,Status InOrderThreading(BiThrTree & Thrt,BiThrTree T),if(!(Thrt =( BiThrTree),malloc,(sizeof(BiThrNode)exit(OVER),0,1,0 - 0,0 + 0 0 * 0,1 a 1 0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,Thrt-Ltag = Link0; Thrt-Rtag=Thread 1;建立头结点,Thrt-rchild = Thrt; 右指针回指,0,1,0 - 0,0 + 0 0 * 0,1 a 1 0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,if (!T)Thrt-Lchild = Thrt; 假设二叉树为空，那么左指针回指,else Thrt-Lchild = T; pre= Thrt；T存在与头结点链接,T,pre,0,1,0 - 0,0 + 0 0 * 0,1 a 1 0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,T,pre,InThreading(T);,调用中序遍历进行中序线索化,Void InThreading(BiThrTree p) 中序线索化过程,if (P) InThreading(p- lchild); 左子树线索化,p- lchild,0,1,0 - 0,0 + 0 0 * 0,1 a 1 0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,T,pre,InThreading(T);,调用中序遍历进行中序线索化,Void InThreading(BiThrTree p- lchild) 中序线索化过程,f (p- lchild) InThreading(p- lchild - lchild); 左子树线索化,p- lchild,p- lchild - lchild,p- lchild - lchild=NULL,0,1,0 - 0,0 + 0 0 * 0,a 1 0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,T,pre,InThreading(T);,调用中序遍历进行中序线索化,p,if (! P-lchild)p-Ltag= Thread; p-lchild= pre;前驱化,if (!pre-rchild)pre-Rtag=Thread;pre-rchild=p;后继),pre = p; 修改前驱,pre,1,0,1,0 - 0,0 + 0 0 * 0,1,a 1 0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,T,pre,p pre,InThreading( p- rchild);,右子树线索化,0,1,0 - 0,0 + 0 0 * 0,1,a,0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,T,p,InThreading( p- rchild);,右子树线索化,pre,if (! P-lchild)p-Ltag= Thread; p-lchild= pre;前驱化,if (!pre-rchild)pre-Rtag=Thread;pre-rchild=p;后继),pre = p; 修改前驱,pre,1,0,1,0 - 0,0 + 0 0 * 0,1,a,1,0 * 0 1 e 1 1 f 1,1 b 1 0 - 0,1 c 1 1 d 1,thrt,bt,T,p,pre,InThreading( p- rchild);,右子树线索化,p-rchild,InThreading(p - rchild - lchild); 左子树线索化,p-rchild-lchild,p-rchild-lchild-lchild=NULL,0,1,0 - 0,0 + 0 0 * 0,1,a,1,0 * 0 1 e 1 1 f 1,b 1 0 - 0,1 c 1 1 d 1,thrt,bt,T,p,p pre,if (! P-lchild)p-Ltag= Thread; p-lchild= pre;前驱化,if (!pre-rchild)pre-Rtag