第六章树无答案.ppt

1、第 六 章 树 和 二 叉 树,第六章 树和二叉树,6.1 树的定义和基本术语 6.2 二叉树的定义、性质和存储结构 6.3 遍历二叉树与线索二叉树 6.4 树和森林 6.5树与等价问题 6.6 赫夫曼树及其应用,6.1 树的定义和基本术语,1、树的结构特点 结构特点:树是一个层次结构,“有且仅有一个根结点无前驱(第一层);有一或多个叶结点无后继;其余结点有唯一前驱和若干后继” 。 递归定义:树由根结点(唯一)及该根结点的若干(零或多个)“子树”组成。不含任何结点也是树，称为空树,树的图形表示,6.1 树的定义和基本术语,1、树的结构特点 结构特点:树是一个层次结构,“有且仅有一个根结点无前驱

2、(第一层);有一或多个叶结点无后继(最后一层);其余结点有唯一前驱和若干后继” 。 递归定义:树(非空)由根结点(唯一)及该根结点的若干(零或多个)子树组成。空树不含任何结点,树的图形表示,树的操作可递归分解成对根结点及其各子树(由根节点的孩子即子树的根标识)的操作进行,直至空.如求结点数/叶结点数/深度等,int NodeCount(Tree T)/递归法统计所有结点的个数 if(T为空树)n=0; else n=1+NodeCount(子树1)+NodeCount(子树k); return n; int TreeDepth(Tree T)/递归法求树的深度 if(T为空树)d=0; els

3、e d1=TreeDepth(子树1); dk=TreeDepth(子树k); d=max(d1,dk)+1; return d; int LeafCount(Tree T)/递归法统计叶子结点的个数 if(T为空树)n=0; else if(T只含一个根结点)n=1; else n=LeafCount(子树1)+LeafCount(子树k); return n; ,2、ADT树的定义-逻辑结构,右例：D=A,B,M H= 数据对象D:若干数据元素的集合 数据关系R:若|D|=0或1则R为空, 否则R=H,H具体定义如下: (1) D中有唯一元素无前驱,root (2) 若D-root非空则存

4、在它的一个划分D1Dm使得任意两个Di与Dj不相交,且每个Dk中存在唯一元素xi使得H (3)对应于元素集合D-root的划分，关系集合H-, ,也存在划分H1Hm，使得(Di,Hi)也是一个树(root的子树),树的图形表示,3、树的相关术语,空树 根结点(可标识一颗树) 叶子结点 结点的子树 树的子树 结点的度 (叶子结点的度为几) 树的度 终端结点 非终端(分支)结点 内部结点 结点的孩子/双亲/兄弟/祖先/子孙/堂兄弟 结点的层次(从1始) 树的深度、宽度 无序树 有序树 森林:互不相交的树的集合 Tree=(root, F)，F=T1,Tm Ti=ri,Fi,RF 路径与路径长度，如

