数据结构中的树、图、查找、排序

1、数据结构数据结构树、图、查找、排序树、图、查找、排序树树: : 是是 n(n0) n(n0) 个结点的有限集合。如果个结点的有限集合。如果该集合为空，称为空树。在任意一棵非空该集合为空，称为空树。在任意一棵非空树中树中: :abcdefklghijm树的定义树的定义1)1) 有且仅有一个特定的称为有且仅有一个特定的称为根结点根结点 ( root ) ( root ) 的结点的结点; ;2) 2) 其他结点可分为若干个互其他结点可分为若干个互不相交的子集不相交的子集, ,而且每一个而且每一个子集本身又是一棵树子集本身又是一棵树, ,称为称为根的子树。根的子树。递归定义递归定义结点结点: :结点的

2、度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素数据元素+ +若干指向子树若干指向子树的分支的分支结点分支的个数结点分支的个数, ,即子树的数目即子树的数目如：如：a a的度的度-3-3；b b的度的度-2-2；k k的度的度-0-0；树中所有结点的度的最大值树中所有结点的度的最大值 如：树的度为如：树的度为3 3；度为零的结点，也称终端结点度为零的结点，也称终端结点如例：如例：k k，l l，f f，g g，m m，i i，j j为终端结点为终端结点度大于零的结点度大于零的结点如例：如例：a,b,c,d,ea,b,c,d,e基本术语基本术语612345森

3、林：森林：是是 m m（m0m0）棵互不相交的树的集合）棵互不相交的树的集合arootbefklcgdhijmf线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )7.2 7.2 二叉树二叉树 二叉树二叉树或为空树；或是由一个根结或为空树；或是由一个根结点加上两棵分别称为点加上

4、两棵分别称为左左和和右子树右子树的、的、互不交的互不交的二叉树组成。二叉树组成。abcdefghk根结点左子树右子树ef特点：特点：1 1）每个结点）每个结点最多只有两棵最多只有两棵子树；子树；2 2）两颗子树）两颗子树有左右之分，有左右之分，顺序不能换。顺序不能换。二叉树的五种基本形态：二叉树的五种基本形态：n空树空树只含根结点只含根结点nnnlrr右子树为空树右子树为空树l左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树特殊特殊的二叉树：的二叉树：满二叉树满二叉树满二叉树：满二叉树：指的是深度为指的是深度为k且含有且含有2k-1个结点的二叉树。个结点的二叉树。123456789

5、 10 11 12 13 14 151234567深度为深度为3，节点数，节点数=23-1=7深度为深度为4，节点数，节点数=24-1=15特点：特点：1）每一层上的结点数都是最大结点数；）每一层上的结点数都是最大结点数； 2）叶子结点都在最后一层。）叶子结点都在最后一层。完全二叉树：完全二叉树：树中所含的树中所含的 n 个结点和满个结点和满二叉树中编号为二叉树中编号为 1 至至 n 的结点一一对应。的结点一一对应。12345612345612345特点：特点：1）除了最下一层外其余各层都是满的；）除了最下一层外其余各层都是满的； 2）最下一层的结点都集中在该层的左侧。）最下一层的结点都集中在

6、该层的左侧。12345678 9 10特殊特殊的二叉树：的二叉树：完全二叉树完全二叉树 性质性质 1 ：满二叉树的第满二叉树的第 i 层上有层上有2i-1 个结点个结点(i1)用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 时，只有一个根结点，时，只有一个根结点， 2i-1 = 20 = 1；假设第假设第j j层有层有2 2j-1j-1结点，命题成立结点，命题成立; ;第第j层的每个结点都有层的每个结点都有2个结点，则第个结点，则第(j+1)层上的结点数层上的结点数=2*2j-1=2j=2(j+1)-1。二叉树的性质二叉树的性质1234 5 6

7、 7 性质性质 1的推论：的推论：在二叉树的第在二叉树的第 i 层上至多层上至多有有2i-1 个结点个结点 (i1)。性质性质 2 ：深度为深度为 k 的满二叉树共有的满二叉树共有 2k-1 个结个结点（点（k1）。证明：证明： 基于上一条性质，深度为基于上一条性质，深度为 k 的满二叉树上的满二叉树上的结点数为：的结点数为： 20+21+ +2k-1 = 2k-1性质性质 2的推论的推论 ：深度为深度为 k 的二叉树上最多的二叉树上最多有有 2k-1 个结点（个结点（k1） 性质性质 3 ：设二叉树叶子结点数为设二叉树叶子结点数为n0，度为度为 2 的结点数为的结点数为n2 ，则必存在关系式

