数据结构中的树图查找排序实用教案

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

2、定义第1页/共212页第一页，共212页。结点结点(ji din):(ji din):结点结点(ji din)(ji din)的度的度: :树的度树的度: :叶子叶子(y zi)(y zi)结点结点: :分支结点分支结点: :数据元素数据元素+ +若干指向子树的若干指向子树的分支分支结点分支的个数结点分支的个数, ,即子树的数目即子树的数目如：如：A A的度的度-3-3；B B的度的度-2-2；K K的度的度-0-0；树中所有结点的度的最大值树中所有结点的度的最大值 如：树的度为如：树的度为3 3；度为零的结点，也称终端结点度为零的结点，也称终端结点如例：如例：K K，L L，F F，G G，

3、M M，I I，J J为终端结点为终端结点度大于零的结点度大于零的结点如例：如例：A,B,C,D,EA,B,C,D,E基本术语基本术语612345第2页/共212页第二页，共212页。森林：是森林：是 m m（m0m0）棵互不相交）棵互不相交(xingjio)(xingjio)的树的集合的树的集合ArootBEFKLCGDHIJMF第3页/共212页第三页，共212页。线性结构线性结构(jigu)树型结构树型结构(jigu)第一个数据元素第一个数据元素(yun s)(yun s) ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)

4、多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )第4页/共212页第四页，共212页。7.2 7.2 二叉树二叉树第5页/共212页第五页，共212页。 二叉树或为空树；或是由一个二叉树或为空树；或是由一个(y )根结点加上两棵分别称为左和右根结点加上两棵分别称为左和右子树的、互不交的二叉树组成。子树的、互不交的二叉树组成。ABCDEFGHK根结点(ji din)左子树右子树EF特点：特点：1 1）每个结点）每个结点最多只有两最多只有两棵子树；棵

5、子树；2 2）两颗子树）两颗子树有左右有左右(zuyu)(zuyu)之分，顺序之分，顺序不能换。不能换。第6页/共212页第六页，共212页。二叉树的五种二叉树的五种(w zhn)基本形态：基本形态：N空树空树只含根结点只含根结点(ji din)NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右左右(zuyu)子树子树均不为均不为空树空树第7页/共212页第七页，共212页。特殊特殊(tsh)的二叉树：满二叉树的二叉树：满二叉树满二叉树：指的是深度满二叉树：指的是深度(shnd)为为k且含且含有有2k-1个结点的二叉树。个结点的二叉树。123456789 10 11 12 13

6、 14 151234567深度深度(shnd)为为3，节点数，节点数=23-1=7深度为深度为4，节点数，节点数=24-1=15特点：特点：1）每一层上的结点数都是最大结点数；）每一层上的结点数都是最大结点数； 2）叶子结点都在最后一层。）叶子结点都在最后一层。第8页/共212页第八页，共212页。完全二叉树：树中所含的完全二叉树：树中所含的 n 个结点个结点(ji din)和满二叉树中编号为和满二叉树中编号为 1 至至 n 的结点的结点(ji din)一一对应。一一对应。12345612345612345特点：特点：1）除了最下一层外其余）除了最下一层外其余(qy)各层都是各层都是满的；满的

7、； 2）最下一层的结点都集中在该层的左侧。）最下一层的结点都集中在该层的左侧。12345678 9 10特殊特殊(tsh)的二叉树：完全二叉树的二叉树：完全二叉树第9页/共212页第九页，共212页。 性质性质(xngzh) 1 ：满二叉树的第：满二叉树的第 i 层上有层上有2i-1 个结点个结点(i1)用归纳法证明用归纳法证明(zhngmng)： 归纳基：归纳基： 归纳假设：归纳假设： 归纳证明归纳证明(zhngmng)：i = 1 时，只有一个(y )根结点， 2i-1 = 20 = 1；假设第假设第j j层有层有2 2j-1j-1结点，命题成立结点，命题成立; ;第第j层的每个结点都有层

8、的每个结点都有2个结点，则第个结点，则第(j+1)层上的结点数层上的结点数=2*2j-1=2j=2(j+1)-1。二叉树的性质二叉树的性质1234 5 6 7第10页/共212页第十页，共212页。 性质性质(xngzh) 1的推论：在二叉树的第的推论：在二叉树的第 i 层上至多有层上至多有2i-1 个个结点结点 (i1)。第11页/共212页第十一页，共212页。性质性质 2 ：深度为：深度为 k 的满二叉树共有的满二叉树共有(n yu) 2k-1 个结点（个结点（k1）。）。证明证明(zhngmng)： 基于上一条性质基于上一条性质(xngzh)，深度为，深度为 k 的满的满二叉树上的结点

