数据结构PPT教学课件-第六章 树和二叉树.ppt

第六章 树和二叉树,引言：,树型结构是一类重要的非线性结构。树型结构是结点之间有分支，且具有层次关系的结构，非常类似于自然界中的树。 树结构在客观世界大量存在。例如家谱、行政组织机构都可用树形象地表示。 树在计算机领域中也有着广泛的应用： 在编译程序中，用树来表示源程序的语法结构； 在数据库系统中，可用树来组织信息； windows操作系统中对磁盘文件的管理。 ,南信大,叶子,根,子树,第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 哈夫曼树及应用,树的定义、术语、操作,二叉树定义、性质、操作,二叉树的存储结构(重点) 顺序存储、链接存储,线索二叉树(难点) （特殊的链接存储结构）,二叉树 运算,内容及重、难点,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）除根外的其他结点，都存在唯一条从根到该结点的路径。,(非空)树结构特点：,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),( 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的度：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,结点a的层次：1 结点m的层次：4,有序树 子树的次序不能互换 无序树 子树的次序可以互换 森林（forest） m棵互不相交的树的集合,基本术语（续）：,树的运算分3大类： 第一类：查找类 遍历树中每个结点、求树的状态（如树高度、判树空） 查找满足某种特定关系的结点,如查找根结点等 第二类，插入类 包括初始化空树、构造树、在树的当前结点上插入一个新结点等； 第三类，删除类 包括清空树、销毁树、删除树中结点。,四、树的基本操作（p118）,五、树的抽象数据类型定义 adt tree 数据对象d：由n个具有相同特性的元素构成的集合 数据关系r： 若d为空集，则称为空树 。 否则: (1) 在d中存在唯一的称为根的数据元素root; (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, 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）二叉树中每个结点最多有两棵子树；二叉树每个结点度小于等于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(); 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的结点： n = n0 + n1 + n2 2、另一方面，二叉树中1度结点有一个孩子，2 度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：n = n1 + 2n2 + 1 3、两式相减，得到： n0 = n2 + 1,定义1 满二叉树(full binary tree) 一棵深度为k 且有2k-1个结点的二叉树。,定义2 完全二叉树(complete binary tree) 若设二叉树的高度为h，则共有h层。除第h层外，其它各层(1h-1)的结点数都达到最大个数，第h层从左向右连续有若干结点，这就是完全二叉树。,定义两种特殊的二叉树：,完全二叉树,完全二叉树的特点： （1）除最后一层外，每一层都取最大结点数，最后一层结点都有集中在该层最左边的若干位置。 （2）叶子结点只可能在层次最大的两层出现。 （3）对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次为l或l+1。,满二叉树的特点：每一层都拥有最多结点数,思考： 满二叉树与完全二叉树的有何异同点？ 满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。 满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。,性质4 具有n个结点的完全二叉树的高度 为 +1。,证明： 设深度为k，根据二叉树性质2知： 2k-1-1n2k-1 ，即： 2k-1 n 2k，于是有：,当i1,结点i为根结点，无双亲结点，否则其双亲为 ; 若2in,结点i无左子女;否则其左子女为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 二叉树的存储,一、顺序存储结构 用一组连续的存储单元存储二叉树的结点数据。 要求：必须把二叉树中的所有结点，按照一定的次序排成为一个线性序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。,二叉树的顺序存储示例：,对于完全二叉树，结点的层次序列反映了整个二叉树的结构。 对于一般二叉树，则要通过添加虚结点将其扩充为完全二叉树。,二叉树的顺序存储示例：,思考： 对如下一棵二叉树采用顺序存储结构，需要添加几个空结点?,小结： 对于完全二叉树： 结点编号完全可反映出该二叉树中结点之间的逻辑关系，可将此类二叉树中结点的编号与数组下标建立一一对应关系，所以采用顺序存储结构较好。 对于一般的二叉树： 需要添加 “虚”结点，使之成为一棵完全二叉树，此时仍可用顺序存储结构表示这棵二叉树。 但这样可能造成空间浪费，最坏情况是：深度为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; 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,先序遍历序列：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,(一)二叉树遍历的递归算法,先序遍历的定义等价于： 若二叉树为空，结束 基本项（终止条件） 若二叉树非空 递归项 （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; ,返回,返回,返回,返回,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) /中序遍历根结点的右子树 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; ,(二) 二叉树遍历的非递归算法 递归算法逻辑清晰、易懂； 但在实现时，由于函数调用栈层层叠加，效率不高，而采用非递归算法可提高效率。,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，存放已处理的根结点，以备在处理完该结点的左子树后再处理其右子树。初始，栈为空。 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-rchild; /弹出栈顶结点，处理其右子树 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(s,p); /当前结点压栈 p=p-lchild; /继续向左子树前进 else /已达到左子树末端 pop(s,p); /弹出栈顶 if(!visit(p-data) return error; /处理该结点 p=p-rchild; /向右子树前进 return ok; ,分析: 对左图所示的二叉树执行中序遍历的非递归算法,执行过程中栈、指针的变化情况.,3、后序遍历的非递归算法 遇到一个结点，将它压入栈中，然后去遍历它的左子树；遍历完左子树后，还不能立即访问该结点，而是要根据其右指针指示的结点去遍历该结点的右子树。遍历完右子树后才能从栈顶弹出该结点。为此，需给栈中每个元素加上一个特征位，以示区别： 特征位为l，表示已进入该结点的左子树，将从左边回来； 特征位为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,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中内容 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#,建立二叉树创建二叉链表（按先序序列建立二叉树）,#,#,#,#,#,#,#,#,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; else d1=depth(t-lchild); d2=depth(t-rchild); return max(d1,d2)+1; ,例、 编写 求二叉树的高度的算法。 输入：二叉树的二叉链表 输出：二叉树的高度,二叉树的遍历应用举例,t,6.3.2 线索二叉树,1、什么是线索二叉树？ 在存储结构中保存遍历所得“前驱”和“后继”的信息 。 线索二叉树概念: 对二叉链表的结点增加两个标志域，并作如下规定: 若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域的值为0; 否则，lchild域的指针指向其“前驱”，且左标志的值为1. 若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为0; 否则，rchild域的指针指向其“后继”，且右标志的值为1.,线索二叉树的结点结构：,lchild ltag data rtag rchild,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）,为方便添加结点的前驱或后继，需要设置两个指针： 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, 则结点的后继应是其右子树的左链尾（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为根的中序线索二叉树 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 树和森林,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 树与二叉树的转换 二叉树与树都可用二叉链表存储，以二叉链表作中介，可导出树与二叉树之间的转换。 树与二叉树转换方法：,例：,森林- 树的集合 将森林转换为二叉树的转换规则： 若 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. 先根遍历： 若树为空，则空操作 否则 访问树的根结点 依次先根遍历每棵子树,2. 后根遍历： 若树为空，则空操作 否则 依次后根遍历每棵子树 访问树的根结点,树的遍历,a,b,d,f,c,k,l,m,e,g,h,i,树的先根遍历：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转换为等级分grade，规则为： grade =a: 90 score 100 grade =b: 80 score 90 grade =c: 70 score 80 grade =d: 60 score 70 grade =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=0.05 30.153 0.4020.30 20.10 2=2.20 对10000个成绩，共需要22000次比较。,上述三个方案,一、 赫夫曼树(最优二叉树)的概念 路径：从一个结点到另一个结点之间的若干个分支. 路径长度：路径上的分支数目称为路径长度. 结点的路径长度：从根到该结点的路径长度. 树的路径长度：树中所有叶子结点的路径长度之和；记为pl. 在结点数相同的条件下，完全二叉树是路径最短的二叉树。,结点的权：根据应用的需要可以给树的结点赋权值； 结点的带权路径长度( weighted path length, wpl ) 从根到该结点的路径长度与该结点权的乘积； 树的带权路径长度=树中所有叶子结点的带权路径之和；记作： 示例 赫夫曼树：设有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=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的数组中。 顺序存储 结点结构定义：,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位置,其权值=左右子树根权之和.,算法的输入与输出： ( 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,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,若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换后的二进制编码串便可能缩短。,00010010101100,设要传送的字符为：abaccda 若编码为：a0 b00 c1 d-01,关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀，这种编码称之为前缀编码。,abaccda,000011010,0000 aaaa aba bb,译码,如何设计前缀编码?,设要传送的字符为： abaccda,0110010101110,采用二叉树设计二进制前缀编码,左分支用“0”表示 右分支用“1”表示,可编码为： a0 b110 c10 d-111,译码过程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。,0110010101110,a b a c c d a,假设组成电文的字符集合d= d1,d2,dn ,每个字符 di 在电文中出现的次数为ci，对应的编码长度为li。 因此，求电文的总长最短问题可转换为：,如何得到电文总长最短的前缀编码？,以n种字符出现的频率作为权值，设计一棵赫夫曼树,设计示例：已知某系统在通讯时出现8种字符,其频率为：,a b c d e f g h 0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11,试设计huffman编码。,a: 0001 b: 10 c: 1110 d: 1111 e: 110 f: 01 g: 0000 h: 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,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