8、：，则必存在关系式： n0 = n2+1。性质性质4 4：具有具有 n n 个结点的完全二叉树的个结点的完全二叉树的深深度度为为 loglog2 2n n +1+1性质性质 5 5 ：对于具有对于具有n n个结点的完全二叉树，如个结点的完全二叉树，如果按照从上到下和从左至右的顺序对二叉树果按照从上到下和从左至右的顺序对二叉树中的所有结点从中的所有结点从 1 1 至至 n n进行编号，则对于进行编号，则对于任意的序号为任意的序号为 i i 的结点，有的结点，有：(1)(1)若若 i1i1，则序号为，则序号为i i的结点的双亲结点的序的结点的双亲结点的序号为号为i/2i/2；如果；如果i=1i=1

9、，则该结点是根，无双亲，则该结点是根，无双亲; ;(2)(2) 若若 2i=n2in2in 则该结点无左孩子；则该结点无左孩子；(3)(3) 若若 2i+1=n2i+1n2i+1n，则序号为，则序号为i i的结点无右的结点无右孩子结点。孩子结点。二叉树的存储结构二叉树的存储结构二、二叉树的链式存储表示二、二叉树的链式存储表示一、一、 二叉树的顺序存储表示二叉树的顺序存储表示 用一组连续的存储单元存储二叉树的数用一组连续的存储单元存储二叉树的数据元素据元素, , 以结点存储的相对位置表示结点之以结点存储的相对位置表示结点之间的关系。间的关系。 为了正确地反映结点之间的关系为了正确地反映结点之间的

10、关系, ,任何任何二叉树都必须按照二叉树都必须按照完全二叉树完全二叉树的形式来存储的形式来存储. . 这种存储方式对某些二叉树的存储会造成存这种存储方式对某些二叉树的存储会造成存储空间的浪费。储空间的浪费。顺序存储结构顺序存储结构 在高级语言中在高级语言中, ,可以用一维数组来描述可以用一维数组来描述这种顺序存储结构。这种顺序存储结构。例如：例如：abcdfabcde完全二叉树的顺序存储完全二叉树的顺序存储存储位置存储位置123456数据元素数据元素abcdef一般二叉树的存储一般二叉树的存储存储位置存储位置123456数据元素数据元素abcdnotes:代表空元素代表空元素 #define

11、max_tree_size 100 / 二叉树的最大结点数二叉树的最大结点数telemtype sqbitreemax_tree_size; / 1号单元存储根结点号单元存储根结点例如例如: a b d c e f 1 2 3 4 5 6 7 8 9 10 11 12 13 14abcdef练习：练习：1已知一棵完全二叉树有已知一棵完全二叉树有64个叶子结点，则该树可能达个叶子结点，则该树可能达到的最大深度为（）到的最大深度为（） a7b8 c9d102若一棵二叉树有若一棵二叉树有11个叶子结点，则该二叉树中度为个叶子结点，则该二叉树中度为2的结点个数是（）的结点个数是（） a10b11 c1

12、2d不确定的不确定的3. 已知一棵二叉树的顺序存储序列为：已知一棵二叉树的顺序存储序列为：aebfcd，则：，则： 1）e的左孩子是哪个结点？右孩子是哪个结点？的左孩子是哪个结点？右孩子是哪个结点？ 2）d的双亲是哪个结点？的双亲是哪个结点？答案：答案：b答案：答案：a答案：答案：1）没有左孩子；右孩子是）没有左孩子；右孩子是f；2）b；练习：练习：3 3假设一棵二叉树的顺序存储结构如图所示，假设一棵二叉树的顺序存储结构如图所示，请回答下列问题：请回答下列问题：（1 1）哪个结点是根结点？）哪个结点是根结点？（2 2）哪些结点是叶子结点？）哪些结点是叶子结点？（3 3）哪些结点是）哪些结点是h

13、 h的祖先？的祖先？（4 4）哪些结点是）哪些结点是b b的兄弟？的兄弟？（5 5）树的深度是多少？）树的深度是多少？ a b c d e h 1 2 3 4 5 6 7 8 9 10 11 12 13 14a ad,hd,ha,c,ea,c,ec c4 4二、二叉树的链式存储表示二、二叉树的链式存储表示1. 1. 二叉链表二叉链表2三叉链表三叉链表二叉链结构二叉链结构 每个结点包含三个域每个结点包含三个域: : 数据域和左右指数据域和左右指针域针域, ,如下表所示如下表所示lchilddatarchildadebcf root二叉链表二叉链表struct btnode datatype da

14、ta; struct btnode *lchild, *rchild; typedef btnode *btree;将二叉树类型将二叉树类型btreebtree定义为指向二叉链表结点结定义为指向二叉链表结点结构的指针类型。构的指针类型。lchild data rchild结点结构结点结构:c 语言的类型描述如下语言的类型描述如下: :三叉链表三叉链表 三叉链表结构：每个结点除包含数据域和左右指三叉链表结构：每个结点除包含数据域和左右指针域外针域外, ,还包含一个指向其双亲结点的指针域。还包含一个指向其双亲结点的指针域。rootadebcf parent lchild data rchild s