9、数为：二叉树上的结点数为： 20+21+ +2k-1 = 2k-1性质性质 2的推论的推论 ：深度为深度为 k 的二叉树上最多的二叉树上最多有有 2k-1 个结点（个结点（k1）第12页/共212页第十二页，共212页。 性质性质 3 ：设二叉树叶子：设二叉树叶子(y zi)结点数为结点数为n0，度为度为 2 的结点数为的结点数为n2 ，则必存在关系式：，则必存在关系式： n0 = n2+1。性质性质(xngzh)4(xngzh)4：具有：具有 n n 个结点的完全二个结点的完全二叉树的深度为叉树的深度为 log2nlog2n +1 +1第13页/共212页第十三页，共212页。性质性质 5

10、5 ：对于具有：对于具有n n个结点的完全二叉树，如果个结点的完全二叉树，如果按照按照(nzho)(nzho)从上到下和从左至右的顺序对从上到下和从左至右的顺序对二叉树中的所有结点从二叉树中的所有结点从 1 1 至至 n n进行编号，则对进行编号，则对于任意的序号为于任意的序号为 i i 的结点，有：的结点，有：若若 i1 i1，则序号为，则序号为i i的结点的双亲结点的序号为的结点的双亲结点的序号为i/2i/2；如果；如果i=1i=1，则该结点是根，无双亲，则该结点是根，无双亲; ; 若若 2i=n 2in 2in 则该结点无左孩子；则该结点无左孩子； 若若 2i+1=n 2i+1n2i+1

11、n，则序号为，则序号为i i的结点无右孩子的结点无右孩子结点。结点。第14页/共212页第十四页，共212页。二叉树的存储二叉树的存储(cn ch)结构结构二、二叉树的链式存储二、二叉树的链式存储(cn (cn ch)ch)表示表示一、一、 二叉树的顺序存储表示二叉树的顺序存储表示(biosh)第15页/共212页第十五页，共212页。 用一组连续的存储单元存储二叉树的数据用一组连续的存储单元存储二叉树的数据元素元素, , 以结点存储的相对位置表示结点之间的以结点存储的相对位置表示结点之间的关系关系(gun x)(gun x)。 为了正确地反映结点之间的关系为了正确地反映结点之间的关系(gun

12、 (gun x),x),任何二叉树都必须按照完全二叉树的形任何二叉树都必须按照完全二叉树的形式来存储式来存储. . 这种存储方式对某些二叉树的存储这种存储方式对某些二叉树的存储会造成存储空间的浪费。会造成存储空间的浪费。顺序存储结构顺序存储结构(jigu)第16页/共212页第十六页，共212页。 在高级语言中在高级语言中, ,可以可以(ky)(ky)用一维数组用一维数组来描述这种顺序存储结构。来描述这种顺序存储结构。例如：例如：ABCDFABCDE完全(wnqun)二叉树的顺序存储存储位置123456数据元素ABCDEF一般(ybn)二叉树的存储存储位置123456数据元素ABCDNOTES

13、:代表空元素 第17页/共212页第十七页，共212页。#define MAX_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数TElemType SqBiTreeMAX_TREE_SIZE; / 1号单元号单元(dnyun)存储根结点存储根结点例如例如(lr): A B D C E F 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEF第18页/共212页第十八页，共212页。练习练习(linx)(linx)：1已知一棵完全二叉树有已知一棵完全二叉树有64个叶子结点，则该树可能达个叶子结点，则该树可能达到的最大深度为（）到的最大深度为（） A7B

14、8 C9D102若一棵二叉树有若一棵二叉树有11个叶子结点，则该二叉树中度为个叶子结点，则该二叉树中度为2的结点个数是（）的结点个数是（） A10B11 C12D不确定的不确定的已知一棵二叉树的顺序存储序列为：已知一棵二叉树的顺序存储序列为：aebfcd，则：，则： 1）e的左孩子的左孩子(hi zi)是哪个结点？右孩子是哪个结点？右孩子(hi zi)是哪是哪个结点？个结点？ 2）d的双亲是哪个结点？的双亲是哪个结点？答案：B答案：A答案：1）没有(mi yu)左孩子；右孩子是f；2）b；第19页/共212页第十九页，共212页。练习练习(linx)(linx)：3 3假设一棵二叉树的顺序存储