5、A-D-J长为2 从根结点到任意结点存在唯一路径,树的树形表示,InitTree(/先序遍历 InOrderTraverse(T, Visit();/中序遍历 PostOrderTraverse(T, Visit();/后序遍历 LevelOrderTraverse(T, Visit();/层次遍历,Assign(T, else if(T不空) (*visit)( T的根结点 ); /s1 PreOrderTraverse(T的左子树,(*visit);/s2 PreOrderTraverse(T的右子树,(*visit);/s3 return OK ,先序输出:1 2 3 4 中序输出:2

6、3 1 4 后序输出:3 2 4 1 层次输出:1 2 4 3,2.存储结构：二叉链表,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; BiTree T;/思考树的操作?,3.1 操作：求树深【补】,int TreeDepth(BiTree T)/递归法求树的深度 if(T=NULL)d=0; else d1=TreeDepth(T-lchild1);d2=TreeDepth(T-rchild); if(d1d2)d=d1+1; else d=d2+1; retu

7、rn d; /其余操作类似实现，务必掌握,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;,思路：如果树为空树则深度为0，否则，先递归计算出左子树的深度，再计算出右子树的深度，最后，树的深度为两子树深度的最大值加1,3.2操作：遍历二叉树【P129】,先(根)序遍历:树空无操作，非空则先访问根结点,后递归地先序遍历其左子树；再递归地先序遍历其右子树。 中(根)序遍历:树非空则递归地中序遍历根左子树；后访问根结点,再递归地中序遍历右子树。s2-s1-s3 后(根)序遍

8、历:树非空则递归地后序遍历左子树；后递归地后序遍历右子树，再访问根结点。 s2-s3-s1,先序: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,Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType) if(!T)return OK; else if(T不空) (*visit)( T的根结点 ); /s1 PreOrderTraverse(T的左子树,(*visit);/s2 PreOrderTraverse(T的右子树,(*visit);/s3 return

9、OK; /尚需具体实现, visit可能失败，如求倒数,Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType) if(T) if( (*visit)(T-data) ) /s1 if( PreOrderTraverse(T-lchild,(*visit) /s2 if( PreOrderTraverse(T-rchild,(*visit) /s3 return OK; return ERROR; /只要有一次访问失败则必执行此语句 return OK; /树空时返回OK ,算法思路:定义输出函数PrintElem，调用树的先序遍历函

10、数,并将其传递给先序遍历函数中的参数visit即可,假设元素为整型,3.3 操作:二叉链表的先序输出【补】,Typedef int TElemType; Typedef BiTree Status PrintTElem(TElemType e)printf(%d ,e);return OK; Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType) if(T) if( (*visit)(T-data) ) if( PreOrderTraverse(T-lchild,(*visit) ) if( PreOrderTraverse(T-r

11、child,(*visit) ) return OK return ERROR; else return OK; void main()BiTree T; PreOrderTraverse(T,PrintTElem); ,typedef int TElemType; Status CreateBiTree(BiTree /若元素为字符型则输入时不可随意加空格,先序创建：若输入为0则创建一个空树,停止。否则创建根结点，递归创建左子树，递归创建右子树。如120300400,3.4操作：二叉链表的创建【P131】,Status DestroyBiTree(BiTree ,算法思路：树为空什么都不作，

12、否则，先递归释放左子树，后递归释放右子树，最后释放根结点。,3.5操作:二叉链表的后序递归销毁【补】,遍历应用:由遍历序列确定二叉树(P154例6-5),先序序列+中序序列:先序序列中第1个元素X为根,中序序列中唯有遍历完X的左子树后方访问X,故X之前的abc必构成X的左子树,X之后的def必构成X的右子树.对于子树类似处理,第1个在先序序列中出现的元素Y为该左子树的根,中序序列中Y左侧的元素构成Y的左子树,右侧构成右子树,依此类推,最终可定 中序序列+后序序列:后序序列中最后一个元素为根,中序序列中该结点前的元素为左子树,后的元素为右子树。对于左/右子树,最后一个在后序序列中出现的元素为子树

13、的根结点,再看中序序列,依此类推 先序输出+后序输出不能确定.如AB和BA,先序-+1*2-34/56,中序1+2*3-4-5/6,后序1234-*+56/-,思考:何时先序与中序序列相同,后中序同、先后同如何？,遍历应用P129:表达式的二叉树表示,先序:-+1*2-34/56 前缀表达式/波兰式,中序：1+2*3-4-5/6 中缀表达式,后序:1234-*+56/- 后缀表达式/逆波兰,对于中缀表达式(e1)OP(e2)，令根结点值为OP，左子树为e1，右子树e2，e1与e2递归。如1+2*(3-4)-5/6即( (1)+( (2)*(3-4) ) )-(5)/(6),根据后缀表达式可直接

14、求值(不用考虑优先级)，但求后缀式过程中需用优先级。算符优先法实际在执行过程中隐含形成的逻辑结构就是一颗树。,作业,补充：编写递归算法，计算二叉数结点数 42、编写递归算法,计算二叉树中叶子结点的数目 说明1：假设采用二叉链表存储结构 说明2：分三部分，存储结构定义+思路+代码,中序遍历的非递归描述-完全模拟,递归:调用递归函数时树空则直接返回;树不空先递归访问左子树,中间访问根节点，最后递归访问右子树 转化:何时入栈？何时出栈?入栈、出栈时作什么操作？何时结束？ 【空树 单节点树 普通树】 模拟:T入栈,重复如下操作至栈空： 只要栈顶元素不为则其左孩子入栈。最后栈顶必为，出栈。若下一个栈顶元

15、素不空则出栈访问且右孩子入栈 ,1,2,3,5,Status InOrderTraverse_NonRecur(BiTree T,Status (*visit)(ElemType) SqStack S;InitStack(S); Push(S,T); );/入栈 while(!StackEmpty(S) while(GetTop(S,p) ,中序遍历的非递归描述-略加总结,递归:树空时无操作;树不空时先递归访问左子树,中间访问根节点，最后递归访问右子树 转化:何时入栈？何时出栈?入栈、出栈时作什么操作 总结：设指针p指向根结点:如果p不空,入栈,之后p指向左孩子,开始下次循环;否则p空,出栈访

16、问,令指针指向出栈元素的右孩子,开始下次循环重复至p和栈空,Status InOrderTraverse_NonRecur(BiTree T,Status (*visit)(ElemType) SqStack S;InitStack(S);BiTNode* p=T; while(p|!EmptyStack(S) if(p) Push(S,p); p=p-lchild; else Pop(S,p); if(!(*vist)(p-data)return ERROR; p=p-rchild; return OK; ,时间复杂度:每个结点访问3次,T(n)=O(n) 空间复杂度:栈空间,遍历过程中最大

17、栈长O(n),小 结,树的结构特点及递归定义(非空树由根结点及其子树组成), 二叉树的定义，对二叉树的操作可递归分解成对根结点、左子树(由根节点的左孩子标识)、右子树(根节点右孩子标识)的操作进行.如求结点数/叶结点数/深度/复制/左右互换,int NodeCount(Tree T)/递归法统计所有结点的个数 if(T为空树)n=0; else n=1+NodeCount(子树1)+NodeCount(子树k); return n; int LeafCount(Tree T)/递归法统计叶子结点的个数 if(T为空树)n=0; else if(T只含一个根结点)n=1; else n=Leaf

18、Count(子树1)+LeafCount(子树k); return n; ,小 结,二叉树的二叉链表存储结构、操作及先/中/后/层序遍历,int BiTreeDepth(BiTree T)/递归法求树的深度 if(T= =NULL)d=0; else d1=TreeDepth(T-lchild1);d2=TreeDepth(T-rchild); if(d1d2)d=d1+1;else d=d2+1; return d; /注意创建一个二叉树的原理、测试步骤,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchil

19、d; BiTNode, *BiTree;,6.2 二叉树,二叉树的定义、二叉链表存储(与基本操作) 二叉树的性质 二叉树的其它存储结构,6.2.2 二叉树的性质,性质1: 在二叉树的第i层上最多有2i-1个结点（i1） 性质2: 深度为K的二叉树最多有2K-1个结点（K1） 性质3: 对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。,证: 二叉树上结点总数 n = n0 + n1 + n2 二叉树上边的总数 e = n1+2n2 根结点外每个结点都有且仅有一条边(分支)”进入”,故e = n-1 由此n-1= n0 + n1 + n2 - 1 ，进

20、而 n0 = n2 + 1 。,满二叉树与完全二叉树：,满二叉树：设深度为k,含2k-1个结点的二叉树。结点数达最大,完全二叉树：设树中含n个结点, 它们和满二叉树中编号为1至n的结点位置上一一对应(编号规则为由上到下，从左到右）。相比满二叉树仅少“最后的”若干个，不能少中间的,完全二叉树特点:(1)叶子结点出现在最后2层或多或1层 (2)对于任意结点，若其右分支下的子孙的最大层次为L,则左分支下的子孙的最大层次为L或L+1,证:设完全二叉树的深度为 k 则据性质2得 2k-1 -1 2k-1 n 2k -1 2k 即 k-1 log2 n k 因为 k 只能是整数， 因此， k =log2n

21、 + 1 。,性质4:含n个结点的完全二叉树深度为 log2n +1 。,性质5:若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中编号为 i 的结点：(1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；(2) 若 2in，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子，否则，编号为2i+1 的结点为其右孩子结点。,6.2.3二叉树的存储结构顺序存储,顺序存储结构,:将二叉树映射到完全二叉树上，不存在的结点以空标记，之后用地址连续的存储单元(一维数组)依次自上而

22、下、自左而右存储完全二叉树上的各元素.(将一般二叉树以完全二叉树形式存储),最坏情况下k个结点需2k-1个单元。空间可能浪费，但适合完全二叉树的存储， 操作简单方便,6.2.3二叉树的存储结构顺序存储,顺序存储结构,用地址连续的存储单元(一维数组)依次自上而下、自左而右直接存储二叉树各元素？,存储结构与二叉树不一一对应，不能唯一确定原二叉树，故如此存储不可！,二叉树的存储结构顺序存储,顺序存储结构,:将二叉树映射到完全二叉树上，不存在的结点以空标记，之后用地址连续的存储单元(一维数组)依次自上而下、自左而右存储完全二叉树上的各元素.(将一般二叉树以完全二叉树形式存储),最坏情况下k个结点需2k

23、-1个单元。但适合完全二叉树的存储，操作简单方便,/二叉树的静态分配顺序存储结构 #define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE; /零号元素存根结点,考虑初始化及求根/左孩子/右孩子操作,二叉树的链式存储,二叉链表,三叉链表,线索链表,二叉链表,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; BiTree T;/如何判树空？,求双亲结点慢,三叉链表,typedef struct

24、TriTNode struct TriTNode *parent; TElemType data; struct TriTNode *lchild, *rchild; TriTNode, *TriTree;,求双亲结点快但空间利用率低，两者均不易扩展到普通树,6.3 遍历二叉树和线索二叉树,二叉树遍历的定义、实现和应用（已讲） 线索二叉树：概念、结构、构造、操作实现,6.3.2 线索链表,含n个结点的二叉链表中有2n0+n1=n+1个空链域,用其记录遍历过程中当前结点的前驱或后继,方案1 直观简单，但存储密度低,引：遍历二叉树时结点访问的先后顺序信息只有在遍历的动态过程中得到。若经常遍历或者要

25、求取遍历时节点的前驱、后继信息则应修改二叉链表的结构以保存该遍历顺序信息(线索),加上线索的二叉树称线索二叉树。分先序/中序/后序线索二叉树,线索二叉树的结构（中序线索二叉树）,每个节点的基础上增设两个标记位, 标记位为0(Link)代表指针存储孩子信息；标记位为1(Thread)代表指针存储线索信息，若是左指针则指向前驱，右指针则指向后继,中序:B D C A H G K F E,二叉树的线索化(人工构造),/先写出遍历序列,后添加头结点,再据序列增加线索即可,中序:B D C A H G K F E,T,增设头结点,左标记为Link,左指针指根结点,右标记为Thread,右指针指向最后被访

26、问的结点,树空则均指向头结点.又称双向线索链表,线索二叉树存储结构定义：线索链表,线索二叉树的链式存储称为线索链表,typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerTag LTag, RTag; / 指针性质Link或Thread BiThrNode, *BiThrTree;,typedef enum Link, Thread PointerTag; /指针标记类型 /Link 0 /标记为0代表为指向孩子的指针 /Thread 1 /标记为1代表为指向前驱后继的

27、线索,操作:中序遍历线索二叉链表,在线索二叉树中添加了“前驱”和“后继”的信息，可直接根据这些信息进行遍历或逆向遍历，从而提高遍历效率,算法思路：令p指向原树根, 设法让p指向树中第一个应访问的结点(只要左孩子不为空就令p指向其左孩子，即第一个左标记不为Link的结点); 访问p ; 只要p-RTag=Thread则令p=p-rchild并访问p。否则令p指向其右子树的根, 重复前述操作 直至遍历完毕(p指向头结点),void InOrderTraverse_Thr(BiThrTree T, Status (*visit) (TElemType e) p = T-lchild; / p指向根结

28、点 while (p != T) / 未遍历结束 while (p-LTag=Link) p=p-lchild; /p指向第一个待访问结点 if (!visit(p-data) return ERROR; while(p-RTag=Thread /当前结点右指针非线索, p指向其右子树根 /复杂度也为O(n)，但是没有递归，不需要栈,操作:中序线索二叉链表的构造,思路:(1) 开辟头结点并赋初值(2)遍历原二叉树, 根据其有无孩子修改标记并适时添线索信息 (3) 最后一个结点再单独处理,Status InOrderThreading(BiThrTree ,设函数InThreading(BiTh

29、rTree p,BiThrTree p-lchild=pre; else p-LTag=Link; if(pre-rchild=NULL)pre-RTag=Thread;pre-rchild=p; else pre-RTag=Link;,函数InThreading(BiThrTree p,BiThrTree int parent;/下标 PTNode;,typedef char TElemType; #define MAX_TREE_SIZE 100,typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; /根结点下标和结点个数 PTree;,如

30、何求根、给定结点的双亲及孩子结点？ 注意静态数组和动态数组的区别！,孩子表示法1多重链表,结点中为其每个孩子附设一个指针.具体定义时各结点指针的个数可取最大,也可根据各自的度不同而不同.前者同构,实现简单；后者需动态开辟指针域,实现复杂但空间省,孩子表示法2孩子(双亲)链表表示法,链式存储与顺序存储结合,将各结点存储在一个数组中,每个数组元素附加一指针域指向结点的孩子形成的链表。若经常进行访问双亲结点的操作则可向数组元素追加双亲位置域,typedef struct TElemType data; int parent; ChildPtr firstchild; CTBox;,typedef s

31、truct CTBox nodesMAX_TREE_SIZE; int n, r; CTree;,typedef struct CTNode int Child; /孩子结点的下标 struct CTNode* next;/指下一孩子 *ChildPtr;,孩子-兄弟表示法,链式存储,每个结点包括数据域和两个指针域，左指针指向第一个孩子结点，右指针指向兄弟结点.又称二叉链表存储法,typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, * CSTree;,树采用孩子兄弟表示法在

32、内存中实际形成一个二叉链表，与二叉树的二叉链表存储结构同构,但对指针含义的解释不同,1.2 森林的存储结构补充,思路:单颗树的二叉链表存储结构中根结点的右指针必为空,若要存储多颗树组成的森林，可将后一颗树的根结点看成前一颗树根结点的兄弟，即将后一颗树对应的二叉链表拼接到前一颗树根结点的右指针上，这称为森林的孩子兄弟表示法或二叉链表存储法。,typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,森林的该种表示法也形成一个二叉链表, 与树、二叉树的二叉链表存储结

33、构同构,但指针含义注意区分,2、树、森林与二叉树的转换,以二叉链表存储结构为转换依据，将左右指针所指结点理解为左右孩子结点则得到二叉树；将左指针所指结点理解为孩子,右指针所指结点理解为当前结点的兄弟则得树或森林,二叉树与森林转换举例,思考:怎样编写程序进行森林/树 与二叉树之间的相互转换？,3、树和森林的遍历-树的遍历,树采用二叉链表存储，对树进行遍历即对二叉链表进行遍历。先序遍历二叉链表（先根结点后左子树再右子树）,对应到树上是“先根,后自左到右递归遍历各子树”,称为树的先根序遍历,代码与二叉树的先序遍历基本同,将lchild与rchild换作firstchild和nextsibling即可

34、.写遍历序列也可直接根据先根规则.ABHCEFGD,H,H,树的遍历续,对二叉链表进行中序遍历(先左子树中根再右子树)对应到树上是“先从左到右各子树,后根”,称为树的后根序遍历,代码与二叉树的“中序”遍历基本同,惟lchild与rchild换作firstchild和nextsibling。也可直接根据后根规则写遍历序列。如HBEGFCDA,H,H,先序遍历二叉链表 BEFKL CG DHIJ,森林的遍历,森林采用二叉链表存储(孩子兄弟表示法),先序遍历二叉链表 (先根结点后左子树再右子树),对应到树上为“从左到右依次先根遍历各颗树”,称为森林的先序遍历,代码与二叉树的先序遍历基本同,惟定义中l

35、child与rchild换作firstchild和nextsibling。写遍历序列也可根据“先根序”规则,中序遍历二叉链表 EKLFB GC HIJD,森林采用二叉链表存储(孩子兄弟表示法),对二叉链表“先左子树中根再右子树”中序遍历,对应到森林为“从左到右依次后根遍历各颗树”,称为森林的中序遍历，代码与二叉树的中序遍历基本同,惟lchild与rchild换作firstchild和nextsibling。写遍历序列也可根据“后根序”规则,森林的遍历续,补：由树的先根和后根遍历序列确定树,方法一(间接法，借助二叉链表)：树的先根序列对应二叉链表的先序序列、后根序列对应二叉链表的中序序列，由先序

36、序列与中序序列可确定出二叉链表，再根据此二叉链表按照孩子兄弟表示法的含义可得此二叉链表对应的树 方法二(直接法，根据先根后根)：先根序列中第1个X一定是整颗树的根结点,而后根序列中唯有遍历完X的所有子树后方访问X,故X必然出现在最后；先根序列中第二个顶点必然是第一个子树的根结点，后根序列中该结点前的结点为此子树中各结点；除去第一颗子树中的结点后，先根序列中第一个结点必为第二颗子树的根结点，而后根序列中此结点前的结点构成第二颗子树，以此类推，最终可确定,先根:A B E F C D G H I J K,后根:E F B C I J K H G D A,补:由森林的先序和中序遍历序列确定森林,方法

37、一(间接法，借助二叉链表):森林的先序序列对应二叉链表的先序序列、中序序列对应二叉链表的中序序列，由先序序列与中序序列可确定出二叉链表，再根据此二叉链表按照孩子兄弟表示法的含义可得此二叉链表对应的森林 方法二(直接法，根据先根后根)：先序序列中第1个X一定是第一颗树的根结点,而中序序列中在遍历完第一颗树的最后访问X,故中序序列中X之前的结点构成森林的第一颗树，这些结点在先序和中序序列中的出现次序即为第一颗树的先根序列和后根序列，根据树的确定方法可得第一颗树；除去第一颗树的结点后，先序序列中余下的第一个结点为第二颗树的根结点，中序序列中该结点前结点的构成第二颗树,依次类推，最终可得森林,先序:

38、BEFKLCGDHIJ,中序:EKLFBGCHIJD,int TorFDepth(CSTree F) /采用二叉链表存储结构 if(!F) return 0; else h1 = TreeDepth( F-firstchild )+1; h2 = TreeDepth( F-nextsibling); ,return(max(h1, h2);,补：求树或森林的深度的算法(类似思考求叶子数),思路:树也是森林。对于森林而言，森林或者为空，或者分为两部分：第一颗树、其余树组成的子森林。求森林的深度可以递归，先递归求第一颗树的深度(子树森林深度加1),后递归求其余树所组成的森林的深度,作业:,23 给

39、出树的先根序列GFKDAIEBCHJ和后根序列DIAEKFCJHBG求树 24给出森林先序和中序序列求森林ABCDEFGHIJKL； CBEFDGAJIKLH 60设计算法统计孩子兄弟表示的树或森林的叶子结点数(提示：用递归,仿照求 森林的 深度。叶子意味着firstchild为空,注意第一棵树的叶子数如何求),6.5树与等价问题【自学】,问题：给定元素与关系，划分等价类 思路：初始每个元素一个集合，根据读入的关系进行集合的合并。基本操作包括定位元素所属集合,集合并 存储结构:用树表示集合,将属于同一集合的元素存储到一颗树中，类似双亲表示法，定位操作只需找根，集合并变为树的归并 基本操作及其实

40、现：略,电报对字符进行二进制编码,要满足解码唯一性且尽量短 等长编码：每个字符的编码长度相同。假设字符集只含有4个字符A，B，C，D，可用两位二进制数编码为00，01，10，11。 编码：若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100 译码：当接收方接收到这段电文后，将按两位一段进行译码。 特点：这种编码的特点是译码简单且具有唯一性，但编码长度不一定是最短的，此例总长度为14位,引：电报编码,不等长编码 频度高的字符分配相对较短的编码，频度较低的字符分配较长的编码。 如ABACCDA，若分别为A，B，C，D分配0，00，1，01，则上述电文编码为00001

41、1010，长度为9，但该编码无法正确解码，因为无法断定前面4个0是4个A，还是2个B，即译码不唯一。原因在于A的编码是B的前缀 前缀编码:任一字符的编码都不是另一字符编码的前缀,前缀编码的设计,0 00 1 01,0 100 101 11,A B C D,00 01 10 11,A,前缀编码对应的二叉树中,字符只能作为叶子结点出现 路径长代表字符编码长,叶子结点权值代表字符出现次数,则全文编码长度为树的带权路径长度,构造最优的前缀编码即构造最优二叉树,如赫夫曼树,字符的二进制编码可借助二叉树表示,一个字符对应一个叶结点,根到结点的路径代表相应字符的编码(向左走表0，向右走表1)。如,什么是最优

42、二叉树与赫夫曼树？ 如何构造赫夫曼树？ 赫夫曼树有何应用？ 赫夫曼树的实现及和赫夫曼编码求取,6.6 赫夫曼树及其应用,设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与对应叶子结点权值的乘积之和叫做二叉树的“带权”路径长度，记为：,1、什么是赫夫曼(Huffman)树,对于一组带有确定权植的叶子结点，带权路径长度最小的二叉树称为最优二叉树(如Huffman树),(1)WPL=1*2+3*2+5*2+5*2=28 (2)WPL=1*3+3*3+5*2+5*1=27 (3)WPL=5*3+5*3+3*2+1*1=37,2、如何构造赫夫曼树赫夫曼算法,(1)创建n个根结点,权值

43、w1,w2,.,wn, 得森林T1,T2,.,Tn； (2)在森林中选取根结点权值最小的两棵二叉树归并为新二叉树，新二叉树根结点权值为两权值之和； (3)将新二叉树加入森林，同时忽略被归并的两棵二叉树， (4)重复（2）和（3，至森林只有一棵二叉树。该二叉树就是哈夫曼树。,例如: 已知权值 W= 5, 6, 2, 9, 7 ,5,2,7,6,9,7,6,7,13,9,9,16,29,赫夫曼树不一定唯一!,WPL=2*3+3*3+4*2+5*1=28,WPL=2*2+4*2+5*2+3*2=28,Huffman树肯定最优,不是Huffman树也可能最优树,只要权值个数(叶结点数)严格大于1，Hu

44、ffman树中便不存在度为1的结点。 权值个数(叶节点数)为n则Huffman树含2n-1个结点,利用赫夫曼树设计最佳判定算法，如五级分转换 (注意此处权值与路径及树的带权路径长度的含义),3、赫夫曼树的应用-最佳判定算法,Huffman树应用-字符编码,赫夫曼树对应的编码称为赫夫曼编码,是一种最优前缀编码,例6-2 已知某系统在通讯联络中只可能出现八种字符A,B,C,D,E,F,G,H, 概率如下，设计Huffman编码 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,分别对应A-H，下面根据Huf

45、fman算法构造Huffman树,赫夫曼编码:A0110,B10,C1110,D1111,E110,F00,G0111,H010,权w=5,29,7,8,14,23,3,11,分别对应A-H,字符采用Unicode编码时,一个字符占16位,如包含100个字符的文本文档占用空间为： 100161600 位 现已知文中仅含ABCDEFGH八个字符,八个字符在文件中出现的次数分别为:5,29,7,8,14,23,3,11 如上页构造赫夫曼编码: A0110,B10,C1110,D1111,E110,F00,G0111,H010 则文件占用空间为： 542927484143232113259 位,补充赫夫曼树的应用文件压缩,4、Huffman树和Huffman编码的存储表示,存储结构:含n个字符则赫夫曼树有2n-1个结点,个数固定,编码和解码无增删，故赫夫曼树采用动态分配的顺序存储结构.构造树时从叶子结点逐步向上走,识别字符或者说解码时从根向下走，故结点要含双亲和左右孩子下标,当然还要有权值,typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode; typedef HTNode *HuffmanTree; /所有字符的Huffman编码用含n