数据结构 第6章 树和二叉树.ppt

第六章第六章 树和二叉树树和二叉树（一）教学目的： 掌握树和二叉树的定义及存储结构；二叉树的基本操作；树和二叉树的应用二）教学重点： 1、树的定义及相关术语 2、二叉树的定义、存储结构和基本运算的实现 3、二叉树的遍历，二叉树与树和森林的相互转换 4、哈夫曼树及应用数组的定义及其存储（三）教学难点： 1、二叉树的定义、存储结构和基本运算的实现 2、哈夫曼树及应用6.1树的概念和基本术语6.2二叉树 6.3遍历二叉树和线索二叉树6.4树与森林6.6哈夫曼树 基本内容：6.16.1树的概念和基本术语树的概念和基本术语一、树的定义一、树的定义 树是由树是由 n (n n (n   0) 0) 个结点的有限集合如果个结点的有限集合如果 n = n = 0 0，，称为空树；如果称为空树；如果 n > 0n > 0，则有且仅有一个特定的称，则有且仅有一个特定的称之为根之为根(Root)(Root)的结点，它只有直接后继，但没有直接前的结点，它只有直接后继，但没有直接前驱；驱；当当n > 1n > 1，，除根以外的其它结点划分为除根以外的其它结点划分为 m (m >0) m (m >0) 个互不相交的有限集个互不相交的有限集 T T1 1, T, T2 2 , ,……, T, Tm m，，其中每个集合本其中每个集合本身又是一棵树，并且称为根的子树身又是一棵树，并且称为根的子树( (SubTreeSubTree) )。

ACGBDE FKLHMIJ例如例如A只有根结点的树只有根结点的树有有13个结点的树个结点的树其中：其中：A是根；其余结点分成三个互不相交的子集，是根；其余结点分成三个互不相交的子集，T1={B,E,F,K,L}；； T2={C,G}；； T3={D,H,I,J,M},T1,T2,T3都是根都是根A的子树，且本身也是一棵树的子树，且本身也是一棵树二、树的表示1、树型表示法2、集合表示法3、括号表示法 （1（2（4，5），37）））4、凹入表示法217543124537124537三、树的基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集合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的祖先6.2二叉树 (Binary Tree)五种形态五种形态一、定义一、定义：： 一棵二叉树是结点的一个有限集合，该集合或者为空，或一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

相交的二叉树组成二、特点：二、特点： 每个结点至多只有两棵子树（二叉树中不存在度大于每个结点至多只有两棵子树（二叉树中不存在度大于2 2的的结点）结点）LLRR性质性质1 在二叉树的第 i 层上至多有 2i －1个结点i  1) [证明用归纳法]证明：当证明：当i=1时，只有根结点，时，只有根结点，2 i-1=2 0=1假设对所有假设对所有j，，i>j 1，，命题成立，即第命题成立，即第j层上至多有层上至多有2 j-1 个个结点由归纳假设第由归纳假设第i-1 层上至多有层上至多有 2i －－2个结点由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在第，故在第i层上的层上的最大结点数最大结点数为第为第i-1层上的最大结点数的层上的最大结点数的2倍，即倍，即2* 2i －－2= 2 i-1二、性质1层2层4层3层height= 4ABDEFJKHLI性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2 k- -1个结点个结点(k   1)证明：由性质证明：由性质1可见，深度为可见，深度为k的二叉树的最大结点数的二叉树的最大结点数为为 ＝＝20 + 21 + … + 2 k-1 = 2 k- -1＝＝性质性质3 3 ：对任何一棵二叉树：对任何一棵二叉树T, T, 如果其叶结点数为如果其叶结点数为 n0,n0, 度为度为2 2的结点数为的结点数为 n2,n2,则则n0n0＝＝n2n2＋＋1.1.证明：若度为证明：若度为1 1的结点有的结点有n1n1个，总结点个数为个，总结点个数为n n，，总边数为总边数为e e，，则根据二叉树的定义，则根据二叉树的定义， n=n0+n1+n2 n=n0+n1+n2 根据分支数与总结点数差１个，根据分支数与总结点数差１个，则则e=2n2+n1=n-1e=2n2+n1=n-1因此，有因此，有 2 2n2+n1=n0+n1+n2-1n2+n1=n0+n1+n2-1 n2=n0-1 n0=n2+1 n2=n0-1 n0=n2+1 定义定义1 满二叉树满二叉树 (Full Binary Tree) 一棵深度为一棵深度为k且有且有2 k-1个结点的二叉树称为个结点的二叉树称为满二叉树。