15、结构如图所示，请假设一棵二叉树的顺序存储结构如图所示，请回答下列问题：回答下列问题：（1 1）哪个结点是根结点？）哪个结点是根结点？（2 2）哪些结点是叶子结点？）哪些结点是叶子结点？（3 3）哪些结点是）哪些结点是H H的祖先？的祖先？（4 4）哪些结点是）哪些结点是B B的兄弟的兄弟(xingd)(xingd)？（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第20页/共212页第二十页，共212页。二、二叉树的链式存储二、二叉树的链式存储(cn ch)(

16、cn ch)表示表示1. 1. 二叉链表二叉链表2三叉链表三叉链表第21页/共212页第二十一页，共212页。二叉链结构二叉链结构 每个结点包含三个域每个结点包含三个域: : 数据域和左右指针数据域和左右指针(zhzhn)(zhzhn)域域, ,如下表所示如下表所示lchilddatarchildADEBCF root二叉链表二叉链表第22页/共212页第二十二页，共212页。struct BTNode datatype data; struct BTNode *lchild, *rchild; Typedef BTNode *BTree;将二叉树类型BTree定义为指向二叉链表结点(ji d

17、in)结构的指针类型。lchild data rchild结点结点(ji din)结构结构:C 语言的类型(lixng)描述如下:第23页/共212页第二十三页，共212页。三叉链表三叉链表 三叉链表结构：每个结点除包含数据域和左右指三叉链表结构：每个结点除包含数据域和左右指针域外针域外,还包含一个指向还包含一个指向(zh xin)其双亲结点的指其双亲结点的指针域。针域。rootADEBCF parent lchild data rchild第24页/共212页第二十四页，共212页。 struct TriTNode / 结点结构 datatype data; struct TriTNode

18、*lchild, *rchild; / 左右孩子(hi zi)指针 struct TriTNode *parent; /双亲指针 typedef TriTNode *TriTree;parent lchild data rchild结点结点(ji din)结构结构:C 语言的类型描述(mio sh)如下:第25页/共212页第二十五页，共212页。v 在这两种结构中在这两种结构中, ,只需要给出指向根结点只需要给出指向根结点的指针的指针, ,即可访问即可访问(fngwn)(fngwn)树中任意一个树中任意一个结点结点. .v 尽管在二叉表中无法由结点直接找到其双尽管在二叉表中无法由结点直接找到

19、其双亲，但由于二叉链表的结构灵活，操作方便，亲，但由于二叉链表的结构灵活，操作方便，对于一般情况下的二叉树，甚至比顺序存储对于一般情况下的二叉树，甚至比顺序存储结构还节省空间。因此二叉链表是最常用的结构还节省空间。因此二叉链表是最常用的二叉树存储方式。二叉树存储方式。v 今后，我们今后，我们(w men)(w men)所涉及到的二叉所涉及到的二叉树，如不加特别说明均采用二叉链表存储。树，如不加特别说明均采用二叉链表存储。说明说明(shumng)第26页/共212页第二十六页，共212页。二叉树的遍历二叉树的遍历(bin l)第27页/共212页第二十七页，共212页。 遍历二叉树是指按照一定遍

20、历二叉树是指按照一定(ydng)(ydng)的规律对二叉树中的每个结的规律对二叉树中的每个结点，访问且仅访问一次的处理过程。点，访问且仅访问一次的处理过程。“访问访问”的含义可以很广，如：求结点的度、的含义可以很广，如：求结点的度、层次、输出结点的信息层次、输出结点的信息(xnx)等等。等等。第28页/共212页第二十八页，共212页。“遍历遍历”是任何类型均有的操作，是任何类型均有的操作， 1）对线性结构而言，只有一条搜索路径）对线性结构而言，只有一条搜索路径(因为因为每个结点均只有一个后继每个结点均只有一个后继)，故不需要另加讨论。，故不需要另加讨论。 2）而二叉树是非线性结构，每个结点有

21、两个）而二叉树是非线性结构，每个结点有两个后继，则存在后继，则存在(cnzi)如何遍历即按什么样的搜如何遍历即按什么样的搜索路径进行遍历的问题。索路径进行遍历的问题。 第29页/共212页第二十九页，共212页。 对对“二叉树二叉树”而言，可以把二叉树看成由三个基而言，可以把二叉树看成由三个基本单元组成本单元组成: 根结点根结点(D)、左子树、左子树(L)、右子树、右子树(R),并且并且规定左子树上的所有结点应该在右子树上的所有结点规定左子树上的所有结点应该在右子树上的所有结点之前之前(zhqin)被访问被访问,由此可以得到三种遍历顺序由此可以得到三种遍历顺序:先先序遍历序遍历(DLR)、中序

