第6章 树和二叉树.ppt

第6章 树和二叉树,6.1 树的类型定义,6.2 二叉树的类型定义和实现,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.6 Huffman树与Huffman编码,6.5 树与等价问题,6.1 树的类型定义,树 是 n 个结点的有限集 D，当n1 时：1)有一个特定的结点 root 被称为根(结点);2)根以外的结点被分成 m(m0)个不相交的有限集 T1,T2,Tm，其中每个集合又是一棵树，称为根的子树。,树的定义是一个递归的定义，可以用广义表的形式描述：Tree=(root,T1,T2,Tm)其中 root 是结点类型，其余为树类型(广义表类型)。,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素(无前驱),一个首元素(无前驱),最后一个数据元素(无后继),多个尾元素(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),基 本 术 语,结 点：数据元素+若干指向子树的分支。,结点的度：分支的个数。,树的度：树中所有结点的度的最大值。,叶子结点：度为零的结点。,分支结点：度大于零的结点。,(从根到结点的)路径：从根到该结点所经分支和结点构成的集合。,孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点,结点的层次：假设根结点的层次为 1，第 i 层的结点的子树的根结点的层次为 i+1。,树的深度：树中叶子结点所在的最大层次。,森 林：是m(m0)棵互不相交的树的集合。,有向树：)有确定的根；)树根和子树根之间为有向关系。,有序树：子树之间存在确定的次序关系。,无序树：子树之间不存在确定的次序关系。,就逻辑结构而言，树是二元组：,Tree=(root,F),F 是 m(m0)棵子树的森林，F=(T1,T2,Tm)，其中 Ti=(ri,Fi)；当 m0 时，存在关系：RF=|i=1,2,m,m 0,树的抽象数据类型定义如下：,ADT Tree,若D为空集，则称为空树。否则:1)在D中存在唯一的称为根的数据元素 root；2)当n 1时，其余结点可分为 m(m0)个互不相交的有限集T1,T2,Tm，其中每个子集本身又是符合本定义的一棵树，称为根 root 的子树。,数据对象：,D 是具有相同特性的数据元素的集合。,数据关系：,基本操作：,初始化操作,InitTree(&T)操作结果：初始化置空树。,DestroyTree(&T)初始条件：树 T 存在。操作结果：销毁树 T。,结构销毁操作,CreateTree(&T,definition)操作结果：按定义构造树。,引用型操作,Root(T)初始条件：树 T 存在。操作结果：求树的根结点。,Parent(T,cur_e)初始条件：树 T 存在。操作结果：用 cur_e 返回当前结点双亲的元素值。,Value(T,cur_e)初始条件：树 T 存在。操作结果：用 cur_e 返回当前结点的元素值。,引用型操作（续）,RightSibling(T,cur_e)初始条件：树 T 存在。操作结果：用 cur_e 返回当前结点右兄弟的元素值。,LeftSibling(T,cur_e)初始条件：树 T 存在。操作结果：用 cur_e 返回当前结点左兄弟的元素值。,引用型操作（续）,TreeEmpty(T)初始条件：树 T 存在。操作结果：判定树是否为空树。,TraverseTree(T,Visit()初始条件：树 T 存在。操作结果：按照某种顺序用Visit访问所有的结点。,TreeDepth(T)初始条件：树 T 存在。操作结果：求树的深度。,加工型操作,DeleteChild(&T,&p,i)初始条件：树 T 存在，1 i Degree(p)。操作结果：删除结点p的第i棵子树。,InsertChild(&T,&p,i,c)初始条件：树 T 存在，且 i 1。操作结果：将以c为根的树插入为结点p的第i棵子树。,加工型操作（续）,ClearTree(&T)初始条件：树 T 存在。操作结果：清空树中的所有结点。,ADT Tree,Assign(T,&cur_e,value)初始条件：树 T 存在。操作结果：用 value 给当前结点 cur_e 赋值。,6.2 二叉树的类型定义和实现,二叉树中每个结点至多只有 2 棵子树，二叉树的子树有左右之分。,二叉树的五种基本形态：,空树,左右子树均为空树,右子树为空树,左子树为空树,左右子树均不为空树,二叉树的抽象数据类型定义如下：,若D为空集，则称为空树。否则:1)在D中存在唯一的称为根的数据元素 root；2)当n 1时，其余结点可分为2个互不相交的有限集T1，T2，其中每一棵子集本身又是一棵符合本定义的二叉树，T1称为根 root 的左子树，T2称为根 root 的右子树，,ADT BinaryTree,数据对象：,D 是具有相同特性的数据元素的集合。,数据关系：,基本操作：,初始化操作,InitBiTree(&T)操作结果：初始化置空二叉树。,DestroyBiTree(&T)初始条件：二叉树 T 存在。操作结果：销毁二叉树 T。,结构销毁操作,CreateBiTree(&T,definition)操作结果：按定义构造二叉树。,引用型操作,Root(T)初始条件：二叉树 T 存在。操作结果：求二叉树的根结点。,Parent(T,e)初始条件：二叉树 T 存在。操作结果：用 e 返回当前结点双亲的元素值。,Value(T,e)初始条件：二叉树 T 存在。操作结果：用 e 返回当前结点的元素值。,引用型操作（续）,LeftChild(T,e)初始条件：二叉树 T 存在。操作结果：用 e 返回当前结点左孩子的元素值。,RightChild(T,e)初始条件：二叉树 T 存在。操作结果：用 e 返回当前结点右孩子的元素值。,引用型操作（续）,RightSibling(T,e)初始条件：二叉树 T 存在。操作结果：用 e 返回当前结点右兄弟的元素值。,LeftSibling(T,e)初始条件：二叉树 T 存在。操作结果：用 e 返回当前结点左兄弟的元素值。,引用型操作（续）,BiTreeEmpty(T);初始条件：二叉树 T 存在。操作结果：判定二叉树是否为空树。,BiTreeDepth(T)初始条件：二叉树 T 存在。操作结果：求二叉树的深度。,PreOrderTraverse(T,Visit()初始条件：二叉树 T 存在。操作结果：按照先序用Visit遍历二叉树中的所有结点。,InOrderTraverse(T,Visit()初始条件：二叉树 T 存在。操作结果：按照中序用Visit遍历二叉树中的所有结点。,引用型操作（续）,PostOrderTraverse(T,Visit()初始条件：二叉树 T 存在。操作结果：按照后序用Visit遍历二叉树中的所有结点。,LevelOrderTraverse(T,Visit()初始条件：二叉树 T 存在。操作结果：按照层次用遍历Visit二叉树中的所有结点。,引用型操作（续）,加工型操作,InsertChild(&T,&p,LR,c)初始条件：二叉树 T 存在。操作结果：根据LR的值，将以c为根的树插入为结点p的子树。,DeleteChild(T,p,LR);初始条件：二叉树 T 存在。操作结果：根据LR的值，删除结点p的子树。,加工型操作（续）,ClearBiTree(&T)初始条件：二叉树 T 存在。操作结果：清空二叉树中的所有结点。,ADT BinaryTree,Assign(T,&e,value)初始条件：二叉树 T 存在。操作结果：用 value 给当前结点 e 赋值。,二叉树的重要特性,性质 1 在二叉树的第 i 层上至多有2i-1 个结点(i1),证明：用归纳法证明，,i=1层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1ji，命题成立，二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-22=2i-1。,性质 2 深度为 k 的二叉树上至多含 2k-1 个结点(k1)。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为20+21+2k-1=2k-1。,性质 3 对任何一棵二叉树，若它含有 n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。,证明：,设二叉树上结点总数 n=n0+n1+n2，二叉树上分支总数(总度数)b=n1+2n2，而 b=n-1=n0+n1+n2 1，由此，n0=n2+1。,除根结点外，每个结点指向双亲结点的分支只有一条。,两类特殊的二叉树：,满二叉树(Full Binary Tree)：指的是深度为 k 且含有 2k-1 个结点的二叉树。,完全二叉树(Complete Binary Tree)：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,性质4 具有 n 个结点的完全二叉树的深度为 log2n+1,证明：,设完全二叉树的深度为 k，则根据性质 2 得 2k-1 n 2k，log2n为递增函数，log2n k log2n+1，k 必须为整数，因此，k=log2n+1。,性质 5 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：,1)若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；2)若 2i n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；3)若 2i+1 n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。,二叉树的存储结构,#define MAX_TREE_SIZE 100/二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/0 号单元存储根结点SqBiTree bt;,1.二叉树的顺序存储表示,按照依次自上而下、自左至右的顺序，存储完全二叉树结点的元素值。一般二叉树则按完全二叉树编号后存储，编号处无结点的位置不存储。,例6-2 顺序表示下列二叉树,0,1,2,3,4,5,6,7,8,9,10,11,12,13,2.二叉树的链式存储表示,二叉链表,结点结构:,typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,typedef struct TriTNode/结点结构 TElemType data;struct TriTNode*lchild,*rchild;/左右孩子指针 struct TriTNode*parent;/双亲指针 TriTNode,*TriTree;,结点结构:,三叉链表,6.3 遍历二叉树和线索二叉树,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,二叉树由根、左子树和右子树组成。对二叉树而言，可以有三条搜索路径：1）先(根)序遍历：根 左子树 右子树(TLR)2）中(根)序遍历：左子树 根 右子树(LTR)3）后(根)序遍历：左子树 右子树 根(LRT),一.遍历二叉树,若二叉树为空树，则空操作；否则，1)访问根结点；2)先序遍历左子树；3)先序遍历右子树。,1.先(根)序的遍历算法:,访问路径描述：从根结点开始，沿着左子树方向依次访问，当左子树遍历完成，从左子树退回时访问每个结点的右子树。,例6-3 先序遍历下列二叉树,遍历结果(先序序列)为,a b d e h I j k c f g,先序序列的特点：,1）首结点为根结点2）无法区分左右子树,void Preorder(BiTree T,void(*visit)(TElemType/遍历右子树/Preorder,算法的递归描述：,void Preorder(BiTree T,void(*visit)(TElemType/while/Preorder,算法的非递归描述：,若二叉树为空树，则空操作；否则，1)中序遍历左子树；2)访问根结点；3)中序遍历右子树。,2.中(根)序的遍历算法：,访问路径描述：沿着左子树方向找到最“左边”的结点作为起点，从左子树退回时依次访问每个结点及其右子树。,例6-4 中序遍历下列二叉树,遍历结果(中序序列)为,d b h e j i k a f c g,中序序列的特点：,1）无法确定根结点2）若已知根结点，可区分左右子树,void Inorder(BiTree T,void(*visit)(TElemType/遍历右子树/Inorder,算法的递归描述：,void Inorder(BiTree T,void(*visit)(TElemType/while/Inorder,算法的非递归描述：,若二叉树为空树，则空操作；否则，1)后序遍历左子树；2)后序遍历右子树；3)访问根结点。,3.后(根)序的遍历算法：,访问路径描述：找到最“左边”的叶子结点作为起点，每次经过一个结点时需要判断：如果是从左子树返回，则进入右子树；如果从右子树返回，则访问该结点并后退。判断的方法是看该结点的右子树的根是否为刚刚访问的那个结点。,例6-5 后序遍历下列二叉树,遍历结果(后序序列)为,d h j k i e b f g c a,后序序列的特点：,1）尾结点为根结点2）无法区分左右子树,void Postorder(BiTree T,void(*visit)(TElemType/访问结点/Postorder,算法的递归描述：,void Postorder(BiTree T,void(*visit)(TElemType/用q保存刚访问的结点/else/while/Postorder,算法的非递归描述：,例6-6 写出二叉树的三种遍历序列,先序序列：ABDEGCFHI,中序序列：DBGEACHFI,后序序列：DGEBHIFCA,由二叉树的前序序列和中序序列可以唯一确定这棵二叉树。由二叉树的后序序列和中序序列可以唯一确定这棵二叉树。由二叉树的前序序列和后序序列不能唯一确定这棵二叉树。,结论：,例6-7 已知一棵二叉树的先序序列为 ABHFDECKG 和中序序列 HBDFAEKCG，求这棵二叉树,1）根结点 A,2）左子树中序序列 HBDF，右子树中序序列 EKCG,3）左子树先序序列 BHFD，右子树先序序列 ECKG,先序遍历结果(先序序列)-+a*b-c d/e f,中序遍历结果(中序序列)a+b*(c d)e/f,后序遍历结果(中序序列)a b c d-*+e f/-,例6-8 分别以先序、中序和后序遍历下列二叉树,4.按层次的遍历算法：,访问路径描述：按照从上层到下层，每层从左至右的顺序遍历结点。,第 k 层结点的访问顺序为从坐至右，第 k+1 层按照相同的顺序遍历 k 层结点的孩子结点。,算法中用队列暂存第 k 层经过的结点,算法描述：,void LevelTravelTree(BiTree T,void(*visit)(TElemType/LevelTravelTree,二.遍历算法的应用举例,.统计二叉树中叶子结点的个数,算法基本思想:,遍历二叉树，“访问结点(visit)”的操作为：计数。,void CountLeaf(BiTree T,int/if/CountLeaf,.求二叉树的深度,算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加 1。“访问结点(visit)”的操作为：求得左、右子树深度的最大值，然后加 1。遍历顺序为：后序。,首先分析二叉树的深度和它子树深度之间的关系：,int Depth(BiTree T)if(!T)depthval=0;else depthL=Depth(T-lchild);depthR=Depth(T-rchild);depthval=1+(depthL depthR?depthL:depthR);return depthval;/Depth,.二叉树的创建,以字符串的形式输入二叉树：按照二叉树先序遍历的顺序输入二叉树中每个结点的元素。空结点也必须输入。,空树以空格字符“”表示；,只含一个根结点的二叉树：以字符串“A”表示；,例6-9 以字符串“ABCD”表示二叉树 T,A(B(C()D(),Status CreateBiTree(BiTree/CreateBiTree,三.线索二叉树,.何谓线索二叉树？,遍历二叉树的结果是结点的一个线性序列。,先序序列:A B C D E F G H K,中序序列:B D C A H G K F E,后序序列:D C B H K G F E A,BDCAHGKFE,遍历序列中表示线性关系指针称为“线索”。,在二叉链表的结点中增加两个标志域，并作如下规定：,1）若该结点的左子树不空，则 lchild 指针指向其左子树，且左标志的值为 0；否则，lchild 指针指向其前驱，且左标志的值为 1。,2）若该结点的右子树不空，则 rchild 指针指向其右子树，且右标志域的值为 0；否则，rchild 指针指向其后继，且右标志的值为 1。,线索链表的 C 语言描述：,typedef enum Link,Thread PointerThr;/Link=0:指针，Thread=1:线索,typedef struct BiThrNod TElemType data;struct BiThrNode*lchild,*rchild;/左右指针 PointerThr LTag,RTag;/左右标志 BiThrNode,*BiThrTree;,以这种结点定义的二叉树的存储结构称作“线索链表”。其二叉树称为“线索二叉树”。,在线索链表中定义头结点，其 lchild 指向二叉树的根结点，LTag 为 0；rchild 指向遍历序列中的最后一个结点，RTag 为 1。,对二叉树进行遍历，使其变为线索二叉树的过程叫做“线索化”。,遍历序列中首结点的 lchild 指向头结点，尾结点的 rchild 指向头结点。,.线索链表的遍历算法:,例如:对中序线索链表的遍历算法,中序遍历的第一个结点？,左子树上最“左边的”没有左子树的结点。,在中序线索链表中结点的后继？,若无右子树，则为后继线索所指结点；,否则为其右子树进行中序遍历访问的第一个结点。,void InOrder_Thr(BiThrTree T,void(*Visit)(TElemType e)/遍历头结点为 T 的中序线索链表 p=T-lchild;/p 指向根结点 while(p!=T)/最后一个结点的 rchild 指向 T while(p-LTag=Link)p=p-lchild;/第一个结点(*Visit)(p-data);while(p-RTag=Thread/进入右子树/InOrderTraverse_Thr,.建立中序线索链表,BiThrNode*pre=NULL;void InThreading(BiThrTree p)/结点线索化 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);/右子树线索化/if/InThreading,Status InOrderThreading(BiThrTree/处理最后一个结点,pre-RTag=Thread;Thrt-rchild=pre;return OK;/InOrderThreading,在算法中，pre 作为公用变量，在函数 InThreading 中的修改必须反应在算法中。这样，当 InThreading(T)执行完毕时，pre 是其中序遍历序列中的最后一个结点，T 不变。,6.4 树和森林,一.树的存储结构,.双亲表示法,顺序存储结构，每个结点指示双亲结点的位置,0,1,2,3,4,5,6,data,parent,r=0n=6,typedef struct PTNode TElemType data;int parent;/双亲位置域 PTNode;,#define MAX_TREE_SIZE 100,双亲表的 C 语言描述:,typedef struct PTNode nodesMAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;,.孩子链表表示法,顺序+链式存储结构，顺序存放结点，每个结点指向其孩子结点的单链表。,0,1,2,3,4,5,6,data,firstchild,r=0n=6,typedef struct CTNode int child;struct CTNode*next;*ChildPtr;/孩子结点结构,typedef struct ElemType data;ChildPtr firstchild;/孩子链表的头指针 CTBox;/双亲结点结构,typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;,孩子链表的 C 语言描述:,.孩子-兄弟表示法(二叉树表示法),链式存储结构，用二叉链表作为存储结构。左指针指向第一个孩子结点，右指针指向右兄弟结点。,typedef struct CSNode ElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,二叉链表的 C 语言描述:,二.树、森林和二叉树的对应关系,根据二叉链表表示法，任何一棵树和二叉树之间存在对应关系：树对应的二叉树的右子树为空。,设森林为：F=T1,T2,Tm，二叉树为：B=(root,LB,RB),如果森林中的树的根结点之间看作是兄弟关系，则可以构建森林对应的二叉树。,由森林转换成二叉树的转换规则为:,若 F=，即 m=0，则 B=;,若 F，即 m 0，则 root=ROOT(T1)，LB为T1的子树森林 T11,T12,T1n 对应的二叉树，RB为森林 T2,Tm 对应的二叉树。,由二叉树转换为森林的转换规则为：,若 B=，则 F=；,ROOT(T1)=root；由 LB 对应得到 T11,T12,，T1n；由RB对应得到 T2,T3,Tm。,三.树和森林的遍历,1.树的遍历可有三条搜索路径:,按层次遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空，先访问根结点，然后依次先根遍历各棵子树。,若树不空，先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右访问树中每个结点。,先根遍历时顶点的访问次序：,A B E F C D G H I J K,后根遍历时顶点的访问次序：,E F B C I J K H G D A,层次遍历时顶点的访问次序：,A B C D E F G H I J K,例6-10 遍历下列树的顶点序列分别是：,1第一棵树的根结点；,2第一棵树的子树森林；,3其它树构成的森林。,根据森林和二叉树的对应关系，森林由三部分构成：,2.森林的遍历,1.先序遍历,若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中其余树构成的森林。,即：依次从左至右对森林中的每一棵树进行先根遍历。,2.中序遍历,若森林不空，则中序遍历第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中其余树构成的森林。,即：依次从左至右对森林中的每一棵树进行后根遍历。,树的遍历和二叉树遍历的对应关系？,6.6 树与等价问题,一.等价关系与等价类,等价关系：R 是集合 S 上的一个二元关系，满足自反性、对称性和传递性。,若 R 是 S 上的一个等价关系，则由 R 可以产生 S 的唯一划分 S1,S2,，这些子集互不相交，其并集为 S，则子集 Si 称为 S 的R 等价类。,按给定的等价关系划分某几个为等价类，称为等价问题。,二.划分等价类,假设集合 S 有 n 个元素，m 个形如(x,y)(x,yS)的等价偶对确定了等价关系 R，求 S 的划分。,确定等价类的算法：,1）令 S 中的每个元素各自形成一个只含单成员的子集，记作 S1,S2,Sn；,2）重复读入 m 个偶对，对每个读入的偶对(x,y)，判定 x,y 所属子集 Si 和 Sj，则 Si Sj 取代 Si 和 Sj；,3）当 m 个偶对都被处理后，剩余的非空子集即为 S 的 R 等价类。,划分等价类需要对集合进行三个基本操作：,构造只含一个元素的集合；判定两个元素所在的子集；合并两个互不相交的集合。,实现约定：,树型结构表示集合，结点表示元素；根结点的成员兼作子集的名称,基本操作的实现：,森林 F=T1,T2,Tn 表示集合 S，树 Ti 表示每个子集 Si，每个结点代表每个元素，每棵树的根结点同时用来表示子集 Si。,判定某个元素属于某个集合：从某个元素(结点)出发，向上逐级找到根结点。,集合的合并：将一棵树根结点的双亲指向另一棵树的根结点。,采用双亲表示法作为存储结构,typedef PTree MFSet;,int find_mfset(MFSet S,int i)/找到元素 i 所在的集合(根)if(i S.n)return-1;for(j=i;S.nodej.parent 0;j=S.nodesj.parent);return j;/find_mfset,查找和合并函数,int merge_mfset(MFSet/find_mfset,若每次将成员多的根结点指向成员少的根结点，则全部操作的时间复杂度高。,在“并”之前先判断子集中成员的数目，令成员少的根结点指向成员多的根结点,改进：,修改存储结构：根结点 parent 为子集成员数量的负数。,修改后的合并函数,int mix_mfset(MFSet/find_mfset,例6-11 设集合 S=x|1 x n 是正整数，R 是 S 上的一个等价关系。,R=(1,2),(3,4),(5,6),(7,8),(1,3),(5,7),(1,5),求 S 的等价类。,1）开始,分为 n 棵树，每个结点都是根结点,2）处理(1,2),(3,4),(5,6),(7,8)之后,3）处理(1,3),(5,7)之后,4）处理(1,5)之后,改进查找子集算法，当所查元素 i 不在树的第二层时，增加“压缩路径”功能，从根结点到 i 路径上的元素都变为根结点的孩子结点。,int fix_mfset(MFSet S,int i)/找到元素 i 所在的集合(根)if(i S.n)return-1;for(j=i;S.nodej.parent 0;j=S.nodesj.parent);for(k=i;k!=j;k=t)t=S.nodesk.parent;S.nodesk.parent=j;return j;/fix_mfset,6.7 Huffman树与Huffman编码,一.最优二叉树(Huffman树),结点路径长度：从根到该结点的路径上分支的数目。,树的路径长度：树中每个结点的路径长度之和。,树的带权路径长度：树中所有叶子结点的带权路径长度之和。,结点的带权路径长度：从根到该结点之间的路径长度与结点权的乘积。,在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。如果 m=2，称为“最优二叉树”。,例6-12 求下列二叉树的带权路径长度,WPL=60,WPL=89,根据给定的 n 个权值 w1,w2,wn，构造 n 棵二叉树的集合 F=T1,T2,Tn，Ti 为一个权值为 wi 的结点构成的二叉树；,二.构造Huffman树,Huffman算法：,在 F 中选取根的权值最小的两棵二叉树，分别作为左右子树构造一棵新的二叉树，并置这棵新二叉树根的权值为其左右孩子结点的权值之和；,将新二叉树加入 F，并在 F 中删除其左右子树；,重复(2)和(3)两步，直至 F 中只含一棵树为止。,例6-13 已知权值 W=5,6,2,9,7,二叉树集合 F 变化如下：,1）,2）,3）,4）,5）,前缀编码：不等长编码中，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,三.Huffman 编码,利用Huffman 树可以构造一种不等长的二进制编码，并且构造所得的Huffman编码是一种最优前缀编码，即使所传电文的总长度最短。,不等长编码中，出现频率大的字符的编码长度短。,例6-14 假设用于通信的电文由8个字母(AH)组成，字母在电文出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计 Huffman编码。,算法提示：将频率(100)看作是AH 的权值，根据权值的集合构造最优二叉树。每个权值结点最后得到的编码就是相对应的字符的Huffman 编码。,本章学习要点,