第6章(树和二叉树).ppt

第6章 树和二叉树,6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用,树型结构是一类重要的非线性结构。树结构在客观世界里是大量存在的，树在计算机领域中也有着广泛的应用。,6.1 树的定义和基本术语,1、定义 树是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：,（1）有且仅有一个特定的称为根的结点；,（2）当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,T3,Tm，其中每个子集又是一棵树，并称其为根的子树。,A,只有根结点的树,有子树的树,根,子树,结点表示树中的元素，包括数据项及若干指向其子树的分支,2、基本术语,结点的度(degree)结点拥有的子树数,叶子(leaf)度为0的结点,孩子(child)结点的子树的根称为该结点的孩子,双亲(parents)孩子结点的上层结点叫该结点的双亲,兄弟(sibling)同一双亲的孩子,树的度一棵树中各结点的度的最大值,结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层,深度(depth)树中结点的最大层次数,森林(forest)m(m0)棵互不相交的树的集合,结点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的祖先,2、基本术语,6.2 二叉树,二叉树在树结构的应用中起着非常重要的作用，因为针对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。,二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树也都是二叉树。,这也是一个递归定义。二叉树可以是空集合，根也可以有空的左子树或空的右子树。,(a)空二叉树,A,A,B,A,B,A,C,B,(b)根和空的左右子树,(c)根和左子树,(d)根和右子树,(e)根和左右子树,二叉树的5种基本形态,二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。,6.2.1 二叉树的定义,6.2.2 二叉树的性质,二叉树具有下列重要性质：,性质1:在二叉树的第 i 层上至多有2i-1个结点(i1)。,采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=21-1=20=1，命题成立。,现在假定对所有的j，1ji，命题成立，即第j层上至多有2j-1个结点，那么需要证明当ji时命题也成立。由归纳假设可知，第i-1层上至多有2i-2个结点。,由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i-1层上最大结点数的2倍，,即22i-22i-1。命题得到证明。,性质2：深度为k的二叉树至多有2k-1个结点（k1)。,深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，,性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的 结点数为n2，则n0n21。,设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点的度均小于或等于2，所以有：Nn0n1n2(6-1),再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：NB1,由于这些分支都是由度为1和2的结点射出的，所以有：Bn1+2n2 因此，NB1n12n21（6-2),由式（6-1）和（6-2）得到：,n0+n1+n2=n1+2n2+1,可得 n0n21,性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的 结点数为n2，则n0n21。,满二叉树,一棵深度为k且有2k-1个结点的二叉树称为满二叉树。下面就是一棵满二叉树，并对结点进行了顺序编号。,下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。,（a）完全二叉树,（b）非完全二叉树,（c）非完全二叉树,如果深度为k、有n个结点的二叉树中的每个结点能够与深度为k的顺序编号的满二叉树从1到n编号的结点相对应，则称这样的二叉树为完全二叉树。满二叉树是完全二叉树的特例。,完全二叉树的特点,（1）所有的叶结点都出现在第 k 层或第 k-1 层。,（2）对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l1。,性质4：具有n个结点的完全二叉树的深度为log2n1。符号 x表示不大于x的最大整数。,假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得：2k-1-1n2k-1 或 2k-1n2k,取对数得到:k-1 log2n k，又因为k是整数，所以有：k log2n 1,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n+1层，每层从左到右)，则对任一结点i（1in)，有：,（1）如果i=1，则结点i无双亲，是二叉树的根；如果i1，则其双亲是结点i/2。,（2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。,（3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。,图6.6 完全二叉树中结点i和i+1,只要先证明（2）和（3），便可以从（2）和（3）推出（1）。,对于i1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，此时，结点i无孩子。结点i的右孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。,图6.6 完全二叉树中结点i和i+1,i+1,2(i+1),2i+3,i,2i,2i+1,(b)i和i+1结点不在同一层,对于i1，可分为两种情况：,（1）设第j（1jlog2n)层的第一个结点的编号为i（由二叉树的定义和性质2可知i2j-1），则其左孩子必定为j1层的第一个结点，其编号为2j22j-12i。如果2in，则无左孩子；,其右孩子必定为第j1层的第二个结点，编号为2i1。若2i+1n，则无右孩子。,图6.6 完全二叉树中结点i和i+1,i+1,2(i+1),2i+3,i,2i,2i+1,(b)i和i+1结点不在同一层,（2）假设第j(1jlog2n)层上的某个结点编号为i（2 j-1i2j-1)，且2i1n，则其左孩子为2i，右孩子为2i1.又编号为i1的结点是编号为i的结点的右兄弟或堂兄弟。若它有左孩子，则其编号必定为2i22（i1）；若它有右孩子，则其编号必定为2i32（i1）1。,图6.6 完全二叉树中结点i和i+1,当i1时，就是根，因此无双亲。,当i1时，如果i为左孩子，即2（i/2)=i，则i/2是i的双亲；如果i为右孩子，i2p+1，i的双亲应为p，p（i1）/2=i/2。证毕。,1、顺序存储结构,6.2.3 二叉树的存储结构,#define MAX_TREE_SIZE 100 typedef TElemType SqBiTree MAX_TREE_SIZE;SqBitree bt;,按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的的结点元素存储在如上定义的一维数组中下标为i-1的分量中。,1 2 3 4 5 6 7 8 9 10 11 12,a,b,c,d,e,f,g,h,i,j,k,l,1、顺序存储结构,完全二叉树,从树根起，自上层至下层、每层自左至右的给所有结点编号。,一般二叉树,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为h且只有h个结点的右单支树，却需要2h-1个结点存储空间；而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！,typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,在n个结点的二叉链表中，有n+1个空指针域,二叉树的每一个结点最多有左、右两棵子树，故链表的结点结构除数据域外可设两个链域：左孩子（lchild）、右孩子（rchild）分别指向左、右孩子。称结点由两个链域组成的链表为二叉链表。,2、链式存储结构,typedef struct nodedatatype data;struct node*lchild,*rchild,*parent;JD;,三叉链表：有时为了便于找到双亲结点，另设一个指向双亲的链域，结点由三个链域组成的链表称为三叉链表。,在n个结点的三叉链表中，有n+2个空指针域,用链表表示的二叉树中也会存在许多空链域。例如在含有n个结点的二叉链表中，共有2n个链域，实际用n-1链域（仅有n-1个分支），还有n+1个空链域。可以利用这些空链域存储其它有用信息，从而得到另一种链式存储结构线索链表。,6.3 遍历二叉树和线索二叉树,6.3.1 遍历二叉树 1、定义及递归算法,遍历二叉树：是指按一定的次序系统地访问二叉树中所有结点，而且每个结点仅被访问一次。,访问：所谓“访问”可以是对结点作各种处理，如输出结点的数据 域的值。,二叉树是由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。,假如以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可能有：DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。,若限定先左后右，则只有前三种情况，分别称之为先（根）序遍历，中（根）序遍历和后（根）序遍历。,1、定义及递归算法,先序遍历算法,若二叉树为空树，则空操作；否则，,（1）访问根结点；,（2）先序遍历左子树；,（3）先序遍历右子树。,void PreOrder（BiTree bt）if(bt=NULL)return;/*递归调用的结束条件*/,Visit（bt-data）;/*访问结点的数据域*/,PreOrder（bt-lchild）;/*先序递归遍历bt的左子树*/,PreOrder（bt-rchild）;/*先序递归遍历bt的右子树*/,D L R,先序遍历序列：A B D C,先序遍历:,先序遍历,若二叉树为空树，则空操作；否则，,中序遍历算法,（1）中序遍历左子树；,（2）访问根结点；,（3）中序遍历右子树。,void InOrder（BiTree bt）if(bt=NULL)return;,InOrder（bt-lchild）;,Visit（bt-data）;,InOrder（bt-rchild）;,L D R,中序遍历序列：B D A C,中序遍历,中序遍历,后序遍历算法,若二叉树为空树，则空操作；否则，,（1）后序遍历左子树；,（2）后序遍历右子树；,（3）访问根结点。,void PostOrder（BiTree bt）if(bt=NULL)return;,PostOrder（bt-lchild）;,PostOrder（bt-rchild）;,Visit（bt-data）;,L R D,后序遍历序列：D B C A,后序遍历:,后序遍历,所谓二叉树的层序遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中则按从左到右的顺序对结点逐个访问。,层序遍历,练习：,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,层次序列：,A B E C F D G H K,例如下图所示的二叉树表示下述表达式,按中序遍历，其中序序列为：a+b*c d e/f,a+b*(c-d)-e/f,若先序遍历此二叉树，按访问结点的先后次序将结点排列 起来，其先序序列为：-+a*b c d/e f,按后序遍历，其后序序列为：a b c d-*+e f/-,人们喜欢中缀形式的算术表达式；但对于计算机，使用后缀易于求值。,（1）查询二叉树中某个结点,2、二叉树其它操作的算法,（1）查询二叉树中某个结点,在二叉树不空的前提下，和根结点的元素进行比较。若相等，则找到并返回 OK;,否则在左子树中进行查找，若找到，则返回OK;,否则继续在右子树中进行查找，若找到，则返回 OK；再否则，返回 FALSE。,（2）计算二叉树中叶子结点的个数,（3）求二叉树的深度(后序遍历),（4）按先序遍历序列建立二叉树,Status Preorder(BiTree T,TElemType x,BiTree&p),if(T)if(T-data=x)p=T;return OK;else return FALSE;,else if(Preorder(T-lchild,x,p)return OK;else return(Preorder(T-rchild,x,p);,（1）查询二叉树中某个结点,算法基本思想：先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。,（2）计算二叉树中叶子结点的个数,由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。,void CountLeaf(BiTree T,int,第一种方法,int CountLeaf(BiTree T)if(!T)return 0;if(!T-lchild,第二种方法,int Count(BiTree T)/返回指针T所指二叉树中所有结点个数 if(!T)return 0;if(!T-lchild,类似地求结点的个数,算法基本思想：首先分析二叉树的深度和它的左、右子树深度之间的关系,（3）求二叉树的深度(后序遍历),从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1。,int Depth(BiTree T)/*返回二叉树的深度*/if(!T)depthval=0;else,depthLeft=Depth(T-lchild);,return depthval;,depthRight=Depth(T-rchild);,depthval=1+(depthLeft depthRight?depthLeft:depthRight);,（3）求二叉树的深度(后序遍历),（4）按先序遍历序列建立二叉树,建立二叉树的方法很多，这里介绍一个基于先序遍历的构造方法。算法中输入的是二叉树的先序序列，但必须在其中加入空指针。若用“”表示空指针，要建立下图中所示的二叉树，其输入序列为：,A B C D E G F,Status CreateBiTree(BiTree&T)/*按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树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;,3、遍历二叉树的非递归算法,（1）先序遍历的非递归算法,当找到没有左孩子的结点时，从栈顶退出某结点的右孩子，此时该结点的左子树已遍历完。,再按上述过程遍历该结点的右子树。,使用栈实现先序遍历二叉树的基本思想是：,从二叉树的根结点开始，沿左支一直走到没有左孩子的结点为止，在走的过程中访问所遇到的结点，并把非空右孩子进栈。,void preorder(JD*r)/*先序遍历二叉树的非递归算法*/int i=0;JD*p,*sM;p=r;,do while(p!=NULL),printf(%dt,p-data);,si+=p-rchild;,if(i 0)p=s-i;,while(i0|p!=NULL);,if(p-rchild!=NULL),p=p-lchild;,（1）先序遍历二叉树的非递归算法,（2）中序遍历二叉树的非递归算法,使用栈实现中序遍历的二叉树的基本思想与先序遍历类同，只是在沿左支向前走的过程中将所遇到的结点进栈，待到遍历完左子树时，从栈顶退出结点并访问，然后再遍历右子树。,非递归算法,（3）后序遍历二叉树的非递归算法,使用栈实现后序遍历的二叉树要比先序和中序遍历复杂一些。每个结点要等到遍历左、右子树之后才得以访问，所以在去遍历左、右子树之前，结点都需要进栈。,因此设两个栈，分别称为结点栈（S1M）和标志栈S2M）。标志栈中存放进S1栈结点的标记，标记“0”表明结点在遍历左子树时进栈，标记“1”表明结点在遍历右子树时进栈。,当它出栈时，需要判断是从遍历左子树后的返回（即遍历完左子树，需要继续遍历右子树），还是从遍历右子树后的返回（即遍历完右子树，需要访问这个结点）。,仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，,如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,4、由结点的先序序列和中序序列构造对应的二叉树,根据先序遍历的定义，先序序列中的第一个元素一定是二叉树的根结点。由中序遍历定义可知，中序序列中根结点恰为左、右子树的中序序列的分界点。于是根结点元素把中序序列划分两个子序列，左子树的中序序列和右子树的中序序列。,然后根据左子树的中序序列结点个数在先序序列中找到对应的左子树的先序序列和右子树的先序序列。,由此可建立一个根结点，再确定其左、右子树各自的中序序列和先序序列。,然后用同样的方法分别找出其左、右子树的根结点及子树根结点的左、右子树各自的中序序列和先序序列，依次类推，直到所得左、右子树中包含一个结点为止。,4、由结点的先序序列和中序序列构造对应的二叉树,上述过程是一个递归过程，其递归算法的思想是：先根据先序序列的第一个元素建立根结点；,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；,再在先序序列中确定左、右子树的先序序列；,最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。,同样的道理，由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。,因为，依据后序遍历和中序遍历的定义，后序序列的最后一个结点，就如同先序序列的第一个结点一样，可将中序序列分成两个子序列，分别为这个结点的左子树的中序序列和右子树的中序序列，再拿出后序序列的倒数第二个结点，并继续分割中序序列，如此递归下去，当倒着取取尽后序序列中的结点时，便可以得到一棵二叉树。,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,以二叉链表作为存储结构时，只能找到结点的左右孩子的信息,而不能直接得到结点在任一序列中的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存这些信息,可增加标志域;,6.3.2 线索二叉树,Ltag=,Rtag=,其中:,0 lchild 域指示结点的左孩子 1 lchild 域指示结点的前驱,以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱或后继的指针叫做线索，加上线索的二叉树称之为线索二叉树。,0 rchild 域指示结点的右孩子 1 rchild 域指示结点的后驱,0,0,0,0,1,1,1,1,1,1,1、先序线索二叉树,B,T,中序序列：BCAED,0,0,0,0,1,1,1,1,1,1,2、中序线索二叉树,在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点的后继直至其后继为空时为止。,0,0,0,0,1,1,1,1,1,1,3、后序线索二叉树,对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况：,4、线索二叉树的基本操作实现,（1）如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；,（2）如果该结点的左标志为0，表明该结点有左孩子。根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。,如何在中序线索二叉树中找结点的后继？二叉树中所有叶子结点的右链都是线索，则其右链域直接指示了该叶子结点的后继。二叉树中所有非终端结点的右链若为指针，则无法得到后继的信息。,根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第1个结点，即右子树最左下的结点。,4、线索二叉树的基本操作实现,在中序线索二叉树上查找值为x的结点？,利用在中序线索二叉树上寻找后继结点和前驱结点的算法，就可以遍历到二叉树的所有结点。比如，先找到按某序遍历的第一个结点，然后再依次查询其后继；或先找到按某序遍历的最后一个结点，然后再依次查询其前驱。这样，既不用栈也不用递归就可以访问到二叉树的所有结点。,在中序线索二叉树上查找值为x的结点，实质上就是在线索二叉树上进行遍历，将访问结点的操作具体写为那个结点的值与x比较的语句。,4、线索二叉树的基本操作实现,在后序线索二叉树上查找结点后继？,（1）若结点x是二叉树的根，则其后继为空；,例如：结点B的后继为C结点，C结点的后继为结点D，结点D的后继为结点E。E结点的后继为结点F，F结点的后继为G。(P133 图6.12),（2）若结点x是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继为双亲结点；,（3）若结点x是其双亲结点的左孩子，且其双亲有右子树，则其后继为双亲的右子树按后序遍历列出的第1个结点。,4、线索二叉树的基本操作实现,5、二叉树的线性化,由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。,为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法。,T,中序序列：BCAED带头结点的中序线索二叉树,头结点：LTag=0,lchild指向根结点RTag=1,rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点,6.4 树和森林,6.4.1 树的存储结构,1、双亲表示法,2、孩子表示法,3、孩子兄弟表示法,1、双亲表示法,假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。用这种存储方法，容易找到双亲结点及所有的祖先，但找孩子却比较麻烦，需要顺序扫描数组。,typedef struct PTNode/结点结构 ElemType data;int parent;/双亲位置域 PTNode;,#define MAX_TREE_SIZE 100,typedef struct/树结构 PTNode nodesMAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;,2、孩子表示法,把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子结点的孩子链表为空表）。而n个头指针又组成一个线性表，为了便于查找，其采用顺序存储结构。,与双亲表示法相反，孩子表示法便于那些涉及孩子的操作的实现，却不适合涉及双亲的操作。,带双亲的孩子链表,可以把双亲表示法和孩子表示法结合起来，即将双亲表示和孩子链表结合在一起。下图就是这种存储结构的一个例子。,typedef struct node datatype data;struct node*fch,*nsib;JD;,实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。,3、孩子兄弟表示法（二叉树表示法）,6.4.2 森林与二叉树的转换,树转换成的二叉树其根的右子树一定为空,1、树转换成二叉树,加线：在兄弟之间加一连线,抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系,旋转：以树的根结点为轴心，将整树顺时针转45,2、将二叉树转换成树,加线：若p结点是其双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来,抹线：抹掉原二叉树中双亲与右孩子之间的连线,调整：将结点按层次排列，形成树结构,3、森林转换成二叉树,（1）将各棵树分别转换成二叉树.,（2）将每棵树的根结点用线相连.,（3）以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,4、二叉树转换成森林,抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树.,还原：将孤立的二叉树还原成树,6.4.3 树和森林的遍历,1、树的遍历,一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后访问根结点。,例：,两种次序遍历树的方法：一种是先根（次序）遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树；,先根序列：,后根序列：,A B C D E,B D C E A,2、森林的遍历,先序遍历：ABCDEFGHIJ,中序遍历：BCDAFEHJIG,访问森林中第一棵树的根结点；,先序遍历第一棵树中根结点的子树森林；,先序遍历除去第一棵树之后剩余的树构成的森林。,中序遍历森林中第一棵树的根结点的子树森林；,访问第一棵树的根结点；,中序遍历除去第一棵树之后剩余的树构成的森林。,6.6 赫夫曼树及其应用,6.6.1 最优二叉树（赫夫曼树）,2、树的路径长度：从树根到每一个结点的路径长度之和。,3、结点的带权路径长度：从结点到树根之间的路径长度与结点上权的乘积。,1、从树中一个结点到另一个结点之间的分支构成这两个结点间的路径，路径上的分支数目称为路径长度。,4、树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常,5、假设有n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树或赫夫曼树(Huffman)带权路径长度最短的树。,6.6.1 最优二叉树（赫夫曼树）,例如 构造有4个叶子结点，权值分别为7，5，2，4的二叉树,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,应用：将百分制转换成五分制的程序,则80%的数据需要进行三次或三次以上的比较才能得出结果。,假设以5，15，40，30和10为权构造一棵有五个叶子结点的赫夫曼数，则得到(b)的判定过程。,它可使大部分的数据经过较少的比较次数得出结果。但由于每个判定框有两次比较，将这两次分开，得到（c）所示的判定树。,现假设现有10000个输入数据，若按图（a）所示的判定过程进行操作，则总共需要进行31500次比较；而若按图（c）的判定过程进行操作，则总共仅需要进行22000次比较。,将百分制转换成五分制的程序,6、如何构造赫夫曼树？,（1）根据给定的n个权值 w1,w2,wn 构造n棵二叉树的集合F=T1，T2，Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。,（4）重复（2）和（3），直到F只含一棵树为止，这棵树即赫夫曼树。,（3）在森林中删除这两棵树，同时将新得到的二叉树加入森林中。,（2）在森林中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，并且置新二叉树根结点的权值为其左右子树根结点的权值之和。,构造Huffman树步骤,例如，下图展示了赫夫曼树的构造过程。其中，根结点上标注的数字是所赋的权。,6、如何构造赫夫曼树？,1、例题例如，假设要传送的电文为“ABACCDA”，电文中只含有A、B、C、D四种字符，只需要两个字符的串便可分辨。假设A、B、C、D的编码分别为00、01、10和11，则上述七个字符的电文代码为“00010010101100”，总长度为14，对方接收时，可按二位一分进行译码。,6.6.2 赫夫曼编码,在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短，显然，这种编码方案产生的电文代码不够短。,如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。例如设计A、B、C、D的编码分别为0、00、1和01，则上述七个字符的电文“ABACCDA”可转换成总长为9的字符串“000011010”。,但是，这样的电文无法翻译。例如传送过去的字符串中前四个字符的子串“0000”就可有多种译法“AAAA”或“ABA”，也可以是“BB”。,因此，若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。,6.6.2 赫夫曼编码,编码,假设有一棵如下图所示的二叉树，其4个叶子结点分别表示A、B、C、D这4个字符，且约定左分支表示字符“0”，右分支表示字符“1”，从根结点到叶子结点的路径上分支字符组成的字符串作为该结点字符的编码。,A（0）B（10）C（110）D（111）,2、利用二叉树来设计二进制的前缀编码,3、如何得到使电文总长最短的二进制前缀编码,假设每种字符在电文中出现的次数为wi，其编码长度为li，电文中只有n种字符，则电文总长为,对应到二叉树上，若置wi为叶子结点的权，li恰为根到叶子的路径长度。则 恰为二叉树上带权路径长度。,由此可见，设计电文总长度最短的二进制前缀编码，即以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。,如何选定结点结构？,由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既需知双亲结点的信息，又需要知孩子结点的信息。,编码：把一棵二叉树中每个结点左分支标上“0”，右分支标上“1”。从叶子结点开始，顺着双亲域parent反推上去一直到根结点，并将路径上的“0”或“1”连接而得的序列就是叶子结点所对应的字符的二进制编码的逆序。,译码：由于每个字符对应一个叶子结点，则任何一个字符的编码不是另一个字符的编码的前缀，因此，只要顺序扫描电文，就很容易译出相应的电文。,3、如何得到使电文总长最短的二进制前缀编码,具体译法是：从赫夫曼树的根结点出发，用待译码的二进制位串中逐位取码，与二叉树分支上标明的“0”，“1”相匹配，确定一条到达叶子结点的路径。若码是“0”，则向左走，否则向右走到下一层的结点，一旦到达叶子结点，则译出一个字符。再重新从根结点出发，从二进制位串中的下一位开始继续译码直至二进制电文结束。,例题1：已知某系统在通讯联络中只可能出现八种字符，其概率分布分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计赫夫曼编码。,设权W=（5，29，7，8，14，23，3，11），n=8，则m=15，按上述算法可构造一棵赫夫曼树，其存储结构HT的初始状态如6.27(a)所示，其终结状态如6.27(b)后图所示。,3、如何得到使电文总长最短的二进制前缀编码,设置一个结构体数组保存赫夫曼树中各结点的信息.,其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组中的序号，从而建立起结点之间的关系。,构造赫夫曼树时，首先将由n个字符形成的n个叶结点存放到数组的前n个分量中，然后根据前面介绍的赫夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。,3、如何得到使电文总长最短的二进制前缀编码,例 w=5,29,7,8,14,23,3,11,123456789101112131415,Weight parent lchild rchild,例题2：要传输的电文是CAS；CAT；SAT；AT 要传输的字符集 D=C,A,S,T,;字符出现频率 w=2,4,2,3,3,T:00；:01 A:10 C:110 S:111,译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束,例 电文是CAS;CAT;SAT;AT 其编码“11010111011101000011111000011000”,例 编码为“1101000”其电文只能是“CAT”,1.掌握树的相关概念、树的表示和树的性质。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树是二叉树各种操作的基础。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。4.掌握根据先序遍历和中序遍历构造二叉树。5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。掌握 1 至 2 种建立二叉树和树的存储结构的方法。6.了解最优二叉树的特性，掌握建立最优二叉树和赫夫曼编码的方法。,第6章 学习要点,一、单项选择题 1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法。（A）正确（B）错误 2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是。（A）空或只有一个结点（B）完全二叉树（C）二叉排序树（D）高度等于其结点数,第6章 作业,3、深度为5的二叉树至多有 个结点。（A）16（B）32（C）31（D）10 4、根据使用频率为5个字符设计的哈夫曼编码不可能是（A）111，110，10，01，00（B）000，001，010，011，1（C）100，11，10，1，0（D）001，000，01，11，10,第6章 作业,二、填空题 1、树和二叉树的主要差别是，。2、深度为k的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是。3、一棵二叉树的第i(i1)层最多有 个结点；一棵有n（n0）个结点的满二叉树共有 个叶子结点和 个非叶子结点。,第6章 作业,三、计算题,第6章 作业,1、已知二叉树的先序、中序和后序序列分别如下，其中有一些看不清的字母用*表示，请构造出一棵符合条件的二叉树并画出该二叉树。先序序列是：*BC*FG中序序列是：CB*EAG*后序序列是：*EDB*FA,2、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍历的结果。,3、设给定权集w=2，3，4，7，8，9，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。,