22、遍历、中序遍历(LDR)、后序遍历、后序遍历(LRD)先序的遍历先序的遍历(bin l)算法算法中序的遍历中序的遍历(bin l)算法算法后后序的遍历算法遍历算法遍历算法第30页/共212页第三十页，共212页。 若二叉树为空树，则空操作；否则若二叉树为空树，则空操作；否则(fuz)， （1）访问根结点；）访问根结点； （2）先序遍历左子树；）先序遍历左子树； （3）先序遍历右子树。）先序遍历右子树。先序的遍历先序的遍历(bin l)算法：算法：ABCDEGF先序遍历(bin l)：A B D E G C F第31页/共212页第三十一页，共212页。 若二叉树为空树，则空操作；否则，若二叉树

23、为空树，则空操作；否则， （1）中序遍历左子树；）中序遍历左子树； （2）访问）访问(fngwn)根结点；根结点； （3）中序遍历右子树。）中序遍历右子树。中序的遍历中序的遍历(bin l)算法：算法：ABCDEGF中序遍历(bin l)：D B G E A C F第32页/共212页第三十二页，共212页。 若二叉树为空树，则空操作若二叉树为空树，则空操作(cozu)；否则，；否则， （1）后序遍历左子树；）后序遍历左子树； （2）后序遍历右子树；）后序遍历右子树； （3）访问根结点。）访问根结点。后序的遍历后序的遍历(bin l)算法：算法：ABCDEGF后序(hu x)遍历：D G E