满二叉树两种特殊形态的二叉树两种特殊形态的二叉树621754389 10 1113 14 1512满二叉树满二叉树215436 7216543非完全二非完全二叉树叉树定义定义2 完全二叉树完全二叉树 (Complete Binary Tree) 若设二叉树的高度为若设二叉树的高度为h，，则共有则共有h层除第 h 层外层外，其它各层，其它各层 (0   h- -1) 的结点数都达到最大个数，的结点数都达到最大个数，第第 h 层从右向左连续缺若干结点，这就是完全二叉层从右向左连续缺若干结点，这就是完全二叉树621754389 10 11 12完全二完全二叉树叉树1231145891213671014151231145891267101234567123456性质性质4 4 具有具有 n (n n (n   0) 0) 个结点的完全二叉树的深个结点的完全二叉树的深度为度为 loglog2 2(n) (n)  ＋＋1 1 证明：证明：设完全二叉树的深度为设完全二叉树的深度为 h h，，则根据性质则根据性质2 2和完全二叉和完全二叉树的定义有树的定义有2 2h h－－1 1 - 1 < n - 1 < n   2 2h h- 1- 1或或 2 2h h－－1 1   n < 2 n < 2h h取对数取对数 h h－－1 < log1 < log2 2n n   h h，又，又h h是是整数，整数，因此有因此有 h = h =  loglog2 2(n) (n)   ＋＋1 1 621754389 10 11 12071234568 9性质5：在完全二叉树中编号（1开始）为i的结点，1）若有左孩子，则左孩编号为2i；2）若有右孩子，则有孩子结点编号为2i+1；3）若有双亲，则双亲结点编号为i/2；1、顺序表示、顺序表示 （1）完全二叉树的存储，采取一维数组就可以存储出来，将每个元素按照从上而下，从左到右的顺序依次存储在数组中，则元素之间关系利用元素的存储下标可以实现。