15、truct tritnode / 结点结构结点结构 datatype data; struct tritnode *lchild, *rchild; / 左右孩子指针左右孩子指针 struct tritnode *parent; /双亲指针双亲指针 typedef tritnode *tritree;parent lchild data rchild结点结构结点结构:c 语言的类型描述如下语言的类型描述如下: :v 在这两种结构中在这两种结构中, ,只需要给出指向根结只需要给出指向根结点的指针点的指针, ,即可访问树中任意一个结点即可访问树中任意一个结点. .v 尽管在二叉表中无法由结点直接找

16、到其尽管在二叉表中无法由结点直接找到其双亲，但由于二叉链表的结构灵活，操作双亲，但由于二叉链表的结构灵活，操作方便，对于一般情况下的二叉树，甚至比方便，对于一般情况下的二叉树，甚至比顺序存储结构还节省空间。因此二叉链表顺序存储结构还节省空间。因此二叉链表是最常用的二叉树存储方式。是最常用的二叉树存储方式。 今后，我们所涉及到的二叉树，如不今后，我们所涉及到的二叉树，如不加特别说明均采用二叉链表存储。加特别说明均采用二叉链表存储。说明说明二叉树的遍历二叉树的遍历 遍历二叉树遍历二叉树是指按照是指按照一定的规律一定的规律对对二叉树中的二叉树中的每个结点每个结点，访问且仅访问，访问且仅访问一一次次的

17、处理过程。的处理过程。“访问访问”的含义可以很广，如：求结点的的含义可以很广，如：求结点的度、层次、输出结点的信息等等。度、层次、输出结点的信息等等。“遍历遍历”是任何类型均有的操作，是任何类型均有的操作， 1 1）对线性结构而言，只有一条搜索路）对线性结构而言，只有一条搜索路径径( (因为每个结点均只有一个后继因为每个结点均只有一个后继) )，故不，故不需要另加讨论。需要另加讨论。 2 2）而二叉树是非线性结构，）而二叉树是非线性结构，每个结点每个结点有两个后继，则存在如何遍历即按什么样有两个后继，则存在如何遍历即按什么样的的搜索路径搜索路径进行进行遍历的问题。遍历的问题。 对对“二叉树二叉

18、树”而言，而言，可以把二叉树看成由三个基可以把二叉树看成由三个基本单元组成本单元组成: : 根结点根结点(d)(d)、左子树左子树(l)(l)、右子树右子树(r),(r),并并且规定左子树上的所有结点应该在右子树上的所有结且规定左子树上的所有结点应该在右子树上的所有结点之前被访问点之前被访问, ,由此可以得到三种遍历顺序由此可以得到三种遍历顺序: :先序遍历先序遍历(dlr)(dlr)、中序遍历、中序遍历(ldr)(ldr)、后序遍历、后序遍历(lrd)(lrd)先先序的遍历算法中中序的遍历算法后后序的遍历算法遍历算法遍历算法 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，

19、（1）访问根结点；）访问根结点； （2）先序遍历左子树；）先序遍历左子树； （3）先序遍历右子树。）先序遍历右子树。先序的遍历算法：先序的遍历算法：abcdegf先序遍历：先序遍历：a b d e g c f 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则， （1）中序遍历左子树；）中序遍历左子树； （2）访问根结点；）访问根结点； （3）中序遍历右子树。）中序遍历右子树。中序的遍历算法：中序的遍历算法：abcdegf中序遍历：中序遍历：d b g e a c f 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则， （1）后序遍历左子树；）后序遍历左子树； （2）