24、B F C A第33页/共212页第三十三页，共212页。ABCEDGFH先序遍历(bin l)：中序遍历(bin l)：后序(hu x)遍历：A B D G C E H FB G D A H E C FG D B H E F C A例题例题第34页/共212页第三十四页，共212页。中序遍历(bin l)：先序遍历(bin l)：后序(hu x)遍历：a + b * c d e / f- + a * b c d / e fa b c d - * + e f / -例题例题+/e*bfacd( ( )第35页/共212页第三十五页，共212页。根据根据(gnj)遍历序列画遍历序列画二叉树二叉树

25、 由一棵二叉树的先序序列和中序序列或中由一棵二叉树的先序序列和中序序列或中序和后序能够唯一序和后序能够唯一(wi y)确定一棵二叉树。确定一棵二叉树。 先序序列先序序列(xli)：A B C D E F G H I 中序序列中序序列(xli)：B C A E D G H F IABDECFIGH第36页/共212页第三十六页，共212页。练习练习(linx)已知一棵二叉树的先序序列已知一棵二叉树的先序序列(xli)和中序序列和中序序列(xli)，请画出该二叉树。，请画出该二叉树。 先序序列先序序列(xli)：A B C D E F G H I J 中序序列中序序列(xli)：C B E D F

26、 A H G J IABGHDIJCEF第37页/共212页第三十七页，共212页。树和森林树和森林(snln) (snln) 第38页/共212页第三十八页，共212页。树的存储树的存储(cn ch)结构结构一、双亲一、双亲(shungqn)(shungqn)表表示法示法二、孩子二、孩子(hi zi)(hi zi)链表链表表示法表示法三、树的二叉链表三、树的二叉链表( (孩子孩子- -兄弟）兄弟） 存储表示法存储表示法第39页/共212页第三十九页，共212页。树的双亲树的双亲(shungqn)(shungqn)表示法表示法 以一组连续空间以一组连续空间( (数组数组) )存储树的结点存储树

27、的结点, ,同时在每同时在每个结点中附设一个指示器指示其双亲个结点中附设一个指示器指示其双亲(shungqn)(shungqn)结点在数组中的位置结点在数组中的位置. . typedef struct datatype data; int parent; Node; typedef Node Tree MAX_NODE_NUM #define MAX_NODE_NUM 100C C语言的类型语言的类型(lixng)(lixng)描述描述: :ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent第40页/共212页第四十页，共212页。孩

28、子孩子(hi zi)表示法表示法 存储每个结点及其孩子信息存储每个结点及其孩子信息(xnx)(xnx)。每个结点。每个结点的所有孩子结点形成该结点的孩子链表。的所有孩子结点形成该结点的孩子链表。ABCDEFG0 A1 B 2 C 3 D 4 E 5 F 6 G 65123孩子孩子(hi zi)(hi zi)链表链表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第41页/共212页第四十一页，共212页。孩子孩子(hi zi)-(hi zi)-兄弟表示法兄弟表示法struct TreeNode datat

29、ype data; struct TreeNode *children; struct TreeNode *next;typedef struct Tree;C C语言的类型语言的类型(lixng)(lixng)描述描述: :结点结点(ji din)结构结构: 每个结点除其信息域外，再增加两个分别指向该每个结点除其信息域外，再增加两个分别指向该结点的结点的第一个孩子结点第一个孩子结点和和下一个兄弟结点下一个兄弟结点的指针。的指针。childrendatanext第42页/共212页第四十二页，共212页。孩子孩子(hi zi)-(hi zi)-兄弟表示法兄弟表示法第43页/共212页第四十三页

30、，共212页。树、森林树、森林(snln)(snln)与二与二叉树叉树之间的转换之间的转换 第44页/共212页第四十四页，共212页。 将树转换成二叉树的方法将树转换成二叉树的方法加线：在兄弟之间加一连线加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除抹线：对每个结点，除了其左孩子外，去除(q ch)其与其其与其余孩子之间的关系余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转旋转：以树的根结点为轴心，将整树顺时针转45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定(ydng)为空第45页/共212页

31、第四十五页，共212页。将二叉树转换成树将二叉树转换成树加线：若加线：若p p结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将p p的右孩子，右的右孩子，右孩子的右孩子，孩子的右孩子，沿分支找到的所有沿分支找到的所有(suyu)(suyu)右孩子，右孩子，都与都与p p的双亲用线连起来的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI第46页/共212页第四十六页，共212页。AB

32、CDEFGHIABCDEFGHI 树的先序遍历和后序遍历可以借用二叉树树的先序遍历和后序遍历可以借用二叉树的先序遍历和中序遍历的算法的先序遍历和中序遍历的算法(sun f)来实现来实现。先序序列先序序列(xli)(xli)：ABEFGCDHIABEFGCDHI后序序列后序序列(xli)(xli)：EFGBCHIDAEFGBCHIDA先序序列先序序列(xli)(xli)：ABEFGCDHIABEFGCDHI中序序列中序序列(xli)(xli)：EFGBCHIDAEFGBCHIDA后序序列后序序列(xli)(xli)：GFEIHDCBAGFEIHDCBA树树二叉树二叉树第47页/共212页第四十七

33、页，共212页。森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连(xin lin)以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第48页/共212页第四十八页，共212页。二叉树转换成森林二叉树转换成森林抹线：将二叉树中根结点抹线：将二叉树中根结点(ji din)与其右孩子连线，及与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树变成孤立的二叉树还原：将孤立的二叉树还原成树还原：将孤立的二叉树还

34、原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第49页/共212页第四十九页，共212页。 由此，树和森林的各种操作(cozu)均可与二叉树的各种操作(cozu)相对应。 应当注意的是，和树对应的二叉树，其左、右子树的概念(ginin)已改变为： 左是孩子，右是兄弟第50页/共212页第五十页，共212页。 把下面把下面(xi mian)的树转化成二叉树。的树转化成二叉树。ABCDEFGHI练习练习(linx)KLJABCDEFGHIJKL第51页/共212页第五十一页，共212页。哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码(bin m)(bin m) 第

35、52页/共212页第五十二页，共212页。相关相关(xinggun)概概念念树的路径树的路径(ljng)长度定义为：长度定义为： 树中每个结点的路径树中每个结点的路径(ljng)长度之和。长度之和。 结点的路径长度定义为：结点的路径长度定义为： 从根结点到该结点的路径上分支从根结点到该结点的路径上分支(fnzh)的数的数目。目。 树的带权路径长度树的带权路径长度定义为：定义为： 树中所有树中所有叶子结点的带权路径叶子结点的带权路径长度长度之和之和 WPL(T) = wklk (对所有叶子结点对所有叶子结点) 结点的带权路径长度结点的带权路径长度定义为：定义为： 从根结点到该结点的路径长度与结点

36、上权从根结点到该结点的路径长度与结点上权的乘积。的乘积。第53页/共212页第五十三页，共212页。设：a,b,c,d 的权值为： a=7, b=5, c=2, d=4;下面三棵不同的树的带权路径(ljng)长度为： (7+5+4+2）*2=36 (7+5)*3+4*2+2=46 7+5*2+(2+4)*3=35 第3棵树的带权路径(ljng)长度最小。第54页/共212页第五十四页，共212页。最优二叉树 :设有n个权值w1,w2,w3,.,wn,构造有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树(赫夫曼树).赫夫曼树的应用：判定问题。 例

37、：将学生(xu sheng)的百分制变成五级分制：设学生(xu sheng)的成绩分布在五个等级上是不均匀的。分数分数0-590-5960-6960-6970-7970-7980-8980-8990-10090-100五级分制五级分制不及格不及格及格及格中中良良优优比例比例0.050.050.150.150.40.40.30.30.10.1第55页/共212页第五十五页，共212页。二、如何二、如何(rh)构造最优树构造最优树赫夫曼算法:(1)根据给定的n个权值w1,w2,w3,.,wn构成n棵二叉树的集合F=T1,T2,T3,.,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子

38、树均为空.(2)在集合F中选取两棵根结点权值最小的树作为左右子树构造(guzo)一棵新的二叉树,新二叉树的根结点的权值为其左右子树上根结点的权值之和.(3)在集合F中删除这两棵树,同时将新得到的二叉树加入F中.(4)重复步骤(2)、(3),直到F中只含一棵树为止,这棵树就是一棵赫夫曼树.第56页/共212页第五十六页，共212页。9例如(lr): 已知权值 W= 5, 6, 2, 9, 7 56275276976713952795271667132900001111000111100101(1)根据给定的n个权值w1,w2,w3,.,wn构成n棵二叉树的集合F=T1,T2,T3,.,Tn,其中

39、每棵二叉树Ti中只有一个(y )带权为wi的根结点,其左右子树均为空.(2)在集合(jh)F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,新二叉树的根结点的权值为其左右子树上根结点的权值之和.(3)在集合F中删除这两棵树,同时将新得到的二叉树加入F中.(4)重复步骤(2)、(3),直到F中只含一棵树为止,这棵树就是一棵赫夫曼树.第57页/共212页第五十七页，共212页。哈夫曼编码 通信中的信息传递问题：在传递信息时，如何在能够识别的前提下，使传递的字符数最少。例： 电报中的报文 “ABACCDA” 四个字符的编码问题。两位编码： 00 01 10 11 如果用不同长度的编码：

40、例用 0 1 00 01 前缀编码:对于不等长编码,若任一个字符的编码都不是另一个字符的编码的前缀,则这种编码称为前缀编码.前缀编码使得字符编码的平均长度最短.赫夫曼编码是一种前缀编码.赫夫曼编码的方法(fngf): (1)把字符出现的频率作为权值,根据这些权值构造一棵赫夫曼树. (2)约定在赫夫曼树中,左分支表示字符0,右分支表示字符1,则从根结点到叶子结点的路径上的分支字符组成的字符串即为该叶子结点字符的编码.第58页/共212页第五十八页，共212页。 已知某系统在通信联系中只可能出现已知某系统在通信联系中只可能出现8 8种字符：种字符：abcdefghabcdefgh，其概率分别为，其

41、概率分别为0.050.05，0.290.29， 0.07 0.07， 0.080.08， 0.14 0.14，0.23,0.030.23,0.03，0.110.11，试据此构造哈，试据此构造哈夫曼树，要求：夫曼树，要求： 1) 1)画出构造哈夫曼树的过程画出构造哈夫曼树的过程(guchng)(guchng)； 2) 2)求每个字符的哈夫曼编码。求每个字符的哈夫曼编码。例题例题(lt)哈夫曼编码哈夫曼编码(bin m)：a: 0110b: 10c: 1110d: 1111bfhagcd2311e5291437801000000111111e: 110f: 00g: 0111h: 010第59页/