（2）非完全二叉树的存储，需先补齐0使之成为完全二叉树，然后按照完全二叉树的存储形式三、二叉树的存储结构abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 112、链式存储结构-------二叉链表lchild data rchild ABCDEFG在n个结点的二叉链表中，有n+1个空指针域 AB C D E F G^^^^^^^^typedef struct BiTNode { //结点定义结点定义 TElemType data; struct BiTNode * lchild, * rchild;} BiTNode,*BiTree;BiTree指针数据类型作为二叉树的数据类型指针数据类型作为二叉树的数据类型三叉链表lchild data parent rchildABCDEFG A B C D E F G^^^^^^^^^6.3 二叉树的遍历6.3.1 遍历二叉树一、定义1、遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。

2、访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据 遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事二、二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树 约定先左后右,有三种遍历方法： DLR、LDR、LRD ，分别称为先序遍历、中序遍历、后序遍历 A A F F G G E E D D C C B B 1、先序遍历（DLR） 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；； 先序遍历序列：：A,B,D,E,G,C,FA,B,D,E,G,C,F A A F F G G E E D D C C B B例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按DLRDLR的顺序遍历左子树 （3）先序遍历右子树：即按DLRDLR的顺序遍历右子树2、中序遍历（LDR）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树 中序遍历序列： D,B,G,E,A,C,F A A F F G G E E D D C C B B例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按LDR的顺序遍历左子树 （2）访问根结点A （3）中序遍历右子树：即按LDR的顺序遍历右子树3、后序遍历（LRD）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点 后序遍历序列： D,G,E,B,F,C,A例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按LRD的顺序遍历左子树 （2）后序遍历右子树：即按LRD的顺序遍历右子树 （3）访问根结点A A A F F G G E E D D C C B B4、由二叉树的先序（或后序）序列和中序序列可唯一地确定一棵二叉树。

例, 先序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下： 后序遍历序列：a,b,c,d,-,*,+,e,f,/,- 中序遍历序列：a,+,b,*,c,-,d,-,e,/,f 先序遍历序列：-,+,a,*,b,-,c,d,/,e,f5、算术表达式：根据表达式a+b*(c-d)-e/f，结合表达式运算的先后顺序，可以形成算术表达式的二叉树的表示，由此可转换为前缀表达式或后缀表达式 -- -/ /+ +* *abcdef这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分：1）基本项（也叫终止项）； 2）递归项 若二叉树非空 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树；先序遍历递归定义递归项三、遍历的递归算法 上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例：先序遍历（DLR）的定义：该定义隐含着若二叉树为空，结束 1、先序遍历二叉树的递归算法void void PreOrderTraverse(BiTreePreOrderTraverse(BiTree T){ T){if (T){if (T){printf("%c",Tprintf("%c",T->data);->data);PreOrderTraverse(TPreOrderTraverse(T->->lchildlchild););PreOrderTraverse(TPreOrderTraverse(T->->rchildrchild);); } } } } 中序遍历二叉树的递归算法、后序遍历二叉树的递归算法均只是将printf(“%c”,T->data);放在中间或者最后执行就可。

2、遍历二叉树的非递归算法先序遍历：算法1，将右子树根结点 入栈，(栈所需最大容量为n/2+1)；算法2将根结点入栈 中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树后序遍历： 1）设定一个指针，指向 最近访问过的结点在退栈取出根结点时，需判断：若根结点的右子树为空，或它的右子树非空，但已遍历完毕，即它的右子树根结点恰好是最近一次访问过的结点时，应该遍历该根结点反之，该根结点应重新入栈，先遍历它的右子树 2）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈需用到栈，顺序栈的定义如下：typedef BiTNode* SElemType;typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;先序遍历的非递归算法先序遍历的非递归算法先序遍历的非递归算法先序遍历的非递归算法1 1 1 1void preorder(BiTree T) {SqStack S; BiTree P=T;InitStack(S);Push(S,NULL);while (P) { printf("%c",P->data);if (P->rchild)Push(S,P->rchild);if (P->lchild)P=P->lchild;else Pop(S,P);} }先序遍历的非递归算法先序遍历的非递归算法先序遍历的非递归算法先序遍历的非递归算法2 2 2 2void preorder(BiTree T){int top=0;BiTree stack[20], P=T;do { while (P){printf("%c",P->data);stack[top]=P; top++;P=P->lchild;}if (top){top--;P=stack[top];P=P->rchild;}}while (top || P);}中序遍历的非递归算法序遍历的非递归算法序遍历的非递归算法序遍历的非递归算法1void inorder(BiTree T){SqStack S; BiTree P=T;InitStack(S);do{while(P){ * (S.top) = P;S.top++;P=P->lchild;}if (S.top){S.top--;P=*(S.top);printf("%c",P->data);P=P->rchild;}}while((S.top!=S.base) || P);}中序遍历的非递归算法中序遍历的非递归算法中序遍历的非递归算法中序遍历的非递归算法2 2 2 2（（（（p131p131p131p131算法算法算法算法6.3)6.3)6.3)6.3)void inorder(BiTree T) {SqStack S; BiTree P=T;InitStack(S);while( P || !Empty(S)) { if (P) {Push(S,P);P=P->lchild; } else {Pop(S,P);printf("%c",P->data);P=P->rchild;} } } 后序遍历时，每遇到一个结点，先把它推入栈中，让后序遍历时，每遇到一个结点，先把它推入栈中，让后序遍历时，每遇到一个结点，先把它推入栈中，让后序遍历时，每遇到一个结点，先把它推入栈中，让PopTimPopTimPopTimPopTim=0=0=0=0。