20、后序遍历右子树；）后序遍历右子树； （3）访问根结点。）访问根结点。后序的遍历算法：后序的遍历算法：abcdegf后序遍历：后序遍历：d g e b f c aabcedgfh先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：a b d g c e h fb g d a h e c fg d b h e f c a例题例题中序遍历：中序遍历：先序遍历：先序遍历：后序遍历：后序遍历：a + b * c d e / f- + a * b c d / e fa b c d - * + e f / -例题例题+/e*bfacd( ( )根据遍历序列画二叉树根据遍历序列画二叉树 由一棵二叉树的

21、由一棵二叉树的先序序列和中序序列先序序列和中序序列或或中序和后序中序和后序能够唯一确定一棵二叉树。能够唯一确定一棵二叉树。 先序序列：先序序列：a b c d e f g h i 中序序列：中序序列：b c a e d g h f iabdecfigh练习练习已知一棵二叉树的已知一棵二叉树的先序序列和中序序列先序序列和中序序列，请，请画出该二叉树。画出该二叉树。 先序序列：先序序列：a b c d e f g h i j 中序序列：中序序列：c b e d f a h g j iabghdijcef树和森林树和森林 树的存储结构树的存储结构一、双亲表示法一、双亲表示法二、孩子链表表示法二、孩子

22、链表表示法三、树的二叉链表三、树的二叉链表( (孩子孩子- -兄弟）兄弟） 存储表示法存储表示法树的双亲表示法树的双亲表示法 以一组连续空间以一组连续空间( (数组数组) )存储树的结点存储树的结点, ,同时同时在每个结点中附设一个指示器指示其双亲结点在每个结点中附设一个指示器指示其双亲结点在数组中的位置在数组中的位置. . typedef struct datatype data; int parent; node; typedef node tree max_node_num #define max_node_num 100c c语言的类型描述语言的类型描述: :abcdefg0 a -1

23、1 b 02 c 03 d 04 e 2 5 f 26 g 5data parent孩子表示法孩子表示法 存储每个结点及其孩子信息。每个结点的所有存储每个结点及其孩子信息。每个结点的所有孩子结点形成该结点的孩子链表。孩子结点形成该结点的孩子链表。abcdefg0 a1 b 2 c 3 d 4 e 5 f 6 g 65123孩子链表孩子链表0 a1 b 2 c 3 d 4 e 5 f 6 g -1 0 0 0 2 2 46 4 5 1 2 3带双亲的孩带双亲的孩子链表子链表4孩子孩子- -兄弟表示法兄弟表示法struct treenode datatype data; struct treeno

24、de *children; struct treenode *next;typedef struct tree;c c语言的类型描述语言的类型描述: :结点结构结点结构: 每个结点除其信息域外，再增加两个分别指向每个结点除其信息域外，再增加两个分别指向该结点的该结点的第一个孩子结点第一个孩子结点和和下一个兄弟结点下一个兄弟结点的指针。的指针。childrendatanext孩子孩子- -兄弟表示法兄弟表示法树、森林与二叉树树、森林与二叉树之间的转换之间的转换 将树转换成二叉树的方法将树转换成二叉树的方法l加线：在兄弟之间加一连线加线：在兄弟之间加一连线l抹线：对每个结点，除了其左孩子外，去除其

25、与其余孩子之间的关系抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系l旋转：以树的根结点为轴心，将整树顺时针转旋转：以树的根结点为轴心，将整树顺时针转45abcdefghiabcdefghiabcdefghiabcdefghiabcdefghi树转换成的二叉树其右子树一定为空树转换成的二叉树其右子树一定为空将将二叉二叉树转换成树树转换成树l加线：若加线：若p p结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将p p的右孩子，右孩子的右孩的右孩子，右孩子的右孩子，子，沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与p p的双亲用线连起来的双亲用线连起来l抹线：抹掉原二

26、叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线l调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构abcdefghiabcdefghiabcdefghiabcdefghiabcdefghiabcdefghiabcdefghi 树的树的先序遍历先序遍历和和后序遍历后序遍历可以借用二叉可以借用二叉树的树的先序遍历先序遍历和和中序遍历中序遍历的算法来实现。的算法来实现。先序序列：先序序列：abefgcdhiabefgcdhi后序序列：后序序列：efgbchidaefgbchida先序序列：先序序列：abefgcdhiabefgcdhi中序序列：中序序列：ef

27、gbchidaefgbchida后序序列：后序序列：gfeihdcbagfeihdcba树树二叉树二叉树森林转换成二叉树森林转换成二叉树l将各棵树分别转换成二叉树将各棵树分别转换成二叉树l将每棵树的根结点用线相连将每棵树的根结点用线相连l以第一棵树根结点为二叉树的根，再以根结点为轴心，顺以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构时针旋转，构成二叉树型结构abcdefghijabcdefghijabcdefghijabcdefghij二叉树二叉树转换成森林转换成森林l抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所抹线：将二叉树中根结点与其右孩子连线，

28、及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树有右孩子间连线全部抹掉，使之变成孤立的二叉树l还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树abcdefghijabcdefghijabcdefghijabcdefghij 由此，树和森林的各种操作均可与二叉树的各种操作相对应。 应当注意的是，应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为： 左是孩子，右是兄弟左是孩子，右是兄弟 把下面的树转化成二叉树。把下面的树转化成二叉树。abcdefghi练习练习kljabcdefghijkl哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码 相关概念相关概念树的路径长度树的路径

29、长度定义为：定义为： 树中每个结点的路径长度之和。树中每个结点的路径长度之和。 结点的路径长度结点的路径长度定义为：定义为： 从根结点到该结点的路径上分支的数目。从根结点到该结点的路径上分支的数目。 树的带权路径长度树的带权路径长度定义为：定义为： 树中所有树中所有叶子结点的带权路径叶子结点的带权路径长度长度之和之和 wpl(t) = wklk (对所有叶子结点对所有叶子结点) 结点的带权路径长度结点的带权路径长度定义为：定义为： 从根结点到该结点的路径长度与结点上权从根结点到该结点的路径长度与结点上权的乘积。的乘积。设：设：a,b,c,d 的权值为：的权值为： a=7, b=5, c=2,

30、d=4;下面三棵不同的树的带权路径长度为：下面三棵不同的树的带权路径长度为： (7+5+4+2）*2=36 (7+5)*3+4*2+2=46 7+5*2+(2+4)*3=35 第第3 3棵树棵树的带权路径长度最小。的带权路径长度最小。最优二叉树最优二叉树 :设有设有n个权值个权值w1,w2,w3,.,wn,构造有构造有n个叶子结点的个叶子结点的二叉树二叉树,每个叶子结点带权为每个叶子结点带权为wi,则其中带权路径长度则其中带权路径长度wpl最小的最小的二叉树称为最优二叉树二叉树称为最优二叉树(赫夫曼树赫夫曼树).赫夫曼树的应用：判定问题。赫夫曼树的应用：判定问题。 例：将学生的百分制变成五级分

31、制：设学生的成绩分布在五例：将学生的百分制变成五级分制：设学生的成绩分布在五个等级上是不均匀的。个等级上是不均匀的。分数分数0-590-5960-6960-6970-7970-7980-8980-8990-10090-100五级分制五级分制不及格不及格及格及格中中良良优优比例比例0.050.050.150.150.40.40.30.30.10.1二、如何构造最优树二、如何构造最优树赫夫曼算法赫夫曼算法:(1)根据给定的根据给定的n个权值个权值w1,w2,w3,.,wn构成构成n棵二叉树的集棵二叉树的集合合f=t1,t2,t3,.,tn,其中每棵二叉树其中每棵二叉树ti中只有一个带权为中只有一个

32、带权为wi的根结点的根结点,其左右子树均为空其左右子树均为空.(2)在集合在集合f中选取两棵根结点权值最小的树作为左右子树中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树构造一棵新的二叉树,新二叉树的根结点的权值为其左右子新二叉树的根结点的权值为其左右子树上根结点的权值之和树上根结点的权值之和.(3)在集合在集合f中删除这两棵树中删除这两棵树,同时将新得到的二叉树加入同时将新得到的二叉树加入f中中.(4)重复步骤重复步骤(2)、(3),直到直到f中只含一棵树为止中只含一棵树为止,这棵树就是一这棵树就是一棵赫夫曼树棵赫夫曼树.9例如: 已知权值 w= 5, 6, 2, 9, 7 562

33、75276976713952795271667132900001111000111100101(1)根据给定的根据给定的n个权值个权值w1,w2,w3,.,wn构成构成n棵二叉树棵二叉树的集合的集合f=t1,t2,t3,.,tn,其中其中每棵二叉树每棵二叉树ti中只有一个带权为中只有一个带权为wi的根结点的根结点,其左右子树均为空其左右子树均为空.(2)在集合在集合f中选取两棵根结点权中选取两棵根结点权值最小的树作为左右子树构造一值最小的树作为左右子树构造一棵新的二叉树棵新的二叉树,新二叉树的根结新二叉树的根结点的权值为其左右子树上根结点点的权值为其左右子树上根结点的权值之和的权值之和.(3)

34、在集合在集合f中删除这两棵树中删除这两棵树,同时将新得到同时将新得到的二叉树加入的二叉树加入f中中.(4)重复步骤重复步骤(2)、(3),直到直到f中只含一棵树为中只含一棵树为止止,这棵树就是一棵赫夫曼树这棵树就是一棵赫夫曼树.哈夫曼编码哈夫曼编码 通信中的信息传递问题：在传递信息时，如何在能够识别的通信中的信息传递问题：在传递信息时，如何在能够识别的前提下，使传递的字符数最少。前提下，使传递的字符数最少。例：例： 电报中的报文电报中的报文 “abaccda” 四个字符的编码问题。两位编四个字符的编码问题。两位编码：码： 00 01 10 11 如果用不同长度的编码：如果用不同长度的编码： 例

35、用例用 0 1 00 01 前缀编码前缀编码:对于不等长编码对于不等长编码,若任一个字符的编码都不是另一个字若任一个字符的编码都不是另一个字符的编码的前缀符的编码的前缀,则这种编码称为前缀编码则这种编码称为前缀编码.前缀编码使得字符编码的平均长度最短前缀编码使得字符编码的平均长度最短.赫夫曼编码是一种前缀编码赫夫曼编码是一种前缀编码.赫夫曼编码的方法赫夫曼编码的方法: (1)把字符出现的频率作为权值把字符出现的频率作为权值,根据这些权值构造一棵赫夫曼根据这些权值构造一棵赫夫曼树树. (2)约定在赫夫曼树中约定在赫夫曼树中,左分支表示字符左分支表示字符0,右分支表示字符右分支表示字符1,则则从根

36、结点到叶子结点的路径上的分支字符组成的字符串即为该叶从根结点到叶子结点的路径上的分支字符组成的字符串即为该叶子结点字符的编码子结点字符的编码. 已知某系统在通信联系中只可能出现已知某系统在通信联系中只可能出现8 8种字符：种字符：abcdefghabcdefgh，其概率分别为，其概率分别为0.050.05，0.290.29， 0.07， 0.08， 0.140.14，0.23,0.030.23,0.03，0.110.11，试据此构造哈，试据此构造哈夫曼树，要求：夫曼树，要求： 1)1)画出构造哈夫曼树的过程；画出构造哈夫曼树的过程； 2)2)求每个字符的哈夫曼编码。求每个字符的哈夫曼编码。例题