42、共212页第五十九页，共212页。 设权值序列为设权值序列为8，5，3，4，7，据此构造，据此构造(guzo)一棵哈夫曼一棵哈夫曼树。画出构造树。画出构造(guzo)哈夫曼树过程。哈夫曼树过程。 练习练习(linx)58347第60页/共212页第六十页，共212页。习习 题题 一一第61页/共212页第六十一页，共212页。1. 假定( jidng)在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 A15 B16 C17 D472. 深度为5的二叉树至多有_个结点。A. 16 B. 32 C. 31 D. 103. 对一个满二叉树，m个树叶，n个结点，深度为h，

43、则_ 。A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1答案(d n)：B C D第62页/共212页第六十二页，共212页。4.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面(qin mian)，这种说法_。 5. A. 正确 B. 错误6.5. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。7.A. bdgcefha B. gdbecfha 8.C. bdgaechf D. gdbehfca9.6. 在一非空二叉树的中序遍历序列中，根结点的右边_。10. A. 只有右子树上

44、的所有结点 11. B. 只有右子树上的部分结点12. C. 只有左子树上的部分结点 13. D. 只有左子树上的所有结点答案(d n)：A D A第63页/共212页第六十三页，共212页。7. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论_是正确的。 A.树的先根遍历序列与其(yq)对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其(yq)对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其(yq)对应的二叉树的中序遍历序列相同 D.以上都不对答案(d n)：A第64