在遍历其左子树前，改结点的在遍历其左子树前，改结点的在遍历其左子树前，改结点的在遍历其左子树前，改结点的PopTimPopTimPopTimPopTim= = = =1 1 1 1，，，，将将将将其左孩子推入栈中在遍历完左子树后，还不能访问该其左孩子推入栈中在遍历完左子树后，还不能访问该其左孩子推入栈中在遍历完左子树后，还不能访问该其左孩子推入栈中在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，此时改结点的结点，必须继续遍历右子树，此时改结点的结点，必须继续遍历右子树，此时改结点的结点，必须继续遍历右子树，此时改结点的PopTimPopTimPopTimPopTim=2=2=2=2，，，，并把其右孩子推入栈中在遍历完右子树后，结点才退并把其右孩子推入栈中在遍历完右子树后，结点才退并把其右孩子推入栈中在遍历完右子树后，结点才退并把其右孩子推入栈中在遍历完右子树后，结点才退栈访问 后序遍历的非递归算法后序遍历的非递归算法1 1void Postorder(BiTree T){ BiTree p=T,q=NULL; SqStack S; InitStack(S); Push(S,p); while (!StackEmpty(S)){ if (p && p!=q) { Push(S,p); p=p->lchild; } else { Pop(S,p); if (!StackEmpty(S)) if (p->rchild && p->rchild!=q) { Push(S,p); p=p->rchild;} else {printf("%c",p->data); q=p;} } }}后序遍历的非递归算法后序遍历的非递归算法2 2void postorder(BiTree T){BiTree P=T,q; int flag;SqStack S;InitStack(S); do { while (P){ *(S.top)=P;S.top++;P=P->lchild;} q=NULL; flag=1; while ((S.top!=S.base) && flag) { P=*(S.top-1); if (P->rchild == q) { printf("%c",P->data); S.top--; q=p;} else { P=P->rchild;flag=0;} } }while ((S.top!=S.base));}五、二叉树遍历应用1、：为二叉树建立二叉链表(递归算法递归算法) 输入：二叉树的先序序列结果：二叉树的二叉链表 基本思想：基本思想：输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字符//）按先序编历的顺序，建立二叉链表的所有结点并完成相应结点的链接∧∧ D D A A B∧B∧ C C ∧∧∧∧ E∧E∧∧∧ F∧F∧T T 先序序列：A B D F C E（在空子树处添加*的二叉树的）先序序列：A B D * F * * C E * * * * A A F F E E D D C C B B******* A A F F E E D D C C B BStatus CreateBiTree(BiTree &T) {//输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字符）按先序编历的顺序，建立二叉链表，并将该二叉链表根结点指针赋给T scanf (&ch); if (ch= = ‘* ’) T=NULL; // 若ch= = ‘*’ 则T=NULL返回 else { // 若ch! = ‘*’ if (! (T=(BiTNode * )malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->date = ch; // 建立（根）结点 CreateBiTree(T->lchild); //构造左子树链表，并将左子树根结点指针赋 给（根）结点 的左孩子域 CreateBiTree(T->rchild); //构造右子树链表，并将右子树根结点指针赋给（根）结点 的右孩子域 } return OK;}//CreateBiTree2、二叉树的显示输出void PrintBiTree(BiTree T,int n){int i; char ch=' ';if (T) {PrintBiTree(T->rchild,n+1);for (i=1;i<=n;++i) {printf("%5c",ch);}printf("%c\n", T->data);PrintBiTree(T->lchild,n+1);}}int Count(BiTtree T) { if (T==NULL) return 0; else return 1 + Count (T->lchild)+Count(T->rchild);}3.3.计算二叉树结点个数计算二叉树结点个数( (递归算法递归算法) )4.4.求二叉树中叶子结点的个数求二叉树中叶子结点的个数int Countleaf(BiTree T ) //求二叉树中叶子结点的数目{ if ( T==NULL ) return 0; //空树没有叶子 if(T->lchild==NULL&&T->rchild==NULL) return 1;//叶子结点 return Countleaf(T->lchild)+Countleaf(T->rchild);//左子树的叶子数加上右子树的叶子数}int Height ( Bitree T ) //Height of a tree{ if ( T == NULL ) return -1; else {int m = Height ( T->lchild ); int n = Height ( T->rchild ); return (m > n) ? m+1 : n+1 ; } }5.求二叉树高度(递归算法)6.复制二叉树void CopyTree(BiTree T,BiTree &T1) { if (T) { T1=(BiTree)malloc(sizeof(BiTNode)); if (!T1) { printf("Overflow\n"); exit(1);} T1->data=T->data; T1->lchild=T1->rchild=NULL; CopyTree(T->lchild,T1->lchild); CopyTree(T->rchild,T1->rchild);}}7.左右子树互换void Exchange(BiTree &T){BiTree S;if (T) { S=T->lchild; T->lchild=T->rchild; T->rchild=S; Exchange(T->lchild); Exchange(T->rchild); }}六、按层次遍历二叉树六、按层次遍历二叉树 从根开始逐层访问，从根开始逐层访问，用用FIFOFIFO队列实现。