37、例题哈夫曼编码：哈夫曼编码：a: 0110b: 10c: 1110d: 1111bfhagcd2311e5291437801000000111111e: 110f: 00g: 0111h: 010 设权值序列为设权值序列为8，5，3，4，7，据此构造一棵哈夫曼树。，据此构造一棵哈夫曼树。画出构造哈夫曼树过程。画出构造哈夫曼树过程。 练习练习58347习习 题题 一一1. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 a15 b16 c17 d472. 深度为5的二叉树至多有_个结点。a. 16 b. 32 c. 31 d. 103. 对一个满二叉树，m个树

38、叶，n个结点，深度为h，则_ 。a. n=h+m b. h+m=2n c. m=h-1 d. n=2 h-1答案：b c d4. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_。 a. 正确 b. 错误5. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。a. bdgcefha b. gdbecfha c. bdgaechf d. gdbehfca6. 在一非空二叉树的中序遍历序列中，根结点的右边_。 a. 只有右子树上的所有结点 b. 只有右子树上的部分结点 c. 只有左子树上的部分结点 d.

39、 只有左子树上的所有结点答案：a d a7. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论_是正确的。 a.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 b.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 c.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 d.以上都不对答案：a8. 有一棵树如图所示，回答下面的问题： 这棵树的根结点是_； 这棵树的叶子结点是_； 结点k3的度是_； 这棵树的度是_； 这棵树的深度是_； 结点k3的子女是_； 结点k3的父结点是_；k