45、页/共212页第六十四页，共212页。8. 有一棵树如图所示，回答下面的问题： 这棵树的根结点是_； 这棵树的叶子(y zi)结点是_； 结点k3的度是_； 这棵树的度是_； 这棵树的深度是_； 结点k3的子女是_； 结点k3的父结点是_；k1 k7k5k2k4k6k31. k1 k2,k5,k7,k4 2 3 4 k5,k6 k1 第65页/共212页第六十五页，共212页。9.9.一棵二叉树的结点数据采用顺序一棵二叉树的结点数据采用顺序存储结构存储结构(jigu)(jigu)，存储于数组，存储于数组t t中，如图所示，则该二叉树的链接中，如图所示，则该二叉树的链接表示形式为表示形式为_ _

46、 _。10. 深度为k的完全二叉树至少有_个结点。至多有_个结点，若按自上而下，从左到右次序给结点编号（从1开始(kish)），则编号最小的叶子结点的编号是_。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 k-1 、 2 k-1 、 2 k-1第66页/共212页第六十六页，共212页。11.根据二叉树的定义，具有( jyu)三个结点的二叉树有5种不同的形态，请将它们分别画出。假设

47、一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。aaaaacccccbbbbbbEBEFAECDKGHIJ图6.12第67页/共212页第六十七页，共212页。 以数据集4，5，6，7，10，12，18为结点权值，画出构造Huffman树的每一步图示，计算( j sun)其带权路径长度为。 假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这八个字母设计哈夫曼编码。62372519181312109674

48、5图6.16 Huffman树第68页/共212页第六十八页，共212页。习题习题(xt)二二1. 三个结点( ji din)的二叉树的基本形态有 种，三个结点( ji din)的树的基本形态有 种。2一棵具有64个结点( ji din)的完全二叉树的高度为 。 3. 设一棵二叉树的先序遍历序列为ABCDFEGH，中序遍历序列为BAFDCGEH，请完成下列要求： 1）画出该二叉树； 2）写出该二叉树的后序遍历序列； 3）将该二叉树转换成森林；第69页/共212页第六十九页，共212页。习题习题(xt)4. 已知一棵二叉树的顺序存储结构如下图所示，图中“0”表示(biosh)不存在的结点， 1）

49、画出该二叉树； 2）求该二叉树的先序遍历序列和中序遍历序列； 3）将该二叉树转换成一棵树。5. 设字符集为A，B，C，D，E，其对应的权值为7，5，2，4，9，据此构造哈夫曼树，要求： 1）画出构造哈夫曼树过程； 2）求每个字符的哈夫曼编码；A B 0 C D 0 0 E 0 F G第70页/共212页第七十页，共212页。本章本章(bn zhn)复习要复习要点点1、树的基本概念；、树的基本概念；结点、结点的度、树的度、叶子结点、分支结点、路径、孩结点、结点的度、树的度、叶子结点、分支结点、路径、孩子、双亲、结点的层次、树的深度、兄弟、堂兄弟子、双亲、结点的层次、树的深度、兄弟、堂兄弟2、二叉

50、树的基本概念：二叉树、满二叉树、完全二叉树；、二叉树的基本概念：二叉树、满二叉树、完全二叉树；3、二叉树的、二叉树的5个性质；个性质；4、具有、具有3个结点的二叉树的个结点的二叉树的5种形态；种形态；3个结点的树的个结点的树的2种的种的形态；形态；5、理解二叉树的顺序存储结构；根据二叉树的顺序存储结、理解二叉树的顺序存储结构；根据二叉树的顺序存储结构画二叉树；构画二叉树；6、二叉树的先序、中序和后序遍历；根据先序和中序遍历、二叉树的先序、中序和后序遍历；根据先序和中序遍历的序列画二叉树；的序列画二叉树；7、构造、构造(guzo)哈夫曼树，写出哈夫曼编码；哈夫曼树，写出哈夫曼编码；8、树、森林、

51、二叉树的互相转换；、树、森林、二叉树的互相转换；第71页/共212页第七十一页，共212页。 1. B 2. B 3. C 4. C 1. 由于(yuy)二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_。 A. 正确 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 第72页/共2