队列实现typedef BiTNode* ElemType;typedef struct{QElemType *base;int front,rear;}SqQueue;遍历顺序遍历顺序遍历顺序遍历顺序void void LevelOrderTraverse(BiTreeLevelOrderTraverse(BiTree T) T) { { BiTreeBiTree p; p; SqQueueSqQueue Q; Q; InitQueue(QInitQueue(Q);); if (T){ Q.base[Q.rear]=T; if (T){ Q.base[Q.rear]=T; Q.rear=(Q.rear+1)%MAXQSIZE; Q.rear=(Q.rear+1)%MAXQSIZE; while (Q.front !=Q.rear) while (Q.front !=Q.rear) { p=Q.base[Q.front]; { p=Q.base[Q.front]; printf("%c",pprintf("%c",p->data);->data); Q.front=(Q.front+1)%MAXQSIZE; Q.front=(Q.front+1)%MAXQSIZE; if (p-> if (p->lchildlchild) ) { Q.base[Q.rear]=p-> { Q.base[Q.rear]=p->lchildlchild; ; Q.rear=(Q.rear+1)%MAXQSIZE;} Q.rear=(Q.rear+1)%MAXQSIZE;} if (p-> if (p->rchildrchild) ) { Q.base[Q.rear]=p-> { Q.base[Q.rear]=p->rchildrchild; ; Q.rear=(Q.rear+1)%MAXQSIZE;} Q.rear=(Q.rear+1)%MAXQSIZE;} } }} }} }6.3.2 线索二叉树一、基本概念： 1、线索 (Thread): 指向结点前驱和后继的指针 若结点有左孩子，则lchild指示其左孩子，否则lchild中存储该结点的前驱结点的指针；若结点有右孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针 2、实质：对一个非线性结构进行线性化操作，使每个结点（除第一和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。

3、说明：索树中的前驱和后继是指按某种次序遍历所得到的序列中的前驱和后继概念: (p132) 线索链表、线索、线索化、线索二叉树中序遍历序列：D,B,H,E,A,F,C,G在中序序列中，D的后继是B，H的前趋是B，后继是E… A A G G H H E E D D C C B B F F加上结点前趋后继信息（结索）的二叉树称为线索二叉树线索二叉树线索二叉树孩子指针前趋指针后继指针二、线索二叉树二、线索二叉树二、线索二叉树二、线索二叉树 (Threaded Binary Tree)(Threaded Binary Tree)(Threaded Binary Tree)(Threaded Binary Tree)Ltag=0, lchild为左子女指针Ltag=1, lchild为前驱线索Rtag=0, rchild为右子女指针Rtag=1, rchild为后继指针结点结构结点结构lchildlchildrchildrchilddatadataLtagRtagABCGEIDHFroot悬空悬空？？悬空？悬空？解：该二叉树中序遍历结果为解：该二叉树中序遍历结果为: : H, D, I, B, E, A, F, C, G所以添加线索应当按如下路径进行：所以添加线索应当按如下路径进行：为为避免悬空避免悬空态，应增设态，应增设一个头结点一个头结点三、线索二叉树的建立过程：三、线索二叉树的建立过程：例例1 1：：画出以下二叉树对应画出以下二叉树对应的中序线索二叉树。

的中序线索二叉树00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为: : H, D, I, B, E, A, F, C, G0--root0对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：四、线索二叉树的生成算法四、线索二叉树的生成算法目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后 继注解：为方便添加结点的前驱或后继，需要设置两个指针：注解：为方便添加结点的前驱或后继，需要设置两个指针： p指针指针→当前结点之指针；当前结点之指针； pre指针指针→前驱结点之指针前驱结点之指针技巧：当结点技巧：当结点p的左的左/右域为空时，只改写它的左域（装入前驱右域为空时，只改写它的左域（装入前驱pre），），而其右域（后继）留给下一结点来填写而其右域（后继）留给下一结点来填写 或者说，当前结点的指针或者说，当前结点的指针p应当送到前驱结点的空右域中应当送到前驱结点的空右域中若若p->lchild＝＝NULL, ,则则{p->{p->LtagLtag=1;p->=1;p->lchildlchild＝＝pre;};} //p //p的前驱结点指针的前驱结点指针pre存入左空域存入左空域若若pre->rchild＝＝NULL, 则则{pre->{pre->RtagRtag＝＝1;pre->rchild=p;} //p存入其前驱结点存入其前驱结点pre的右的右空域空域Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) {// 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。

