《数据结构PPT教学课件-第六章 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构PPT教学课件-第六章 树和二叉树.ppt（125页珍藏版）》请在三一办公上搜索。
1、第六章 树和二叉树,引言：,树型结构是一类重要的非线性结构。树型结构是结点之间有分支，且具有层次关系的结构，非常类似于自然界中的树。树结构在客观世界大量存在。例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用：在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；Windows操作系统中对磁盘文件的管理。,南信大,叶子,根,子树,第六章 树和二叉树6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 哈夫曼树及应用,树的定义、术语、操作,二叉树定义、性质、操作,二叉树的存储结构(重点)顺序存储、链接存储,线索
2、二叉树(难点)（特殊的链接存储结构）,二叉树运算,内容及重、难点,6.1,6.2,6.2,6.3,6.3,6.4,6.5,6.1 树的定义与术语,一、树的定义 树是由n(n 0)个结点组成的有限集合。如果n=0，称为空树；如果n 0，则：有一个特定的元素称之为根(root)的结点，除根以外的其他结点划分为m(m 0)个互不相交的有限集合T1,Tm，每个集合又是一棵树，并且称之为根的子树(subTree)。,根,子树,例：,1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径。,(非空)树结构特
3、点：,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),(A(B(E(K,L),F),C(G),D(H(M),I,J)广义表,二、树的表示方法,凹入表,结点(node)结点的度(degree)结点的子树个数分支(branch)结点 度不为0的结点根(root)即根结点(没有前驱)叶(leaf)结点 度为0的结点孩子(child)结点 双亲(parent)结点 兄弟(sibling)结点 具有同一双亲的结点,三、树的基本术语,结点A的度：3结点B的度：2结点M
4、的度：0,分支结点：A,B,C,D,E,H叶结点：K，L，F，G，M，I，J,结点A的孩子：B，C，D结点B的孩子：E，F,结点I的双亲：D结点L的双亲：E,结点B，C，D为兄弟结点K，L为兄弟,祖先(ancestor)结点 结点的祖先是从根到该结点所经分支上的所有结点.子孙(descendant)结点 以某结点为根的子树中的任一结点都为该结点的子孙.结点的层次(level)根结点的层数为1，其余结点的层数为双亲结点的层数加1 树的高度(depth)树中结点的最大层数 树的度(degree),树的基本术语(续),结点K的祖先：A,B,E结点B的子孙：E,F,K,L,树的度：3,树的高度：4,结
5、点A的层次：1结点M的层次：4,有序树 子树的次序不能互换 无序树 子树的次序可以互换 森林（Forest）m棵互不相交的树的集合,基本术语（续）：,树的运算分3大类：第一类：查找类遍历树中每个结点、求树的状态（如树高度、判树空）查找满足某种特定关系的结点,如查找根结点等第二类，插入类包括初始化空树、构造树、在树的当前结点上插入一个新结点等；第三类，删除类包括清空树、销毁树、删除树中结点。,四、树的基本操作（P118）,五、树的抽象数据类型定义 ADT Tree数据对象D：由n个具有相同特性的元素构成的集合数据关系R：若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root
6、;(2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树.基本操作P：,Root(T)/求树的根结点,Value(T,cur_e)/求当前结点的元素值,Parent(T,cur_e)/求当前结点的双亲结点,LeftChild(T,cur_e)/求当前结点的最左孩子,CreateTree(&T,definition)/构造树,InitTree(&T)/初始化置空树,TreeEmpty(T)/判定树是否为空树,TreeDepth(T)/求树的深度,TraverseTree(T,Visit()/遍历,Assign(T
7、,cur_e,value)/给当前结点赋值,InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树,RightSibling(T,cur_e)/求当前结点的右兄弟,ClearTree(&T)/清空树,DestroyTree(&T)/销毁树,DeleteChild(&T,&p,i)/删除结点p的第i棵子树,ADT Tree,6.2 二叉树,6.2.1 二叉树的定义,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,说明（1）二叉树中每个结点最多有两棵子树；二叉树每个结
8、点度小于等于2；（2）左、右子树不能颠倒有序树；（3）二叉树是递归结构。,二叉树的五种基本形态,问题：1.只有两个结点的二叉树有几种不同的形态？,2.只有3个结点的二叉树有几种不同形态？分别画出来。,二叉树的基本操作,查找类,插入类,删除类,Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit()
9、;PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();,InitBiTree(,ClearBiTree(,性质1 若二叉树的层次从1开始,则在二叉树的第 i 层最多有 2i-1 个结点。(i 1)证明用数学归纳法,性质2 高度为 k 的二叉树最多有 2k-1个结点。(k 1)证明用求等比级数前k项和的公式 20+21+22+2k-1=2k-1,6.2.2 二叉树的性质,性质3 对任何一棵二叉树,如果其叶结点有 n0 个,度为2的非叶结点有 n2 个,则有 n0n21,证明：1、结点总数为度为0的结点加上度为1的结点再加上度为2的结点
10、：n=n0+n1+n22、另一方面，二叉树中1度结点有一个孩子，2 度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：n=n1+2n2+13、两式相减，得到：n0=n2+1,定义1 满二叉树(Full Binary Tree)一棵深度为k 且有2k-1个结点的二叉树。,定义2 完全二叉树(Complete Binary Tree)若设二叉树的高度为h，则共有h层。除第h层外，其它各层(1h-1)的结点数都达到最大个数，第h层从左向右连续有若干结点，这就是完全二叉树。,定义两种特殊的二叉树：,完全二叉树,完全二叉树的特点：（1）除最后一层外，每一层都取最大结点数，最后一层结点都有集中
11、在该层最左边的若干位置。（2）叶子结点只可能在层次最大的两层出现。（3）对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次为L或L+1。,满二叉树的特点：每一层都拥有最多结点数,思考：满二叉树与完全二叉树的有何异同点？满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。,性质4 具有n个结点的完全二叉树的高度 为+1。,证明：设深度为k，根据二叉树性质2知：2k-1-1n2k-1，即：2k-1 n 2k，于是有：,当i1,结点i为根结点，无双亲结点，否则其双亲为;若2in,结点i无
12、左子女;否则其左子女为2i;若2i1n,结点i无右子女;否则其右子女为2i1。,性质5 对具有n个结点的完全二叉树进行编号（按层次从左到右）编号可以反映二叉树结点之间的关系。,1,2,4,3,5,6,8,9,10,7,11,12,13,14,15,16,17,例：,i=8,其双亲为4号结点。i=18，则9号结点无左子女。i=14，则7号结点的左子女为14号结点。i=19，则9号结点无右子女。i=15，则7号结点的右子女为15号结点。,顺序存储结构链接存储结构二叉链表三叉链表,6.2.3 二叉树的存储,一、顺序存储结构 用一组连续的存储单元存储二叉树的结点数据。要求：必须把二叉树中的所有结点，按
13、照一定的次序排成为一个线性序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。,二叉树的顺序存储示例：,对于完全二叉树，结点的层次序列反映了整个二叉树的结构。对于一般二叉树，则要通过添加虚结点将其扩充为完全二叉树。,二叉树的顺序存储示例：,思考：对如下一棵二叉树采用顺序存储结构，需要添加几个空结点?,小结：对于完全二叉树：结点编号完全可反映出该二叉树中结点之间的逻辑关系，可将此类二叉树中结点的编号与数组下标建立一一对应关系，所以采用顺序存储结构较好。对于一般的二叉树：需要添加“虚”结点，使之成为一棵完全二叉树，此时仍可用顺序存储结构表示这棵二叉树。但这样可能造成空间浪费，最坏情况是：深
14、度为k且只有k个结点的单支树，需要长度为2k1的空间。,二、二叉树的链式存储结构结点结构的设计二叉链表结点结构三叉链表结点结构,二叉链表,typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,在n个结点的二叉链表中，有n+1个空指针域,空指针个数：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1,结点包含三个域：数据域、左指针域、右指针域,三叉链表,typedef struct BiTNode TElemType data
15、;struct BiTNode*lchild,*rchild,*parent;BiTNode,*BiTree;,结点包含四个域：数据域、双亲指针域、左指针域、右指针域,6.3 遍历二叉树和线索二叉树,遍历定义：指按照某种顺序访问二叉树中的每个结点，并且使每个结点被访问一次且仅一次。,6.3.1 遍历二叉树,遍历操作使非线性结构线性化。,遍历的顺序,T、L、R分别代表访问根结点、遍历左子树、遍历右子树遍历方式有6种：TLR、TRL、LTR、RTL、LRT、RLT。TLR（先序遍历）;LTR（中序遍历）;LRT（后序遍历）;,按深度遍历,按广度遍历(层序遍历)：从上到下、从左到右。,T L R,先
16、序遍历序列：A B D C,先序遍历:,先序遍历（T L R）若二叉树非空（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树,L T R,中序遍历序列：B D A C,中序遍历（L T R）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树,中序遍历:,L R T,后序遍历序列：D B C A,后序遍历（L R T）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点,后序遍历:,先序：a*bc def,中序：ab*cdef,后序：abcd*ef,(一)二叉树遍历的递归算法,先序遍历的定义等价于：若二叉树为空，结束 基本项（终止条件）若二叉树非空 递归项
17、（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；,1、先序遍历递归算法(采用二叉链表)Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)/*功能:先序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/if(T)/若根结点不空 if(visit(T-data)/访问根结点 if(PreOrderTraverse(T-lchild,visit)/先序遍历根的左子树 if(PreOrderTraverse(T-rchild,visit)/先序遍历根的右子树 return OK;,返回,返回,返回,返回,
18、A,C,B,D,返回,先序序列：A B D C,B,A,C,E,D,G,F,先序遍历序列：,A,B,D,E,G,C,F,A,B,D,E,G,C,F,2、中序遍历递归算法Status InOrderTraverse(BiTree T,Status(*visit)(TElemType e)/*功能:中序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/if(T)/若根结点不空 if(InOrderTraverse(T-lchild,visit)/中序遍历根结点的左子树 if(visit(T-data)/访问根结点 if(InOrderTraverse(T-rchild,visit)
19、/中序遍历根结点的右子树 return OK;,3、后序遍历递归算法Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType e)/*功能:后序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/if(T)/若根结点不空 if(PostOrderTraverse(T-lchild,visit)/后序遍历根结点的左子树 if(PostOrderTraverse(T-rchild,visit)/后序遍历根结点的右子树 if(visit(T-data)/访问根结点 return OK;,(二)二叉树遍历的非递归算法 递归算法逻
20、辑清晰、易懂；但在实现时，由于函数调用栈层层叠加，效率不高，而采用非递归算法可提高效率。,T:A,T:B,T:E,T:G,栈在先序遍历中的作用,B,A,C,E,D,G,F,T,先序遍历序列：,A,B,D,E,G,栈用于存放已处理的根结点，以备在处理完该结点的左子树后再处理其右子树,前序遍历的非递归算法基本思路：1)、访问当前结点（初始时是根结点）2)、结点进栈，沿左指针查找左孩子。3)、若有左孩子，转第1步。4)、若无左孩子，判栈空？空则结束。非空，栈顶结点出栈,转向右子树，转第1步。,1、前序遍历的非递归算法,1、前序遍历的非递归算法 使用一个栈S，存放已处理的根结点，以备在处理完该结点的左
21、子树后再处理其右子树。初始，栈为空。Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)/*功能:前序遍历二叉树;参数:T为二叉树的根,visit为对结点的处理方法*/P=T;InitStack(S);/初始化栈 while(p|(!StackEmpty(S)/二叉树未处理完 if(p)/当前未遇空结点 if(!visit(p-data)/访问当前子树根结点 return ERROR;/访问当前子树根结点时出错 push(S,p);/结点压栈 p=p-lchild;/继续向左子树前进 else pop(S,p);p=p-rch
22、ild;/弹出栈顶结点，处理其右子树 return OK;,处理的数据项 栈S中内容 p的指向,空 A,A A B,B AB C,C ABC,AB,A D,D AD,A E,E AE,A,空,p,B,A,C,E,D,G,F,T,T:A,T:B,T:E,T:G,栈在中序遍历中的作用,中序遍历序列：,D,B,G,栈用于保存当前结点的祖先结点,2、中序遍历的非递归算法Status InorderTraverse(BiTree T,Status(*visit)(TElemType e)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)/未到达左子树末端 Push(
23、S,p);/当前结点压栈 p=p-lchild;/继续向左子树前进 else/已达到左子树末端 Pop(S,p);/弹出栈顶 if(!visit(p-data)return ERROR;/处理该结点 p=p-rchild;/向右子树前进 return OK;,分析:对左图所示的二叉树执行中序遍历的非递归算法,执行过程中栈、指针的变化情况.,3、后序遍历的非递归算法 遇到一个结点，将它压入栈中，然后去遍历它的左子树；遍历完左子树后，还不能立即访问该结点，而是要根据其右指针指示的结点去遍历该结点的右子树。遍历完右子树后才能从栈顶弹出该结点。为此，需给栈中每个元素加上一个特征位，以示区别：特征位为L
24、，表示已进入该结点的左子树，将从左边回来；特征位为R，表示已进入该结点的右子树，将从右边回来.,有关的说明：typedef enumL,R Tag;typedef struct BiTNode/二叉树结点类型定义 TElemType data;Tag tag;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,lchild data rchild Tag,后序遍历的非递归算法Status PostorderTraverse(BiTree T,Status(*visit)(TElemType e)if(T)InitStack(S);p=T;push(S,
25、NULL);/初始栈底放一空指针 while(p|!StackEmpty(S)while(!p)p-tag=L;Push(S,p);/进入左子树，赋左标志，入栈 p=p-lchild;/左子树已走到尽头 Pop(S,p);/从栈顶弹出一个结点 while(p,处理的数据项 栈S中内容 p的指向 tag,空 A L,AL B L,ALBL C L,ALBLCL(C左),ALBL C L,ALBLCR(C右),ALBL C R,C AL B L,ALBR D L,ALBRDL,ALBR D L,ALBRDR E L,ALBRDREL,ALBRDR E L,ALBRDRER,p,处理的数据项 栈S中
26、内容 p的指向 tag,ALBRDR E R,E ALBR D R,D AL B R,B 空 A L,AR,空 A R,A 空,三、按层次遍历二叉树,层序遍历,按自上而下，每层从左到右顺序访问结点。例如：-+/a*e f b-c d,层序遍历,先根，后子树；先左子树，后右子树,队列,队头,层序遍历序列:,层序遍历,队列,队头,A,层序遍历序列:,层序遍历,队列,队头,A,层序遍历序列:A,Status CreateBiTree(BiTree/CreateBiTree,例如：建立如上二叉树的二叉链表结构应输入：ABC#DE#G#F#,建立二叉树创建二叉链表（按先序序列建立二叉树）,#,#,#,#
27、,#,#,#,#,T,void LeafNum(BiTree T,int*n)/采用二叉链表存储二叉树，n用于累加二叉树的叶子结点/的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数 if(T)if(T-lchild=NULL,例、编写 求二叉树的叶子结点个数的算法 输入：二叉树的二叉链表 结果：二叉树的叶子结点个数,二叉树的遍历应用举例,int Depth(BiTree T);/求二叉树的高度int d1,d2;if(!T)return 0;elsed1=Depth(T-lchild);d2=Depth(T-rchild);return max(d1,d2)+1;,例、编写 求二叉树
28、的高度的算法。输入：二叉树的二叉链表 输出：二叉树的高度,二叉树的遍历应用举例,T,6.3.2 线索二叉树,1、什么是线索二叉树？在存储结构中保存遍历所得“前驱”和“后继”的信息。线索二叉树概念:对二叉链表的结点增加两个标志域，并作如下规定:若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域的值为0;否则，lchild域的指针指向其“前驱”，且左标志的值为1.若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为0;否则，rchild域的指针指向其“后继”，且右标志的值为1.,线索二叉树的结点结构：,lchild ltag data rtag rchild
29、,ltag=0/lchild域指示结点的左孩子 1/lchild域指示结点的前驱rtag=0/rlchild域指示结点的右孩子 1/rchild域指示结点的后继,0,0,0,0,1,1,1,1,1,1,typedef enum Link,Thread PointerTag;/Link：指针；Thread：线索typedef struct BiThrNode TElemType data;struct BiThrNode*lchild,*rchild;PointerTag Ltag,Rtag;BiThrNode,*BiThrTree；,线索二叉树的生成算法（算法6.6,见教材P134）,为方便添
30、加结点的前驱或后继，需要设置两个指针：Thrt指针当前结点之指针；pre指针前驱结点之指针。,若Thrt-lchildNULL,则 Thrt-Ltag=1;Thrt-lchildpre;/Thrt的前驱结点指针pre存入左空域若pre-rchildNULL,则 pre-Rtag1;pre-rchild=Thrt;/Thrt存入其前驱结点pre的右空域,void InThreading(BiThrTree Thrt,BiThrNode*,算法遍历中序线索二叉树,在中序线索二叉树中找结点后继的方法：（1）若rtag=Thread,则rchild域直接指向其后继（2）若rtag=Link,则结点的后
31、继应是其右子树的左链尾（ltag=Thread)的结点,在中序线索二叉树中找结点前驱的方法：（1）若ltag=Thread,则lchild域直接指向其前驱（2）若ltag=Link,则结点的前驱应是其左子树的右链尾（rtag=Thread)的结点,BiThrNode*find_succ(BiThrNode*p)/在中序线索树中找指定结点的后继结点，返回其指针 BiThrNode*q=p-rchild;if(!p-rtag)while(q-ltag=0)q=q-lchild;return q;,void InOrderThread(BiThrTree Thrt)/中序遍历以Thrt为根的中序线索
32、二叉树 BiThrTree p=Thrt;if(p)while(p-ltag=0)p=p-lchild;/找到最左下结点，即中序的第一个结点printf(“%3c”,p-data);/访问该结点while(p-rchild!=NULL)/反复执行在中序线索树中找指定结点的后继结点操作，访问相应结点 p=find_succ(p);/找该结点的后继 printf(“%3c”,p-data);/访问其后继结点,中序线索二叉树的中序遍历算法,6.4.1 树的存储结构 1、双亲表示法(顺序存储)采用一组连续空间存储树的结点,通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。,无双亲,6.4
33、树和森林,0 1 2 3 4 5 6 7 8 9,data link,树的孩子链表图示,结点的孩子结点链表,(1)孩子链表：对树的每个结点用线性链表存储它的孩子结点。,找一个结点的孩子十分方便，但要找一个结点的双亲则要遍历整个结构,2、孩子表示法通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。,0 1 2 3 4 5 6 7 8 9,data parent link,带双亲的孩子链表,结点的孩子结点链表,(2)双亲孩子表示法：结合双亲表示法和孩子表示法,6.4.2 树与二叉树的转换 二叉树与树都可用二叉链表存储，以二叉链表作中介，可导出树与二叉树之间的转换。树与二叉树转换方法：,
34、例：,森林-树的集合 将森林转换为二叉树的转换规则：若 F=T1，T2，T3，Tn 是森林，则 B（F）=root,LB,RB（1）若 F 为空，即 n=0，则 B(F)为空树。（2）若 F 非空，则 B（F）的根是T1的根，其左子树为LB，是从T1根结点的子树森林F1=T11，T12，T1m转换而成的二叉树；其右子树为RB，是从除T1外的森林F=T2，T3，Tn转换而成的二叉树；,包含3棵树的森林,每棵树对应的二叉树,森林对应的二叉树,6.4.3 树和森林的遍历深度优先遍历（1）先根次序遍历树（2）后根次序遍历树广度优先遍历树（按层次遍历树）,树的遍历,1.先根遍历：若树为空，则空操作否则访
35、问树的根结点依次先根遍历每棵子树,2.后根遍历：若树为空，则空操作否则依次后根遍历每棵子树访问树的根结点,树的遍历,A,树的先根遍历：ABDEGHICFKLM树的后根遍历：DGHIEBFCLMKA,树的先根遍历等同于对转换所得的二叉树进行先序遍历树的后根遍历等同于对转换所得的二叉树进行中序遍历,层序遍历,遍历序列：A，B，C，D，E，F，G，H，I，J,6.5 赫夫曼树及应用,1.什么是Huffman树？2.建立Huffman树的算法Huffman算法（1）Huffman树的存储结构（2）算法描述3.Huffman编码、Huffman译码,引例,编写程序将百分制表示的成绩score转换为等级分
36、grade，规则为：grade=A:90 score 100grade=B:80 score 90grade=C:70 score 80grade=D:60 score 70grade=F:score 60,转换n个成绩的平均比较次数：3.15*n,转换n个成绩的平均比较次数：2.05*n,转换n个成绩的平均比较次数：2.2*n,（a）WPL=0.05 10.152 0.4030.30 40.10 4=3.15 对10000个成绩，共需要31500次比较。（b）WPL=0.05 40.153 0.4010.30 20.10 4=2.05 对10000个成绩，共需要20500次比较。（c）WPL
37、=0.05 30.153 0.4020.30 20.10 2=2.20 对10000个成绩，共需要22000次比较。,上述三个方案,一、赫夫曼树(最优二叉树)的概念路径：从一个结点到另一个结点之间的若干个分支.路径长度：路径上的分支数目称为路径长度.结点的路径长度：从根到该结点的路径长度.树的路径长度：树中所有叶子结点的路径长度之和；记为PL.在结点数相同的条件下，完全二叉树是路径最短的二叉树。,结点的权：根据应用的需要可以给树的结点赋权值；结点的带权路径长度(Weighted Path Length,WPL)从根到该结点的路径长度与该结点权的乘积；树的带权路径长度=树中所有叶子结点的带权路径
38、之和；记作：示例赫夫曼树：设有n个权值(w1,w2,wn)，构造有n个叶子结点的严格二叉树，每个叶子结点有一个 wi 作为它的权值。则带权路径长度最小的严格二叉树称为哈夫曼树。,7 5 2 4,4,7,5,2,4,7,5,2,4,7,5,2,WPL=7*2+5*2+2*2+4*2=36,WPL=7*1+5*2+2*3+4*3=35,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,1初始化:构造一个森林F=(T1,T2,Tn)，其中每棵二叉树Ti有且仅有一个根结点，权值为Wi；2在F中选取两棵根结点权值最小的树Ti,Tj(权值分别为Wi,Wj，并设Wi
39、=Wj)，分别作为左、右子树，生成一棵新二叉树Tk，Tk根结点权Wk=Wi+Wj；3从F中删除Ti,Tj，同时将Tk加入F；4重复 2、3，直到F中只含一棵树为止；即为Huffman树。,(一)构造赫夫曼树的步骤：,二、赫夫曼树的构造Huffman算法,例：构造以W=（2，4，5，7）为叶结点的赫夫曼树。,(二)赫夫曼算法的实现：,1、赫夫曼树的存储结构：,当给定n个叶结点构造赫夫曼树,共需要进行n-1次合并.每次合并都要产生一个新结点。合并过程中共产生n-1个新结点。故：赫夫曼树中总结点数为2n-1.如何设计赫夫曼树的存储结构？将赫夫曼树中的2n-1个结点可以存储在一个大小为2n-1的数组中
40、。顺序存储 结点结构定义：,typedef struct int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;,赫夫曼树的存储结构举例：设叶结点权:2,4,5,7,序号,权值,父母,左孩子,右孩子,1,2,3,4,5,6,7,2、赫夫曼算法描述：,算法的思想：（1）Huffman树初始化；（2）i从1开始循环n-1次：从序号1当前结点(序号:n+i-1)中选取权值最小、且无父母结点(parent域为0)的两个结点，其序号分别为l,r;以l,r分别为左、右子树的根生成一棵新的二叉树,新树根结点存于序号为n+1位置,其权值=左右子树根权之
41、和.,算法的输入与输出：(HuffmanTree&HT,int w,int n),Select(HuffmanTree HT,int m,int l,int r),CreateBT(HuffmanTree&HT,int R,int l,int r),Huffman算法：,void Huffman(HuffmanTree,Select（）函数,void Select(HuffmanTree HT,int m,int r=j:,CreateBT（）函数,void CreateBT(HuffmanTree,哈夫曼树的构造过程举例：设叶结点权:2,4,5,7,序号,权值,父母,左孩子,右孩子,1,2,
42、3,4,5,6,7,6,0,1,2,5,5,11,0,3,5,6,6,18,0,4,6,7,7,三、赫夫曼编码,在远程通讯中，要将待传字符串转换成二进制的0、1序列。最简单的编码方式是采用等长编码 设要传送的字符为：ABACCDA 若编码为：A00 B01 C10 D11,若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换后的二进制编码串便可能缩短。,设要传送的字符为：ABACCDA若编码为：A0 B00 C1 D-01,关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀，这种编码称之为前缀编码。,ABACCDA,000
43、011010,0000AAAA ABA BB,译码,如何设计前缀编码?,设要传送的字符为：ABACCDA,采用二叉树设计二进制前缀编码,左分支用“0”表示右分支用“1”表示,可编码为：A0 B110 C10 D-111,译码过程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。,A B A C C D A,假设组成电文的字符集合D=d1,d2,dn,每个字符 di 在电文中出现的次数为ci，对应的编码长度为li。因此，求电文的总长最短问题可转换为：,如何得到电文总长最短的前缀编码？,以n种字符出现的频率作为权值，设计一棵赫夫曼树,设计示
44、例：已知某系统在通讯时出现8种字符,其频率为：,a b c d e f g h0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计Huffman编码。,a:0001b:10c:1110d:1111e:110f:01g:0000h:001,Huffman编码算法：,算法的思想：（1）以各字符出现频率为叶结点权值 构造Huffman树;（2）对每个叶结点执行：由叶结点到根结点逆向求每个字 符的Huffman编码.,权值,父母,左孩子,右孩子,序号,字符,a 1,b 2,c 3,d 4,e 5,f 6,g 7,h 8,9,10,11,12,13,14,15,9,10
45、,11,12,13,14,1,0,0,0,所以：a的编码为0001,8,19,42,58,29,15,100,哈夫曼编码的存储结构：,HC,序号,0 0 0 1,1 0,1 1 1 0,1 1 1 1,1 1 0,HC0不用！,typedef char*Huffmancode;,void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int W,int n),存储准备,Huffman(HT,W,n);,创建Huffman树,对每个字符求其编码,HC空间申请;临时工作空间申请;,for(i=1;i=n;i+),在当前结点的parent域不为0(未追溯到根
46、)时,循环执行:if(当前结点为其父母的左孩子)则 编码=0;else if(当前结点为其父母的右孩子)则 编码=1;,临时工作空间工作指针初始化;,将存在临时工作空间中的该字符的huffman编码链入HC,END,void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int W,int n),Huffman(HT,W,n);/创建Huffman树,/分配n+1个字符编码的头指针向量HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);/分配存放字符编码的临
47、时工作空间cdn-1=0;/字符串结束符,HC空间申请;临时工作空间申请;,for(i=1;i=n;i+)/逐个字符求Huffman编码,start=n-1;/编码结束符位置,for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶到根逆向求编码 if(HTf.lchild=c)cd-start=0;else if(HTf.rchild=c)cd-start=1;,/为第i个字符分配编码存储空间 HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,在当前结点的parent域不为0(未追溯到根)时,循环执行:i
48、f(当前结点为其父母的左孩子)则 编码=0;else if(当前结点为其父母的右孩子)则 编码=1;,free(cd);/释放临时工作空间,Huffman译码算法：,算法的思想：对Huffman编码串每个符号的译码，都是从Huffman树的根结点向叶结点下行的过程：逢“0”向左孩子下行；逢“1”向右孩子下行；当下行遇到叶结点时，该叶结点中的字符就是译码符号.,设Huffman编码为：0 0 0 1 1 1 1 0 1 1 1 1 0 0 1,a,c,译码结果为：acdh,举例：,Status HuffmanDecoding(HuffmanCode HC,HuffmanTree HT,int n
49、,char*HCode,HuffmanDecode,本章小结,1.定义和性质(递归特性、5个性质),2.存储结构,3.遍历,4.线索化,孩子-兄弟,线索二叉树,习题,1、在树型结构中，树根结点没有_结点，其余每个结点有且只有_个前驱结点；叶子结点没有_结点，其余每个结点的后继结点可以有_。2、设某二叉树的中根序列CBEDAGJIFH，后根序列为CEDBJIGHFA，试构造出这棵二叉树，画出构造过程和所得到的二叉树。3、若一棵树中度为的结点有n1个，度为2的结点有n2个，度为m的结点有nm个,该树有多少个叶结点？,习题,4、写一个递归函数计算二叉树的高度。5、试证明：在二叉链表中，空指针的个数是二叉树的结点数加1。6、在一份电文中共使用6种字符：a,b,c,d,e,f，,习题7、对如下的二叉链表进行中序线索化操作，画出添加线索后的线索树。,
