数据结构六树

1、第六章 树和二叉树 树是一类重要的非线性数据结构，是以分支关系定义的层次结构6.1 树的定义定义定义：树(tree)是n(n0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点根树中各子树是互不相交的集合A只有根结点的树ABCDEFGHIJKLM有子树的树根子树基本术语结点(node)表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)结点拥有的子树数叶子(leaf)度为0的结点孩子(child)结点

2、子树的根称为该结点的孩子双亲(parents)孩子结点的上层结点叫该结点的兄弟(sibling)同一双亲的孩子树的度一棵树中最大的结点度数结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层深度(depth)树中结点的最大层次数森林(forest)m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先

3、6.2 二叉树定义定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空二叉树性质性质1：) 1(21iii个结点层上至多有在二叉树的第证明：用归纳法证明之 i=1时，只有一个根结点， 是对的 假设对所有j(1j1，则其双亲是i/2l (2) 如果2in，则结点i无左孩子；如果2in，则其左孩子是2il (3) 如果2i+1n，则结点i无右孩

4、子；如果2i+1n，则其右孩子是2i+11log2nn深度为个结点的完全二叉树的具有l性质l性质4：6.3 树的存储结构树的存储结构双亲表示法实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置特点：找双亲容易，找孩子难typedef struct node datatype data; int parent;JD;JD tM;abcdefhgiacdefghib012235551096012345789dataparent0号单元不用或存结点个数如何找孩子结点v孩子表示法v多重链表：每个结点有多个指针域，分别指向其子树的根v结点同

5、构：结点的指针个数相等，为树的度Dv结点不同构：结点指针个数不等，为该结点的度ddata child1 child2 . childDdata degree child1 child2 . childdl孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表孩子结点：typedef struct node int child; /该结点在表头数组中下标 struct node *next; /指向下一孩子结点 JD;表头结点：typedef struct tnode datatype data; /数据域 struct node *fc; /指向第一个孩子结点 TD

6、; TD tM; /t0不用abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找双亲结点l带双亲的孩子链表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgiv孩子兄弟表示法（二叉树表示法）v实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点v特点v操作容易v破坏了树的层次typedef struct node datatype data; struct node *fch, *nsib;JD;abcdefhgi a

7、b c d e f g h i二叉树的存储结构顺序存储结构实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11v链式存储结构v二叉链表typedef struct BiTNode datatype data; struct BiTNode *lchild, *rchild; BiTNode; * BiTree;lchild data rchild ABCDEFG在n个结点的二叉链表中，有n+1个空指针域 AB C D

8、 E F Gl三叉链表typedef struct TriTNode datatype data; struct node *lchild, *rchild, *parent; TriTNode, TriTree;lchild data parent rchildABCDEFG A B C D E F G树与二叉树转换ACBED树ABCDE二叉树 A B C D E A B C D E A B C D E 对应存储存储解释解释v将树转换成二叉树v加线：在兄弟之间加一连线v抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系v旋转：以树的根结点为轴心，将整树顺时针转45ABCDEFGHI

9、ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空v将二叉树转换成树v加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来v抹线：抹掉原二叉树中双亲与右孩子之间的连线v调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIv森林转换成二叉树v将各棵树分别转换成二叉树v将每棵树的根结点用线相连v以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABC

10、DEFGHIJABCDEFGHIJv二叉树转换成森林v抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树v还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ6.4 树和二叉树的遍历树的遍历遍历按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列常用方法先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层

11、的结点ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO二叉树的遍历方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：- + a * b - c d / e f-+a*b-cd/

12、ef- +a *b - c d/e f-+a*b-c d/e fADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:算法的递归定义是：算法的递归定义是：若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 中序遍历左子树中序遍历左子树(递归调用本算法递归调用本算法)； 访问根结点；访问根结点； 中序遍历右子树中序遍历右子树(递归调用本算法递归调用本算法)。v中序遍历的递归算法中序遍历的递归算法void InorderTraverse(BTNode *T) if (T!=NULL) InorderTraverse(T-Lchild) ;visit

13、(T-data) ; /* 访问根结点访问根结点 */InorderTraverse(T-Rchild) ; 中序遍历非递归算法思路：中序遍历非递归算法思路：设设T是指向二叉树根结点的指针是指向二叉树根结点的指针变量，非递归算法是：变量，非递归算法是：若二叉树为空，则返回；否则，若二叉树为空，则返回；否则，令令p=T 若若p不为空，不为空，p进栈，进栈， p=p-Lchild ； 否则否则(即即p为空为空)，退栈到，退栈到p，访，访问问p所指向的结点；所指向的结点； p=p-Rchild ，转，转(1)；直到栈空为止。直到栈空为止。中序遍历的非递归算法：中序遍历的非递归算法：#define M

14、AX_NODE 50void InorderTraverse( BTNode *T) BTNode *p=T ; InitStack(S); while (p!=NULL| !StackEmpty(S) if (p!=Null) Push(S,p) ; p=p-Lchild ; /*向左走向左走到底到底*/ else pop(S,p) ; visit( p-data ) ; p=p-Rchild ; /else 访问结点，向右一步访问结点，向右一步 /while; l中序遍历的非递归算法执行过程中序遍历的非递归算法执行过程ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABC

15、DEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)pABCDEFGiP-A访问：C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B Ep(8)ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E Gp(10)ABCDEFGiP-A访问：C B E G D Fp=NULL(13)

16、ABCDEFGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D F Ap=NULL(15)ADBCD L RAD L RD L RBDCD L R算法的递归定义是：算法的递归定义是： 若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 访问根结点；访问根结点； 先序遍历左子树先序遍历左子树(递归调用本算法递归调用本算法)； 先序遍历右子树先序遍历右子树(递归调用本算法递归调用本算法)。先序遍历:先序遍历序列：A B D Cv先序遍历的递归算法先序遍历的递归算法void PreorderTraverse(BTNode *T) if (T!=NULL)

17、 visit(T-data) ; /* 访问根结点访问根结点 */PreorderTraverse(T-Lchild) ;PreorderTraverse(T-Rchild) ; 说明：说明：visit()函数是访问结点的数据域，其要求视具体问题而定。树采函数是访问结点的数据域，其要求视具体问题而定。树采用二叉链表的存储结构，用指针变量用二叉链表的存储结构，用指针变量T来指向。来指向。void PreorderTraverse(BTNode *T) if (T!=NULL) printf(%dt,bt-data);/* 访问根结点访问根结点 */PreorderTraverse(T-Lchil

18、d) ;PreorderTraverse(T-Rchild) ; 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C先序遍历的非递归算法先序遍历的非递归算法设设T是指向二叉树根结点的指针是指向二叉树根结点的指针变量，非递归算法是：变量，非递归算法是：若二叉树为空

19、，则返回；否则，若二叉树为空，则返回；否则，令令p=T； 访问访问p所指向的结点；所指向的结点； q=p-Rchild ，若，若q不为空，不为空，则则q进栈；进栈； p=p-Lchild ，若，若p不为空，不为空，转转(1)，否则转，否则转(4)； 退栈到退栈到p ，转，转(1)，直到栈空，直到栈空为止。为止。先序遍历的非递归算法先序遍历的非递归算法void PreorderTraverse( BTNode *T) BTNode*p=T, *q ;InitStack(S); while (p!=NULL) visit( p- data ) ; q=p-Rchild ; if ( q!=NULL

20、 ) push(S,q) ; p=p-Lchild ; if (p=NULL) pop(S, p) ; /while中序遍历的非递归算法：中序遍历的非递归算法：void InorderTraverse( BTNode *T) BTNode *p=T ; InitStack(S); while (p!=NULL| !StackEmpty(S) if (p!=Null) Push(S,p) ; p=p-Lchild ; /*向左走到底向左走到底*/ else pop(S,p) ; visit( p-data ) ; p=p-Rchild ; /else 访问结点，访问结点，向右一步向右一步 /wh

21、ile ADBC L R DL R DL R DADCL R D后序遍历序列： D B C A后序遍历:B算法的递归定义是：算法的递归定义是： 若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 后序遍历左子树后序遍历左子树(递归调用本算法递归调用本算法)； 后序遍历右子树后序遍历右子树(递归调用本算法递归调用本算法) ； 访问根结点访问根结点 。v后序遍历的递归算法后序遍历的递归算法void PostorderTraverse(BTNode *T) if (T!=NULL) PostorderTraverse(T-Lchild) ;PostorderTraverse(T-Rchil

22、d) ; visit(T-data) ; /* 访问根结点访问根结点 */ 遍历二叉树的算法中基本操作是访问结点，因遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有此，无论是哪种次序的遍历，对有n个结点的二叉个结点的二叉树，其时间复杂度均为树，其时间复杂度均为O(n) 。后序遍历的非递归算法后序遍历的非递归算法 在后序遍历中，根结点是最在后序遍历中，根结点是最后被访问的。因此，在遍历过程后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左子树，此时根结点

23、进栈。当其左子树遍历完后再搜索到该根其左子树遍历完后再搜索到该根结点时，还是不能访问，还需遍结点时，还是不能访问，还需遍历其右子树。所以，此根结点还历其右子树。所以，此根结点还需再次进栈，当其右子树遍历完需再次进栈，当其右子树遍历完后再退栈到到该根结点时，才能后再退栈到到该根结点时，才能被访问。被访问。 因此，设立一个状态标志变因此，设立一个状态标志变量量tag ：0 ： 结点暂不能访问结点暂不能访问1 ： 结点可以被访问结点可以被访问tag= 其次，设两个堆栈S1、S2 ，S1保存结点，S2保存结点的状态标志变量tag 。S1和S2共用一个栈顶指针。 设T是指向根结点的指针变量，非递归算法是

24、：若二叉树为空，则返回；否则，令p=T； 第一次经过根结点p，不访问： p进栈S1 ， tag 赋值0，进栈S2，p=p-Lchild 。 若p不为空，转(1)，否则，取状态标志值tag ： 若tag=0：对栈S1，不访问，不出栈；修改S2栈顶元素值(tag赋值1) ，取S1栈顶元素的右子树，即p=S1top-Rchild ，转(1)； 若tag=1：S1退栈，访问该结点；直到栈空为止。算法实现：算法实现：#define MAX_NODE 50void PostorderTraverse( BTNode *T) BTNode *S1MAX_NODE ,*p=T ;int S2MAX_NODE

25、, top=0 , bool=1 ;if (T=NULL) printf(“Binary Tree is Empty!n”) ;else do while (p!=NULL) S1+top=p ; S2top=0 ; p=p-Lchild ; if (top=0) bool=0 ; else if (S2top=0) p=S1top-Rchild ; S2top=1 ; else p=S1top ; top- ; visit( p-data ) ; p=NULL ; /* 使循环继续进行而不至于死使循环继续进行而不至于死循环循环 */ while (bool!=0) ;层次遍历二叉树层次遍历二

26、叉树 层次遍历二叉树，是从根结点开始遍历，按层次次层次遍历二叉树，是从根结点开始遍历，按层次次序序“自上而下，从左至右自上而下，从左至右”访问树中的各结点。访问树中的各结点。 为保证是按层次遍历，必须设置一个队列，初始化为保证是按层次遍历，必须设置一个队列，初始化时为空。时为空。 设设T是指向根结点的指针变量，层次遍历非递归算是指向根结点的指针变量，层次遍历非递归算法是：法是：若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T，p入队；入队； 队首元素出队到队首元素出队到p；访问访问p所指向的结点；所指向的结点； 将将p所指向的结点的左、右子结点依次入队。直到队所指向的结点的左

27、、右子结点依次入队。直到队空为止。空为止。#define MAX_NODE 50void LevelorderTraverse( BTNode *T) BTNode *QueueMAX_NODE ,*p=T ;int front=0 , rear=0 ;if (p!=NULL) Queue+rear=p; /* 根结点入队根结点入队 */while (frontdata ); if (p-Lchild!=NULL) Queue+rear=p; /* 左结点入队左结点入队 */ if (p-Rchild!=NULL) Queue+rear=p; /* 左结点入队左结点入队 */ v遍历算法应用v

28、“遍历”是二叉树最重要的基本操作，是各种其它操作的基础，二叉树的许多其它操作都可以通过遍历来实现。如建立二叉树的存储结构、求二叉树的结点数、求二叉树的深度等。v按先序遍历序列建立二叉树的二叉链表，已知先序序列为：v A B C D E G F l求二叉树深度算法ABCDEFG A B C D E F G l统计二叉树中叶子结点个数算法（1）按先序遍历方式建立二叉链表）按先序遍历方式建立二叉链表 对一棵二叉树进行对一棵二叉树进行“扩充扩充”，就可以得到有该二叉，就可以得到有该二叉树所扩充的二叉树。树所扩充的二叉树。ABCDEFG(a) 二叉树二叉树T1(b) T1的扩充二叉树的扩充二叉树T2AB

29、CDEFG? 二叉树的扩充方法是：在二叉树中结点的每一个空链二叉树的扩充方法是：在二叉树中结点的每一个空链域处增加一个扩充的结点域处增加一个扩充的结点(总是叶子结点，用方框总是叶子结点，用方框“”表示表示)。对于二叉树的结点值：。对于二叉树的结点值： 是是char类型：扩充结点值为类型：扩充结点值为“？”； 是是int类型：扩充结点值为类型：扩充结点值为0或或-1； 下面的算法是二叉树的前序创建的递归算法，读入一下面的算法是二叉树的前序创建的递归算法，读入一棵二叉树对应的扩充二叉树的前序遍历的结点值序列。每棵二叉树对应的扩充二叉树的前序遍历的结点值序列。每读入一个结点值就进行分析：读入一个结点

30、值就进行分析： 若是扩充结点值：令根指针为若是扩充结点值：令根指针为NULL； 若是若是(正常正常)结点值：动态地为根指针分配一个结点，将结点值：动态地为根指针分配一个结点，将该值赋给根结点，然后递归地创建根的左子树和右子树。该值赋给根结点，然后递归地创建根的左子树和右子树。利用先序序列创建二叉链表算法实现：利用先序序列创建二叉链表算法实现：#define NULLKY ?#define MAX_NODE 50typedef struct BTNode char data ;struct BTNode *Lchild , *Rchild ;BTNode ;BTNode *Preorder_Cr

31、eate_BTree(BTNode *T) /* 建立链式二叉树，返回指向根结点的指针变量建立链式二叉树，返回指向根结点的指针变量 */ char ch ; ch=getchar() ; getchar(); if (ch=NULLKY) T=NULL; return(T) ; else T=(BTNode *)malloc(sizeof(BTNode) ;Tdata=ch ;Preorder_Create_BTree(T-Lchild) ;Preorder_Create_BTree(T-Rchild) ;return(T) ; 当希望创建图当希望创建图6-10(a)所示的二叉树时，输入的字符

32、序列应当是：所示的二叉树时，输入的字符序列应当是：ABD?E?G?CF?（2）求二叉树的叶子结点数）求二叉树的叶子结点数 可以直接利用先序遍历二叉可以直接利用先序遍历二叉树算法求二叉树的叶子结点数。树算法求二叉树的叶子结点数。只要将先序遍历二叉树算法中只要将先序遍历二叉树算法中visit()函数简单地进行修改就可以函数简单地进行修改就可以。#define MAX_NODE 50int search_leaves( BTNode *T) BTNode*p=T, *q ;InitStack(S); while (p!=NULL) if (p-Lchild=NULL) & (p-Rchild

33、=NULL ) num+ ; q=p-Rchild ; if ( q!=NULL ) push(S,q) ; p=p-Lchild ; if (p=NULL) pop(S, p) ; /whilereturn(num) ;（3）求二叉树的深度）求二叉树的深度 利用层次遍历算法可以直接求得利用层次遍历算法可以直接求得二叉树的深度。二叉树的深度。算法实现：算法实现：#define MAX_NODE 50int search_depth( BTNode *T) BTNode *StackMAX_NODE ,*p=T;int front=0 , rear=0, depth=0, level ;/* l

34、evel总是指向访问层的最后一总是指向访问层的最后一个结点在队列的位置个结点在队列的位置 */if (T!=NULL) Queue+rear=p; /* 根结根结点入队点入队 */level=rear ; /* 根是第根是第1层的最层的最后一个节点后一个节点 */while (frontLchild!=NULL) Queue+rear=p; /* 左结点入队左结点入队 */ if (p-Rchild!=NULL) Queue+rear=p; /* 左结点入队左结点入队 */ if (front=level) /* 正访问的是当前层的最后一个结点正访问的是当前层的最后一个结点 */ depth+

35、 ; level=rear ; 遍历二叉树是按一定的规则将树中的结点排列成一个线性序列，即是对非线性结构的线性化操作。如何找到遍历过程中动态得到的每个结点的直接前驱和直接后继(第一个和最后一个除外)?如何保存这些信息? 设一棵二叉树有n个结点，则有n-1条边(指针连线) ， 而n个结点共有2n个指针域(Lchild和Rchild) ，显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。对结点的指针域做如下规定： 6.5线索二叉树线索二叉树 若结点有左孩子，则若结点有左孩子，则Lchild指向其左孩子，否指向其左孩子，否则，指向其直接前驱；则，指向其直接前

36、驱； 若结点有右孩子，则若结点有右孩子，则Rchild指向其右孩子，否指向其右孩子，否则，指向其直接后继；则，指向其直接后继；为避免混淆为避免混淆,对结点结构加以改进，增加两个标志对结点结构加以改进，增加两个标志域，如图所示。域，如图所示。Lchild Ltag data Rchild Rtag线索二叉树的结点结构线索二叉树的结点结构0：Lchild域指示结点的左孩子1 1：LchildLchild域指示结点的前驱域指示结点的前驱Ltag=0 0：RchildRchild域指示结点的右孩子域指示结点的右孩子1 1：RchildRchild域指示结点的后继域指示结点的后继Rtag= 用这种结点结

37、构构成的二叉树的存储结构；叫做线索链表；指向结点前驱和后继的指针叫做线索；按照某种次序遍历，加上线索的二叉树称之为线索二叉树。线索二叉树的结点结构与示例typedef struct BiThrNode ElemType data;struct BiTreeNode *Lchild , *Rchild ; int Ltag , Rtag ;BiThrNode ; AFHIEGBDC(a) 二叉树 (b) 先序线索树的逻辑形式先序线索树的逻辑形式 结点序列：结点序列：ABDCEGFHIAFHIEGBDCNIL(d) 后序线索树的逻辑形式后序线索树的逻辑形式 结点序列：结点序列：DBGEHIFCA(

38、c) 中序线索树的逻辑形式中序线索树的逻辑形式 结点序列：结点序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNIL 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1 (e) 中序线索树的链表结构中序线索树的链表结构说明：画线索二叉树时，实线表示指针，指向其左、右孩子；说明：画线索二叉树时，实线表示指针，指向其左、右孩子；虚线表示线索，指向其直接前驱或直接后继。虚线表示线索，指向其直接前驱或直接后继。 在线索树上进行遍历，只要先找到序列中的第一个结点，在线索树上进行遍历，只要先找到序列中的第一个结点，然后就可以依

39、次找结点的直接后继结点直到后继为空为止。然后就可以依次找结点的直接后继结点直到后继为空为止。 如何在线索树中找结点的直接后继如何在线索树中找结点的直接后继? ? 树中所有叶子结点的右链都是线索。右链直接树中所有叶子结点的右链都是线索。右链直接指示了结点的直接后继，如结点指示了结点的直接后继，如结点G G的直接后继是结点的直接后继是结点E E。 树中所有非叶子结点的右链都是指针。根据中序树中所有非叶子结点的右链都是指针。根据中序遍历的规律，非叶子结点的直接后继是遍历其右子树遍历的规律，非叶子结点的直接后继是遍历其右子树时访问的第一个结点，即右子树中最左下的时访问的第一个结点，即右子树中最左下的(

40、 (叶子叶子) )结结点。如结点点。如结点C C的直接后继：沿右指针找到右子树的根的直接后继：沿右指针找到右子树的根结点结点F F，然后沿左链往下直到，然后沿左链往下直到Ltag=1Ltag=1的结点即为的结点即为C C的直的直接后继结点接后继结点H H。 如何在线索树中找结点的直接前驱?若结点的Ltag=1，则左链是线索，指示其直接前驱；否则，遍历左子树时访问的最后一个结点(即沿左子树中最右往下的结点) 为其直接前驱结点。 对于后序遍历的线索树中找结点的直接后继比较复杂，可分以下三种情况： 若结点是二叉树的根结点：其直接后继为空； 若结点是其父结点的左孩子或右孩子且其父结点没有右子树：直接后

41、继为其父结点； 若结点是其父结点的左孩子且其父结点有右子树：直接后继是对其父结点的右子树按后序遍历的第一个结点。6.5.1 线索化二叉树线索化二叉树 二叉树的线索化指的是依照某种遍历次序二叉树的线索化指的是依照某种遍历次序使二叉树成为线索二叉树的过程。使二叉树成为线索二叉树的过程。 线索化的过程就是在遍历过程中修改空指针线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后继的过程。使其指向直接前驱或直接后继的过程。 仿照线性表的存储结构，在二叉树的线索链仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点表上也添加一个头结点head，头结点的指针域，头结点的指针域的安排是：的安

42、排是： Lchild域：指向二叉树的根结点；域：指向二叉树的根结点； Rchild域：指向中序遍历时的最后一个结点域：指向中序遍历时的最后一个结点； 二叉树中序序列中的第一个结点二叉树中序序列中的第一个结点Lchild指针指针域和最后一个结点域和最后一个结点Rchild指针域均指向头结点指针域均指向头结点head。 如同为二叉树建立了一个双向线索链表，如同为二叉树建立了一个双向线索链表，对一棵线索二叉树既可从头结点也可从最后对一棵线索二叉树既可从头结点也可从最后一个结点开始按寻找直接后继进行遍历。显一个结点开始按寻找直接后继进行遍历。显然，这种遍历不需要堆栈，如图然，这种遍历不需要堆栈，如图6

43、-126-12所示。所示。结点类型定义结点类型定义#define MAX_NODE 50#define MAX_NODE 50typedef enmuLink , Thread PointerTag ;typedef enmuLink , Thread PointerTag ;/ /* * Link=0 Link=0表示指针，表示指针， Thread=1 Thread=1表示线索表示线索 * */ /typedef struct BiThrNodetypedef struct BiThrNode ElemType data; ElemType data;struct BiTreeNode st

44、ruct BiTreeNode * *Lchild , Lchild , * *Rchild ; Rchild ; PointerTag Ltag , Rtag ;PointerTag Ltag , Rtag ;BiThrNode;BiThrNode;(a) 二叉树二叉树(b) 中序线索树的逻辑形式中序线索树的逻辑形式AFHIEGBDCNILNILAFHIEGBDC中序线索二叉树及其存储结构中序线索二叉树及其存储结构(c) 中序线索二叉链表 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1Thrt 0 1head 1 先序线索化二叉树先

45、序线索化二叉树 void preorder_Threading(BiThrNode *T) BiThrNode *last=NULL, *p=T ;InitStack(S); while (p!=NULL) if (p-Lchild!=NULL) p-Ltag=0 else p-Ltag=1 ; p-Lchild=last ; if (p-Rchild!=NULL) push(S, p-Rchild) ; if (last!=NULL)if (last-Rchild!=NULL) last-Rtag=0 ;else last-Rtag=1 ; last-Rchild=p ; last=p ;p

46、=p-Lchild;if (p=NULL) pop(S,p) ;/ /whileLast-Rtag=1; /* 最后一个结点是叶子结最后一个结点是叶子结点点 */先序遍历的非递归算法先序遍历的非递归算法void PreorderTraverse( BTNode *T) BTNode*p=T, *q ;InitStack(S); while (p!=NULL) visit( p- data ) ; q=p-Rchild ; if ( q!=NULL ) push(S,q) ; p=p-Lchild ; if (p=NULL) pop(S, p) ; /while2 中序线索化二叉树中序线索化二叉

47、树void inorder_Threading(BiThrNode *T) BiThrNode *last=NULL, *p=T ; InitStack(S);while (p!=NULL| !StackEmpty(S)if (p!=NULL) push(S,p); p=p-Lchild; else pop(S,p) ; if (p-Lchild!=NULL) p-Ltag=0 ; else p-Ltag=1 ; p-Lchild=last ; if (last!=NULL) if (last-Rchild!=NULL) last-Rtag=0 ; else last-Rtag=1 ; las

48、t-Rchild=p ; last=p ; p=p-Rchild; last-Rtag=1; /* 最后一个结点是叶子结最后一个结点是叶子结点点 */中序遍历的非递归算法：中序遍历的非递归算法：void InorderTraverse( BTNode *T) BTNode *p=T ; InitStack(S); while (p!=NULL| !StackEmpty(S) if (p!=Null) Push(S,p) ; p=p-Lchild ; /*向左走到底向左走到底*/ else pop(S,p) ; visit( p-data ) ; p=p-Rchild ; /else 访问结点，

49、向右访问结点，向右一步一步 /while 6.5.2 线索二叉树的遍历线索二叉树的遍历 在线索二叉树中，由于有线索存在，在某在线索二叉树中，由于有线索存在，在某些情况下可以方便地找到指定结点在某种遍历些情况下可以方便地找到指定结点在某种遍历序列中的直接前驱或直接后继。此外，在线索序列中的直接前驱或直接后继。此外，在线索二叉树上进行某种遍历比在一般的二叉树上进二叉树上进行某种遍历比在一般的二叉树上进行这种遍历要容易得多，不需要设置堆栈，且行这种遍历要容易得多，不需要设置堆栈，且算法十分简洁。算法十分简洁。1 先序线索二叉树的先序遍历先序线索二叉树的先序遍历void preorder_Thread

50、_bt(BiThrNode *T) BiThrNode *p=T ;while (p!=NULL) visit(p-data) ; if (p-Ltag=0) p=p-Lchild ; else p=p-Rchild 在先序线索二叉树中找结点后继的方法：在先序线索二叉树中找结点后继的方法：（1）若）若Ltag=0, 则则Lchild域直接指向其后继域直接指向其后继（2）若）若Ltag=1, 则则Rchild域直接指向其后继域直接指向其后继2 中序线索二叉树的中序遍历中序线索二叉树的中序遍历void inorder_Thread_bt(BiThrNode *T) BiThrNode *p ;if

51、 (T!=NULL) p=T;while (p-Ltag=0 ) p=p-Lchild; /* 寻找最左的结点寻找最左的结点 */while (p!=NULL) visit(p-data) ; if (p-Rtag=1) p=p-Rchild ; /* 通过右线索找通过右线索找到后继到后继 */ else /* 否则，右子树的最左结点否则，右子树的最左结点为后继为后继 */ p=p-Rchild ; while (p-Ltag=0 ) p=p-Lchild; /else /while/if 在中序线索二叉树中找结点后继的方法：在中序线索二叉树中找结点后继的方法：（1）若）若Rtag=1, 则则

52、Rchild域直接指向其后继域直接指向其后继（2）若）若Rtag=0, 则结点的后继应是其右子树则结点的后继应是其右子树的左链尾（的左链尾（Ltag=1)的结点的结点拓展思考：拓展思考：在中序线索二叉树中找结点前驱的方法：在中序线索二叉树中找结点前驱的方法：（1）若）若Ltag=1, 则则Lchild域直接指向其前驱域直接指向其前驱（2）若）若Ltag=0, 则结点的前驱应是其左子则结点的前驱应是其左子树的右链尾（树的右链尾（Rtag=1)的结点的结点中序线索树的逻辑形式中序线索树的逻辑形式AFHIEGBDCNILNIL中序线索二叉树及其存储结构中序线索二叉树及其存储结构(c) 中序线索二叉链

53、表 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉树 0 1头结点：Ltag=0, Lchild指向根结点Rtag=1, Rchild指向遍历序列中最后一个结点遍历序列中第一个结点的Lchild域和最后一个结点的Rchild域都指向头结点 A B D C ET中序序列：BCAED中序线索二叉树00001111116.6 二叉树的应用哈夫曼树哈夫曼树(Huffman)带权路径长度最短的树定义路径：从树中一个结点到另一个结点

54、之间的分支构成这两个结点间的路径长度：路径上的分支数树的路径长度：从树根到每一个结点的路径长度之和树的带权路径长度：树中所有带权结点的路径长度之和结点到根的路径长度权值其中：记作：kknkkklwlwwpl1lHuffman树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL1

55、vHuffman树应用v最佳判定树等级分数段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60a2n-1 */ typedef structint Weight ; /* 权值域权值域 */int Parent , Lchild , Rchild ; HTNode ;(2) Huffman树的生成树的生成算法实现算法实现void Create_Huffman(int n, HTNode HT , int m)

56、 /* 创建一棵叶子结点数为创建一棵叶子结点数为n的的Huffman树树 */ int w ; int k , j ;for (k=1 ; km ; k+) if (k=n) printf(“n Please Input Weight : w=?”); scanf(“%d”, &w) ;HTk.weight=w ; /* 输入时，所有叶子结点都有权值输入时，所有叶子结点都有权值 */else HTk.weight=0; /* 非叶子结点没有权非叶子结点没有权值值 */HTk.Parent=HTk.Lchild=HTk.Rchild=0 ; /* 初始化向量初始化向量HT */ for

57、(k=n+1; km ; k+) int w1=32767 , w2=w1 ; /* w1 , w2分别保存权值最小的两个权值分别保存权值最小的两个权值 */ int p1=0 , p2=0 ; /* p1 , p2保存两个最小权值的下标保存两个最小权值的下标 */for (j=1 ; j=k-1 ; j+) if (HTk.Parent=0) /* 尚未合并尚未合并 */ if (HTj.Weightw1) w2=w1 ; p2=p1 ; w1=HTj.Weight ; p1=j ; else if (HTj.Weightw2) w2=HTj.Weight ; p2=j ; /* 找到权值最小的两个值及其下标找到权值最小的两个值及其下标 */HTk.Lchild=p1 ; HTk.Rchild=p2 ;HTk.weight=w1+w2 ;HTp1.Parent=k ; HTp2.Parent=k ; 说明：生成说明：生成Huffman树后，树的根结点的下标是树后，树的根结点的下标是2n-1 ，即，即m-1 。(3) Huffman编码算法编码算法 根据出现频度根据出现频度(权值权值)Weight，对叶子结点的，对叶子结点的Huffman编码有编码有