数据结构导论第4章.ppt

复习前节;第4章 树;本章项目： 电文编码;;网络信息传输：;本章项目：电文编码问题 涉及知识点： 1、树的概念 2、树的专业术语 3、二叉树的概念 4、哈夫曼树和哈夫曼编码;自然中的树;旋转后;适当进行调整;数据结构中树的形态，具有分层特点;某姓氏族谱;;树描述的是一种层次结构， 是一种一对多的逻辑关系;树(Tree)是n(n=0)个结点的有限集。n=0时称为空树。 n1时， 有且仅有一个称为根的结点； 其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又是一棵树，称为子树;树 的 其 他 表 示 形 式;结点：数据元素的内容及其指向其子树根的分支 结点的度：结点拥有的子树的数目。 树的度：树内各结点的度的最大值；;叶子（终端结点），非终端结点：度为0的结点称为叶子结点；度不为0的结点称为非终端结点。;结点的层数：树中根结点的层次为1，根结点子树的根为第2层，以此类推。 树的高度（深度）：树中所有结点层次的最大值;孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；双亲在同一层的结点互为堂兄弟。;路径：若树中存在一个序列k1，k2…kn，使得ki是ki+1的双亲，则称该结点序列为k1到kn的一条路径。 路径长度：这些节点经过的边的条数;子孙，祖先：以某结点为根的子树中的所有结点都被称为是该结点的子孙。从根结点到该结点路径上的所有结点称为该结点的祖先。;森林：多棵互不相交的树的集合构成森林;结点 结点的度(Degree) 叶子（Leaf)或终端结点 分支结点或非终端结点 树的度 层次(Level) 树的深度(Depth) 孩子（child) 双亲（Parent) 兄弟(Sibling) 祖先 子孙 路径;知识点3： 二叉树的概念;特征： 每个结点最多只有两棵子树 子树有左右之分，次序不能任意颠倒，只有一棵子树时也必须分清是左子树还是右子树;网络信息传输：;项目实现的进一步分析： 项目核心问题： 如何将电报文字转换成01编码 扩展问题： 电文传送时的高效性;扩展问题： 电文传送时的高效性;实际情况：字符在实际使用中出现频率不一样！;假定： 某电文通信中只由ABCD四个字符构成 且出现频率分别为：;此种编码方式为不等长编码， 采用不等长编码可缩短电文编码长度， 从而提高电文传送效率;假定：;新知识： 设计不等长编码时，必须做到：任何一个字符的编码 不能是另一个字符编码的前缀，这种编码为前缀码;知识点4： 哈夫曼树与哈夫曼编码;知识点4： 哈夫曼树与哈夫曼编码;树的带权路径长度： 树中所有叶子结点的带权的路径长度的和。 通常记为：WPL(Weighted Path Length)。 ;树的带权路径长度： 树中所有叶子结点的带权的路径长度的和。 通常记为：WPL(Weighted Path Length)。 由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（ Huffman）树。;a;1、根据给定的n个权值{w1,w2,…,wn}，构造n棵只有根结点的二叉树，令其权值为wj ; 2、在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和; 3、从森林中删除这两棵树，同时将新得到的二叉树加入森林中; 4、重复上述两步，直到森林中只含一棵树为止，这棵树即哈夫曼树 。;9;9;9;9;9;9;9;设计电文编码时， 随意的不等长编码可能导致编码翻译时出现歧义 使用前缀码，可解决不等长编码出现的歧义 利用哈夫曼树可构造前缀码;假定： 某电文通信中只由ABCD四个字符构成 且出现频率分别为：;假定： 某电文通信中只由ABCD四个字符构成 且出现频率分别为：;假定： 某电文通信中只由ABCD四个字符构成 且出现频率分别为：;假定： 某电文通信中只由ABCD四个字符构成 且出现频率分别为：;项目完成，总结：;n(n0)个结点的树的高度: 最低是多少？最高是多少？ ;答案：√;1、哈夫曼树只有度为0和2的结点，无度为1的结点； 2、n个叶子的哈夫曼树的形态一般不唯一，但WPL是相同的； 3、n个叶子的哈夫曼树共有2n-1个结点。;0.1;2009年10月考题： 27、由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。 ;4.2 二叉树;特征： 每个结点最多只有两棵子树 子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清是左、右子树。;二叉树的五种形态;（1）初始化 IN