40、1 k7k5k2k4k6k31. k1 k2,k5,k7,k4 2 3 4 k5,k6 k1 9.一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图所示，则该二叉树的链接表示形式为_ _。10. 深度为k的完全二叉树至少有_个结点。至多有_个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_。1 12 23 34 45 56 67 78 89 9 1010 1111 1212 1313 1414 1515 1616 1717 1818 1919 2020 2121e ea af fd dg gc cj jl lh hb beaefjcdlghb 2

41、k-1 、 2 k-1 、 2 k-111.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。假设一棵 二叉树的先序序列为ebadcfhgikj和中序序列为abcdefghijk。请画出该树。aaaaacccccbbbbbbebefaecdkghij图6.12 以数据集4，5，6，7，10，12，18为结点权值，画出构造huffman树的每一步图示，计算其带权路径长度为。 假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这八

42、个字母设计哈夫曼编码。623725191813121096745图6.16 huffman树习题二习题二1. 三个结点的二叉树的基本形态有 种，三个结点的树的基本形态有 种。2一棵具有64个结点的完全二叉树的高度为 。 3. 设一棵二叉树的先序遍历序列为abcdfegh，中序遍历序列为bafdcgeh，请完成下列要求： 1）画出该二叉树； 2）写出该二叉树的后序遍历序列； 3）将该二叉树转换成森林；习题习题4. 已知一棵二叉树的顺序存储结构如下图所示，图中“0”表示不存在的结点， 1）画出该二叉树； 2）求该二叉树的先序遍历序列和中序遍历序列； 3）将该二叉树转换成一棵树。5. 设字符集为a，

43、b，c，d，e，其对应的权值为7，5，2，4，9，据此构造哈夫曼树，要求： 1）画出构造哈夫曼树过程； 2）求每个字符的哈夫曼编码；a b 0 c d 0 0 e 0 f g本章复习要点本章复习要点1、树的基本概念；、树的基本概念；结点、结点的度、树的度、叶子结点、分支结点、路径、孩子、双亲、结点、结点的度、树的度、叶子结点、分支结点、路径、孩子、双亲、结点的层次、树的深度、兄弟、堂兄弟结点的层次、树的深度、兄弟、堂兄弟2、二叉树的基本概念：二叉树、满二叉树、完全二叉树；、二叉树的基本概念：二叉树、满二叉树、完全二叉树；3、二叉树的、二叉树的5个性质；个性质；4、具有、具有3个结点的二叉树的个

44、结点的二叉树的5种形态；种形态；3个结点的树的个结点的树的2种的种的形态；形态；5、理解二叉树的顺序存储结构；根据二叉树的顺序存储结构、理解二叉树的顺序存储结构；根据二叉树的顺序存储结构画二叉树；画二叉树；6、二叉树的先序、中序和后序遍历；根据先序和中序遍历的、二叉树的先序、中序和后序遍历；根据先序和中序遍历的序列画二叉树；序列画二叉树；7、构造哈夫曼树，写出哈夫曼编码；、构造哈夫曼树，写出哈夫曼编码；8、树、森林、二叉树的互相转换；、树、森林、二叉树的互相转换； 1. b 2. b 3. c 4. c 1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_。 a. 正确