52、12页第七十二页，共212页。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 h-1 8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_。 A.不发生(fshng)改变 B.发生(fshng)改变 C.不能确定 D.以上都不对 第73页/共212页第七十三页，共212页。9. C 10. A 11. D 9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那

53、么该二叉树的后序为_。 A. uwvts B. vwuts C. wuvts D. wutsv 10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面(qin mian)，这种说法_。 A. 正确 B. 错误 11. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 第74页/共212页第七十四页，共212页。1. A 15. B 12. 在一非空二叉树的中序遍历序列中，根结点的右边_。 A. 只有右子树上的所有

54、结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 15设a,b为一棵二叉树上的两个(lin )结点，在中序遍历时，a在b前的条件是 。 Aa在b的右方Ba在b的左方 Ca是b的祖先Da是b的子孙 第75页/共212页第七十五页，共212页。 16. 已知某二叉树的后序(hu x)遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。 A. acbed B. decab C. deabc D. cedba第76页/共212页第七十六页，共212页。 18. 如图6.3所示的4棵二叉树，_不是(b shi)完全二叉树。(A) (B) (

55、C) (D) 图6.3(A) (B) (C) (D)图6.3第77页/共212页第七十七页，共212页。 第八章第八章 图图第78页/共212页第七十八页，共212页。第79页/共212页第七十九页，共212页。第80页/共212页第八十页，共212页。第81页/共212页第八十一页，共212页。 第82页/共212页第八十二页，共212页。第83页/共212页第八十三页，共212页。1235687410796671231516ABDCE60304535804075第84页/共212页第八十四页，共212页。 第85页/共212页第八十五页，共212页。习习 题题1. 在一个图中，所有顶点的度

56、数之和等于所有边数的_倍。 A. 1/2 B. 1 C. 2 D. 4 2. 任何一个无向连通图的最小生成树 。 A.只有(zhyu)一棵B.有一棵或多棵 C.一定有多棵D.可能不存在3. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。 A. 1/2 B. 1 C. 2 D. 4答案(d n)： C B B第86页/共212页第八十六页，共212页。4. 一个有n个顶点的无向图最多有_条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n5. 具有4个顶点的无向完全图有_条边。 A. 6 B. 12 C. 16 D. 206. 具有6个顶点的无向图至少应有(

57、yn yu)_条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 87. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。 A. n B. n+1 C. n-1 D. n/2CAAC第87页/共212页第八十七页，共212页。图的存储图的存储(cn ch)表示表示一、图的数组一、图的数组( (邻接矩阵邻接矩阵) )存储存储(cn ch)(cn ch)表示表示二、图的邻接二、图的邻接(ln ji)(ln ji)表存储表示表存储表示第88页/共212页第八十八页，共212页。图的数组图的数组( (邻接矩阵邻接矩阵) )存储存储(cn ch)(cn ch)表示表示邻接矩阵表示

58、顶点间相联关系的矩阵定义：设G=(V,E)是有 n 个顶点的图，G的邻接矩阵A是如下(rxi)的n阶方阵。Aij=0 (i,j)E(G)1 (i,j)E(G)第89页/共212页第八十九页，共212页。2）有向图邻接矩阵不一定对称(duchn)；有n个顶点的有向图需存储空间为n3）无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和4）有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和图的邻接矩阵的性质图的邻接矩阵的性质(xngzh)(xngzh)1）无向(w xin)图的邻接矩阵对称，可压缩存储；有n个顶点的无向(w xin)图需存储空间为n(n+1)/2

59、第90页/共212页第九十页，共212页。 网的邻接矩阵网的邻接矩阵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 第91页/共212页第九十一页，共212页。21435BADCE0111110010100011100010100edgesAdjMatrix0111100000000010100000000edgesAdjMatrix第92页/共212页第九十二页，共212页。 邻接表是图的一种链式存储结构。方法是对

60、图中的每一个顶点建立一个依附于该顶点的边的表。而表头结点用一顺序结构(向量(xingling)）的形式存储。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图的邻接表存储图的邻接表存储(cn ch)表示表示第93页/共212页第九十三页，共212页。例题例题(lt)：画出下图的邻接表画出下图的邻接表v1v2v3v4v1 v2 v3 v4 21113 4 4 24 3 第94页/共212页第九十四页，共212页。表中，对每个顶点表中，对每个顶点(dngdin)，链接的，链接的是指向该顶点是指向该顶点(dngdin)的弧