算法大视界课件-爱的密码

第七章第七章 爱的密码爱的密码 主要内容：主要内容：7.1 7.1 如何传输如何传输“I LOVE YOUI LOVE YOU”7.2 7.2 树及二叉树树及二叉树7.3 7.3 哈夫曼树及编码哈夫曼树及编码7.4 7.4 应用：农夫锯木板问题应用：农夫锯木板问题7.5 7.5 总结与思考总结与思考附录附录7.1 7.1 如何传输如何传输“I LOVE YOUI LOVE YOU”7.1.1 7.1.1 问题描述问题描述 要在两个终端之间传输文字要在两个终端之间传输文字“I LOVE YOUI LOVE YOU”，要求：，要求：（1 1）传输的文字编码总长度尽可能短；）传输的文字编码总长度尽可能短；（2 2）任何一个字符的编码都不是同一字符集中另一个字符的编码）任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。的前缀。7.1.2 7.1.2 问题分析问题分析1 1、在传送电文时，希望总长度尽可能短。如果对每个字符设计、在传送电文时，希望总长度尽可能短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长度便可减少。编码，则传送电文的总长度便可减少。2 2、采用、采用前缀编码。即前缀编码。即任何一个字符的编码都不是同一字符集中任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。另一个字符的编码的前缀。如何实现上述要求？如何实现上述要求？利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。7.2.1 7.2.1 树的定义树的定义7.2 7.2 树及二叉树树及二叉树 树（树（TreeTree）是）是n n（n=0n=0）个结点的有限集。在任意一棵非空树）个结点的有限集。在任意一棵非空树中中:1:1）有且仅有一个特定的称为根（）有且仅有一个特定的称为根（RootRoot）的结点；）的结点；2 2）当）当n1n1时，时，其余结点可分为其余结点可分为m m（m0m0）个互不相交的有限集）个互不相交的有限集T T1 1，T T2 2，T Tm m，其，其中每一个集合本身又是一棵树，并且称为根的子树。中每一个集合本身又是一棵树，并且称为根的子树。其抽象数据类型定义如下：其抽象数据类型定义如下：ADT TreeADT Tree 数据对象数据对象 D D：D D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系 R R：若：若D D为空集，则称为空树为空集，则称为空树 。若。若D D仅含一个数据元素，仅含一个数据元素，则则R R为为空集空集,树只有一个根节点；否则树只有一个根节点；否则R=HR=H，H H是如下二元关系是如下二元关系:(1)(1)在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素rootroot；它在；它在H H下无前驱下无前驱 (2)(2)若若D-rootD-root，则存在，则存在D-rootD-root的一个划分的一个划分D D1 1,D,D2 2,D,Dm m（m0)m0)，对任意，对任意j kj k，有，有D Dj j D Dk k=,且对任意的且对任意的i i，唯一存在数据元素，唯一存在数据元素x xi iD Di i,有有root,x H;H;(3)(3)对应于对应于D-rootD-root的划分，的划分，H-root,xH-，root,x 有惟一的一有惟一的一个划分个划分H H1 1,H,Hm m(m0)(m0)，对任意，对任意j kj k，有，有H Hj j H Hk k=,且对任意的且对任意的i i，H Hi i是是D Di i上的关系，（上的关系，（D Di i,H,Hi i)是一棵符合本定义的树，称为根是一棵符合本定义的树，称为根rootroot的子树。的子树。主要操作：主要操作：InitTree(&T)/InitTree(&T)/初始化置空树初始化置空树 Root(T)/Root(T)/求树的根结点求树的根结点 Value(T,cur_e)/Value(T,cur_e)/求当前结点的元素值求当前结点的元素值 Parent(T,cur_e)/Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点 TreeEmpty(T)/TreeEmpty(T)/判定树是否为空树判定树是否为空树 TreeDepth(T)/TreeDepth(T)/求树的深度求树的深度 TraverseTree(T,Visit()/TraverseTree(T,Visit()/遍历遍历 ClearTree(&T)/ClearTree(&T)/将树清空将树清空A AC CG GD DH HI IJ JM MB BE EF FK KL LA(A(B(E,F(K,L),B(E,F(K,L),C(G),C(G),D(H,I,J(M)D(H,I,J(M)T T1 1T T3 3T T2 2树根树根例如例如:在日常工作和学习中也有很多树的应用例子。例如在日常工作和学习中也有很多树的应用例子。例如WindowsWindows的的树形文件结构就是一个典型的树型结构。树形文件结构就是一个典型的树型结构。例如，有文件结构如下图示：例如，有文件结构如下图示：工作工作计划计划我的我的文档文档数据数据库库算法大算法大视界视界第一第一章章第二第二章章第三第三章章参考参考文献文献 图中，圆圈代表文件夹，图中，圆圈代表文件夹，方框代表文件。整个文件结构方框代表文件。整个文件结构就是一个树的结构。就是一个树的结构。基本术语：基本术语：结点的度结点的度:结点拥有的子树的数目结点拥有的子树的数目 树的度树的度:树中所有结点的度的最大值树中所有结点的度的最大值 叶子结点叶子结点:度为零的结点度为零的结点 分支结点分支结点:度不为零的结点度不为零的结点 结点的层次结点的层次:假设根结点的层次为假设根结点的层次为1 1，根的孩子为第二层。第，根的孩子为第二层。第L L层层的结点的子树根结点的层次为的结点的子树根结点的层次为L+1L+1 树的深度树的深度(高度高度)：树中叶子结点所在的最大层次：树中叶子结点所在的最大层次 森林森林：是：是m m（m0m0）棵互不相交的树的集合）棵互不相交的树的集合7.2.1 7.2.1 二叉树二叉树一、基本概念一、基本概念 二叉树或为空树，或是由一个根结点加上两棵分别称为二叉树或为空树，或是由一个根结点加上两棵分别称为左子树左子树和和右子树右子树的、的、互不互不相相交的交的二叉树组成。二叉树组成。ABCDEGFHK根结点根结点左子树左子树右子树右子树ADT BinaryTreeADT BinaryTree数据对象数据对象 D D：D D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系 R R：若若D=D=，则，则R=R=，称，称BinaryTreeBinaryTree为空二叉树为空二叉树 。否则，。否则，R=HR=H，H H是如下二元关系是如下二元关系:(1)(1)在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素rootroot；它在；它在H H下无前驱下无前驱 (2)(2)若若D-root D-root，则存在，则存在D-root=DD-root=Dl l,D,Dr r,且且D Dl l D Dr r=;(3)(3)若若D Dl l ，则，则D Dl l中存在惟一的元素中存在惟一的元素x xl l,root,x,HH，且存在，且存在D Dl l上的关上的关系系H Hl lH H；若；若D Dr r ，则，则D Dr r中存在惟一的元素中存在惟一的元素x xr r，root,xHH，且存在，且存在D Dr r上上的关系的关系H Hr rH H；H=root,xH=,H,Hl l,H,Hr r ；（4 4）(D(Dl l,H,Hl l)是一棵符合本定义的二叉树，称为根的是一棵符合本定义的二叉树，称为根的左子树左子树，(D(Dr r,H,Hr r)是是一棵符合本定义的二叉树，称为根的一棵符合本定义的二叉树，称为根的右子树右子树，二叉树的五种基本形态二叉树的五种基本形态：空树空树N N只含根结点只含根结点N NL L右子树为空树右子树为空树N NR R左子树为空树左子树为空树N NR RL L左右子树均不左右子树均不为空树为空树InitBiTree(&T);InitBiTree(&T);初始化置空二叉树初始化置空二叉树Root(T);Root(T);求二叉树的根结点求二叉树的根结点 Parent(T,e);Parent(T,e);求当前结点的双亲结点求当前结点的双亲结点BiTreeEmpty(T);BiTreeEmpty(T);判定二叉树是否为空树判定二叉树是否为空树 BiTreeDepth(T);BiTreeDepth(T);求二叉树的深度求二叉树的深度PreOrderTraverse(T,Visit();PreOrderTraverse(T,Visit();前序遍历二叉树前序遍历二叉树InOrderTraverse(T,Visit();InOrderTraverse(T,Visit();中序遍历二叉树中序遍历二叉树PostOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();后序遍历二叉树后序遍历二叉树 二叉树的主要基本操作：二叉树的主要基本操作：性质性质 1 1：在二叉树的第在二叉树的第 i i 层上至多有层上至多有2 2i-1 i-1 个结点个结点 (i1)(i1)。二、二、二叉树的性质二叉树的性质性质性质 2 2：深度为深度为 k k 的二叉树上至多含的二叉树上至多含 2 2k k-1-1 个结点（个结点（k1k1）。）。性质性质 3 3：对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n n0 0 个叶子结点、个叶子结点、n n2 2 个度为个度为 2 2 的结点，则必存在关系式：的结点，则必存在关系式：n n0 0=n=n2 2+1+1。两类特殊的二叉树：两类特殊的二叉树：满二叉树：满二叉树：指的是深度为指的是深度为k k且含有且含有2 2k k-1-1个结点的二叉树。个结点的二叉树。完全二叉树：完全二叉树：树中所含的树中所含的 n n 个结点和满二叉树中编号为个结点和满二叉树中编号为 1 1 至至 n n 的结点一一对应。的结点一一对应。1 12 23 34 45 56 67 78 89 91010111112121313141415151 12 23 34 45 56 67 78 89 91010性质性质 4 4：具有具有 n n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2n n+1+1。性质性质 5 5：若对含若对含 n n 个结点的完全二叉树从上到下且从左至右进行个结点的完全二叉树从上到下且从左至右进行 1 1至至n n 的编号，则对完全二叉树中任意一个编号为的编号，则对完全二叉树中任意一个编号为i i 的结点：的结点：(1)(1)若若 i=1i=1，则该结点是二叉树的根，无双亲，否则，编号为，则该结点是二叉树的根，无双亲，否则，编号为 i/2i/2 的结点为其双亲结点；的结点为其双亲结点；(2)(2)若若 2in2in，则该结点无左孩子，否则，编号为，则该结点无左孩子，否则，编号为 2i 2i 的结点的结点为其左孩子结点；为其左孩子结点；(3)(3)若若 2i+1n2i+1n，则该结点无右孩子结点，否则，编号为，则该结点无右孩子结点，否则，编号为2i+1 2i+1 的结点为其右孩子结点。的结点为其右孩子结点。A AD DE EB BC CF F rootrootlchild data rchildlchild data rchil