45、 b. 错误 2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 a15 b16 c17 d47 3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_种。 a. 3 b. 4 c. 5 d. 6 4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_种。 a. 5 b. 6 c. 30 d. 32 5. c 7. d 8. a 5. 深度为5的二叉树至多有_个结点。 a. 16 b. 32 c. 31 d. 10 7. 对一个满二叉树，m个树叶，n个结点，深度为h，则_ 。 a. n=h+m b. h+m=2n c. m=h-1 d. n=2

46、 h-1 8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_。 a.不发生改变 b.发生改变 c.不能确定 d.以上都不对 9. c 10. a 11. d 9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_。 a. uwvts b. vwuts c. wuvts d. wutsv 10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_。 a. 正确 b. 错误 11. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。 a. bdgc

47、efha b. gdbecfha c. bdgaechf d. gdbehfca 1. a 15. b 12. 在一非空二叉树的中序遍历序列中，根结点的右边_。 a. 只有右子树上的所有结点 b. 只有右子树上的部分结点 c. 只有左子树上的部分结点 d. 只有左子树上的所有结点 15设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。 aa在b的右方ba在b的左方 ca是b的祖先da是b的子孙 16. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。 a. acbed b. decab c. deabc d. cedba 18. 如图6

48、.3所示的4棵二叉树，_不是完全二叉树。(a) (b) (c) (d) 图6.3(a) (b) (c) (d)图图6.3 第八章第八章 图图 1235687410796671231516abdce60304535804075 习习 题题1. 在一个图中，所有顶点的度数之和等于所有边数的_倍。 a. 1/2 b. 1 c. 2 d. 4 2. 任何一个无向连通图的最小生成树 。 a.只有一棵b.有一棵或多棵 c.一定有多棵d.可能不存在3. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。 a. 1/2 b. 1 c. 2 d. 4答案： c b b4. 一个有n个顶点的无向图最

49、多有_条边。 a. n b. n(n-1) c. n(n-1)/2 d. 2n5. 具有4个顶点的无向完全图有_条边。 a. 6 b. 12 c. 16 d. 206. 具有6个顶点的无向图至少应有_条边才能确保是一个连通图。 a. 5 b. 6 c. 7 d. 87. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。 a. n b. n+1 c. n-1 d. n/2caac图的存储表示图的存储表示一、一、图的数组图的数组( (邻接矩阵邻接矩阵) )存储表示存储表示二、图的邻接表存储表示二、图的邻接表存储表示图的数组图的数组( (邻接矩阵邻接矩阵) )存储表示存储表示邻接矩阵邻接

50、矩阵表示顶点间相联关系的矩阵表示顶点间相联关系的矩阵定义：定义：设设g=(v,e)是有是有 n 个顶点的图，个顶点的图，g的邻接矩的邻接矩阵阵a是如下的是如下的n阶方阵。阶方阵。aij=0 (i,j)e(g)1 (i,j)e(g)2）有向图邻接矩阵不一定）有向图邻接矩阵不一定对称；有对称；有n个顶点的有向图个顶点的有向图需存储空间为需存储空间为n3）无向图中顶点）无向图中顶点vi的度的度td(vi)是邻接矩阵是邻接矩阵a中第中第i行行元素之和元素之和4）有向图中，顶点）有向图中，顶点vi的出的出度是度是a中第中第i行元素之和顶点行元素之和顶点vi的入度是的入度是a中第中第i列元素之列元素之和和

51、图的邻接矩阵的性质图的邻接矩阵的性质1）无向图的邻接矩阵对称，可压缩存储；有）无向图的邻接矩阵对称，可压缩存储；有n个顶点的无个顶点的无向图需存储空间为向图需存储空间为n(n+1)/2 网的邻接矩阵网的邻接矩阵a ij=wij 若若 或或 （vi,vj） e(g)0 反之反之 0 0 1 0 0 30 100 0 0 5 0 0 0 0 0 0 50 0 0 a= 0 0 0 0 0 10 0 0 0 20 0 60 0 0 0 0 0 0 21435badce0111110010100011100010100edgesadjmatrix0111100000000010100000000edg