if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); Thrt->LTag = Link; Thrt->RTag =Thread；// 建头结点; Thrt->rchild = Thrt; // 右指针回指 if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指 else { Thrt->lchild = T; pre = Thrt; InThreading(T); // 算法6.7：中序遍历进行中序线索化 pre->rchild = Thrt; pre->RTag = Thread; // 最后一个结点线索化 Thrt->rchild = pre; } return OK;} // InOrderThreading中序线索二叉树的创建算法：中序线索二叉树的创建算法：void InThreading(BiThrTree p) { // 算法6.7 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中序线索二叉树的创建算法：中序线索二叉树的创建算法：五、线索二叉树的遍历五、线索二叉树的遍历 理论上，只要找到序列中的第一个结点，然后依次访问结理论上，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空时结束。

点的后继直到后继为空时结束 但是，但是，但是，但是，索化二叉树中，并不是每个结点都能直接找到索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为其后继的，当标志为0 0时，时，R_child=R_child=右孩子地址指针，并非后右孩子地址指针，并非后继！需要通过一定运算才能找到它的后继继！需要通过一定运算才能找到它的后继以以中序线索二叉树中序线索二叉树为例：为例：对叶子结点（对叶子结点（RTag=1），），直接后继指针就在其直接后继指针就在其rchild域内；域内；对其他结点（对其他结点（RTag=0），），直接后继是其直接后继是其右子树最左下的结点右子树最左下的结点；；（因为中序遍历规则是（因为中序遍历规则是LDR，，先左再根再右先左再根再右先左再根再右先左再根再右））①①②②④④⑧⑧⑤⑤⑨⑨③③⑥⑥⑥⑥ ⑦⑦⑩⑩……Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType)) {BiThrTree p; p = T->lchild; // p指向根结点 while (p != T) { // 空树或遍历结束时， p==T while (p->LTag==Link) p = p->lchild; if (!Visit(p->data)) return ERROR; // 访问其左子树为空的结点 while (p->RTag==Thread && p->rchild!=T) { p = p->rchild; Visit(p->data); // 访问后继结点 } p = p->rchild; // p进至其右子树根 } return OK;}线索二叉树的中序遍历算法：线索二叉树的中序遍历算法：程序注解 (非递归，且不用栈）：P=T->lchild; //从头结点进入到根结点；while( p!=T) {while(p->LTag==link)p=p->lchild; //先找到中序遍历起点 if(!visit(p->data)) return ERROR; //若起点值为空则出错告警 while(p->RTag==Thread ……){ p=p->rchild; Visit(p->data);} //若有后继标志，则直接提取p->rchild中线索并访问后继结点；p=p->rchild; //当前结点右域不空或已经找好了后继，则一律从结点的右子树开始重复{ }的全部过程。

}Return OK;LTag=0RTag=1一、树的存储结构一、树的存储结构1.1.双亲表示：双亲表示：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系 以一组连续空间存储树的结点，同时在结点中附设一个以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置指针，存放双亲结点在链表中的位置6.46.4树与森林树与森林ABCDEFGdataparentA B C D E F G- -1 0 0 0 1 1 30 1 2 3 4 5 6思路：思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（n个结点要设立n个链表）；再将n个表头用数组存放起来，这样就形成一个混合结构例如例如：：abecdfhgdefghgfedcbah123456782 2、孩子表示法、孩子表示法bc思路思路：：用二叉链表来表示树，但链表中的两个指针域含义不同左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点nextsiblingdatafirstchild3 3、用孩子兄弟表示法来存储、用孩子兄弟表示法来存储指向左孩子指向左孩子指向右兄弟指向右兄弟abecdfhgbacedfgh例如例如：：二、树与二叉树的转换二、树与二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。