52、esadjmatrix 邻接表邻接表是图的一种链式存储结构。方法是对图中的每是图的一种链式存储结构。方法是对图中的每一个顶点建立一个依附于该顶点的边的表。而表头结点用一个顶点建立一个依附于该顶点的边的表。而表头结点用一顺序结构一顺序结构(向量）的形式存储。向量）的形式存储。dbacfe012345 a 1 4 b 0 4 5 c 3 5 d 2 5 e 0 1 f 1 2 30 1 2 3 4 5图的邻接表存储表示图的邻接表存储表示例题：例题：画出下图的邻接表画出下图的邻接表v1v2v3v4v1 v2 v3 v4 21113 4 4 24 3 在有向图的邻接在有向图的邻接表中不易找到指向该顶点

53、的弧表中不易找到指向该顶点的弧在有向图的逆在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧邻接表中，对每个顶点，链接的是指向该顶点的弧2 13 v1v2v32 1 2 v1v2v3邻接表邻接表逆邻接表逆邻接表v1v2v3有向图的邻接表有向图的邻接表有向图的逆邻接表有向图的逆邻接表例题例题画出该有向图的邻接表和画出该有向图的邻接表和逆邻接表逆邻接表bacd695280123 abcd 1 53 62 83 21 9边的结点结构边的结点结构顶点的结点结构顶点的结点结构图的遍历图的遍历 图的遍历图的遍历: 从图中某个顶点出发游历图，从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个

54、顶点访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索深度优先搜索遍历图深度优先搜索遍历图 从图中的从图中的某一个顶点某一个顶点 v0 v0 出发出发，访问此顶，访问此顶点，然后点，然后 依次从依次从 v0 v0 的的没被访问的邻接点没被访问的邻接点出发出发深度优先深度优先遍历图，直至图中所有和遍历图，直至图中所有和 v0 v0 有路径相有路径相通通的顶点都被访问到；若此时图中仍有顶点没有的顶点都被访问到；若此时图中仍有顶点没有被访问，则另选图中一个未曾访问的顶点作起始被访问，则另选图中一个未曾访问的顶点作起始点，重复

55、上述过程。点，重复上述过程。abdecgfh例例:无向图无向图12345670a- c -g -f -b -e -h -d 0 2 6 5 1 4 7 3a- b-d-h -e -c - f - g 0 1 3 7 4 2 5 6a- b -e-h -d -c - f - g 0 1 4 7 3 2 5 6深度遍历深度遍历根据图的形态做图的深度优先遍历根据图的形态做图的深度优先遍历根据图的形态可根据图的形态可以得出图的多个以得出图的多个深度优先遍历序深度优先遍历序列。列。0123acdb 1 6 7 24e 5 3 0 4 0 1 7 1fgh567 6 2 5 2 4 3abdecgfh例例

56、:无向图无向图123456700a-2c -6g -5f -1b -4e -7h -3d根据图的邻接表做深度优先遍历根据图的邻接表做深度优先遍历从顶点从顶点a出发的深度优先遍历：出发的深度优先遍历：0260147根据图的邻接根据图的邻接表得到的深度表得到的深度优先遍历序列优先遍历序列是唯一的。是唯一的。方法：从图中的某一个顶点方法：从图中的某一个顶点 v0 v0 出发，访问出发，访问v0v0之后，依次之后，依次访问访问v0 v0 的没被访问的邻接点，然后，分别从这些邻接点出的没被访问的邻接点，然后，分别从这些邻接点出发，广度优先遍历图，直至所有顶点都被访问；若此时图发，广度优先遍历图，直至所有

57、顶点都被访问；若此时图中仍有结点没有被访问，则另选图中一个未曾访问的顶点中仍有结点没有被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程。作起始点，重复上述过程。遍历结果：遍历结果： v1- v2 - v3 -v4 - v5 - v6 - v7 - v8 广度优先搜索遍历图广度优先搜索遍历图遍历结果：遍历结果： v1- v3 - v2 -v6 - v7 - v4 - v5 - v8 先访问的顶点其先访问的顶点其邻接顶点也先被邻接顶点也先被访问访问abdecgfh例例:无向图无向图123456700123acdb 1 6 7 2 4e 5 3 0 4 0 1 7 1fgh567 6 2

58、5 2 4 3从从a出发根据邻接表广度优先遍历：出发根据邻接表广度优先遍历：1a- c - b - g - f - e -h23456d -78根据图的邻接表得到的广度优先遍历序列是唯一的。根据图的邻接表得到的广度优先遍历序列是唯一的。8.4 8.4 生成树生成树 生成树生成树v定义：所有顶点均由边连接在一起，但不存在回路的图叫定义：所有顶点均由边连接在一起，但不存在回路的图叫生成树生成树深度优先生成树与广度优先生成树深度优先生成树与广度优先生成树v说明说明l一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树l所有生成树具有以下共同特点：所有生成树具有以下共同特点：u生成树的顶点个数

59、与图的顶点个数相同生成树的顶点个数与图的顶点个数相同u生成树是图的极小连通子图生成树是图的极小连通子图u一个有一个有n n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1n-1条边条边u生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的u在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路l含含n n个顶点个顶点n-1n-1条边的图不一定是生成树条边的图不一定是生成树ghkiv1v2v4v5v3v7v6v8例例深度遍历：深度遍历：v1 v2 v4 v8 v5 v3 v6 v7v1v2v4v5v3v7v6v8深度优先生成树v1v2v4v5v3v7v6v8广

60、度优先生成树v1v2v4v5v3v7v6v8v1v2v4v5v3v7v6v8广度遍历：广度遍历：v1 v2 v3 v4 v5 v6 v7 v8 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的如何在最节省经费的前提下建立前提下建立这个通讯网通讯网？问题：问题： 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）该问题等价于：该问题等价于：算法一：（普里姆算法）算法一：（普里姆算法）abcdegf195141827168213127aedcb