树与二叉树转换方法树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子I IA AC CB BD DH HG GF FE EF FI IA AB BD DH HG GC CE E方法：方法：加加线线——抹线抹线——旋转旋转 abeidfhgcabeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左根根根根结点肯定结点肯定结点肯定结点肯定没有右孩子！没有右孩子！没有右孩子！没有右孩子！二叉树怎样还原为树？二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！要点：把所有右孩子变为兄弟！ abeidfhgc三、森林三、森林森林森林：树的集合：树的集合 将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历； J J O O P P N N M M L L K KI IA AC CB BD DH HG GF FE E包含两棵树的森林T1 T2 T3T1 T2 T3AFHB C DGIJEKAFBCDEGHIKJABCEDHIKJFG3 棵树的森林各棵树的二叉树表示森林的二叉树表示q森林与二叉树的转换森林与二叉树的转换ABCDEFGHJIABCDEFGHJIA ABCDEFGHJI森林转二叉树举例：森林转二叉树举例：兄弟相连兄弟相连 长兄为父长兄为父孩子靠左孩子靠左 头根为根头根为根 A A二叉树如何还原为森林？二叉树如何还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即即B={root, LB, RB} F={TB={root, LB, RB} F={T1 1, T, T2 2, , …,T,Tm m} }当树非空时当树非空时u访问根结点访问根结点u依次先根遍历根的各棵子树依次先根遍历根的各棵子树树先根遍历树先根遍历 ABEFCDGABEFCDG对应二叉树前序遍历对应二叉树前序遍历 ABEFCDGABEFCDG树的先根遍历结果与其对应二叉树树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同表示的前序遍历结果相同树的先根遍历可以借助对应二叉树的前序遍历算法实现树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCEDGF1、树的、树的先根次序先根次序遍遍历历四、树和森林的遍历：2、树的后根次序遍历、树的后根次序遍历:当树非空时当树非空时u依次后根遍历根的各棵子树依次后根遍历根的各棵子树u访问根结点访问根结点树后根遍历树后根遍历 EFBCGDAEFBCGDA对应二叉树中序遍历对应二叉树中序遍历 EFBCGDAEFBCGDA树的后根遍历结果与其对应二叉树树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同表示的中序遍历结果相同树的后根遍历可以借助对应二叉树的中序遍历算法树的后根遍历可以借助对应二叉树的中序遍历算法实现实现ABCEDGF6.66.6哈夫曼树哈夫曼树 (Huffman Tree)(Huffman Tree)一、基本概念一、基本概念1、路径长度、路径长度 (Path Length) 两个结点之间的路径长度 是连接两结点的路径上的分支数。

树的路径长度是各结点(包括叶结点和非叶结点)到根结点的路径长度之和8123456712345678树的路径长度：树的路径长度：PL = 2*1+2*4+3*1 =13树的路径长度树的路径长度PL = 2*1+2*2+3*3+4*1 = 19234567812、带权路径长度、带权路径长度 (Weighted Path Length, WPL) 结点带权路径长度：从一个结点到根结点的路径长度与该结点权值的乘积 树的带权 (外部) 路径长度：是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35 222444555777带权路径长度达带权路径长度达到最小到最小3、哈夫曼树：、哈夫曼树：给定给定n n个权值，以其为叶子结点，构造个权值，以其为叶子结点，构造的所有的二叉树中，树的带权路径长度达到最小的的所有的二叉树中，树的带权路径长度达到最小的二叉树即为哈夫曼树，在哈夫曼树中，权值大的结二叉树即为哈夫曼树，在哈夫曼树中，权值大的结点离根最近点离根最近。

1、构造哈夫曼树： (1) 由给定的 n 个权值 {w0, w1, w2, …, wn-1}，构造具有 n 棵扩充二叉树的森林 F = { T0, T1, T2, …, Tn-1 }，其中每棵扩充二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空 二、霍夫曼二、霍夫曼算法算法 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： ① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和 ② 在 F 中删去这两棵二叉树 ③ 把新的二叉树加入 F赫夫曼树的构造过程举例：赫夫曼树的构造过程举例：例 w={5, 29, 7, 8, 14, 23, 3, 11}51429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100注意：1、一棵有n个叶子结点的Huffman树有2n-1个结点2、同样叶子权值构造出的哈夫曼树形态不唯一。

3、采用顺序存储结构——一维结构数组三、哈夫曼编码哈夫曼编码：数据通信用的二进制编码1、思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列例 要传输的字符集 D={C,A,S,T, ; } 字符出现频率 w={2,4,2,3,3}CS3364224814T;A00110110T : 00; : 01A : 10C : 110S : 1112、译码：从Huffman树根开始，从待译码电文中逐位取码若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束例 电文是{CAS;CAT;SAT;AT} 其编码 “11010111011101000011111000011000” 电文为“1101000” 译文只能是“CAT”CS3364224814T;A00110110T : 00; : 01A : 10C : 110S : 111。