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

数据结构树、图、查找、排序,树: 是 n(n0) 个结点的有限集合。如果该集合为空，称为空树。在任意一棵非空树中:,树的定义,有且仅有一个特定的称为根结点 ( root ) 的结点; 2) 其他结点可分为若干个互不相交的子集,而且每一个子集本身又是一棵树,称为根的子树。,递归定义,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,结点分支的个数,即子树的数目 如：A的度-3；B的度-2；K的度-0；,树中所有结点的度的最大值 如：树的度为3；,度为零的结点，也称终端结点 如例：K，L，F，G，M，I，J为终端结点,度大于零的结点 如例：A,B,C,D,E,基本术语,森林：是 m（m0）棵互不相交的树的集合,A,root,F,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),7.2 二叉树,二叉树或为空树；或是由一个根结点加上两棵分别称为左和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,E,F,特点： 1）每个结点最多只有两棵子树； 2）两颗子树有左右之分，顺序不能换。,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,特殊的二叉树：满二叉树,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,深度为3，节点数=23-1=7,深度为4，节点数=24-1=15,特点：1）每一层上的结点数都是最大结点数； 2）叶子结点都在最后一层。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,特点：1）除了最下一层外其余各层都是满的； 2）最下一层的结点都集中在该层的左侧。,特殊的二叉树：完全二叉树,性质 1 ：满二叉树的第 i 层上有2i-1 个结点(i1),用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 时，只有一个根结点， 2i-1 = 20 = 1；,假设第j层有2j-1结点，命题成立;,第j层的每个结点都有2个结点，则第(j+1)层上的结点数=2*2j-1=2j=2(j+1)-1。,二叉树的性质,性质 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 ，则必存在关系式： n0 = n2+1。,性质4：具有 n 个结点的完全二叉树的深度为 log2n +1,性质 5 ：对于具有n个结点的完全二叉树，如果按照从上到下和从左至右的顺序对二叉树中的所有结点从 1 至 n进行编号，则对于任意的序号为 i 的结点，有： 若 i1，则序号为i的结点的双亲结点的序号为i/2；如果i=1，则该结点是根，无双亲; 若 2in 则该结点无左孩子； 若 2i+1n，则序号为i的结点无右孩子结点。,二叉树的存储结构,二、二叉树的链式存储表示,一、 二叉树的顺序存储表示,用一组连续的存储单元存储二叉树的数据元素, 以结点存储的相对位置表示结点之间的关系。 为了正确地反映结点之间的关系,任何二叉树都必须按照完全二叉树的形式来存储. 这种存储方式对某些二叉树的存储会造成存储空间的浪费。,顺序存储结构,在高级语言中,可以用一维数组来描述这种顺序存储结构。 例如：,完全二叉树的顺序存储,一般二叉树的存储,NOTES:代表空元素,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 TElemType SqBiTreeMAX_TREE_SIZE; / 1号单元存储根结点,例如:,练习：,1已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（） A7B8 C9D10 2若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（） A10B11 C12D不确定的 已知一棵二叉树的顺序存储序列为：aebfcd，则： 1）e的左孩子是哪个结点？右孩子是哪个结点？ 2）d的双亲是哪个结点？,答案：B 答案：A 答案： 1）没有左孩子；右孩子是f； 2）b；,练习：,3假设一棵二叉树的顺序存储结构如图所示，请回答下列问题： （1）哪个结点是根结点？ （2）哪些结点是叶子结点？ （3）哪些结点是H的祖先？ （4）哪些结点是B的兄弟？ （5）树的深度是多少？,A D,H A,C,E C 4,二、二叉树的链式存储表示,1. 二叉链表,2三叉链表,二叉链结构 每个结点包含三个域: 数据域和左右指针域,如下表所示,root,二叉链表,struct BTNode datatype data; struct BTNode *lchild, *rchild; Typedef BTNode *BTree; 将二叉树类型BTree定义为指向二叉链表结点结构的指针类型。,结点结构:,C 语言的类型描述如下:,三叉链表 三叉链表结构：每个结点除包含数据域和左右指针域外,还包含一个指向其双亲结点的指针域。,root,struct TriTNode / 结点结构 datatype data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 typedef TriTNode *TriTree;,结点结构:,C 语言的类型描述如下:,在这两种结构中,只需要给出指向根结点的指针,即可访问树中任意一个结点.,尽管在二叉表中无法由结点直接找到其双亲，但由于二叉链表的结构灵活，操作方便，对于一般情况下的二叉树，甚至比顺序存储结构还节省空间。因此二叉链表是最常用的二叉树存储方式。 今后，我们所涉及到的二叉树，如不加特别说明均采用二叉链表存储。,说明,二叉树的遍历,遍历二叉树是指按照一定的规律对二叉树中的每个结点，访问且仅访问一次的处理过程。,“访问”的含义可以很广，如：求结点的度、层次、输出结点的信息等等。,“遍历”是任何类型均有的操作， 1）对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。 2）而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。,对“二叉树”而言，可以把二叉树看成由三个基本单元组成: 根结点(D)、左子树(L)、右子树(R),并且规定左子树上的所有结点应该在右子树上的所有结点之前被访问,由此可以得到三种遍历顺序:先序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD),先序的遍历算法,中序的遍历算法,后序的遍历算法,遍历算法,若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,先序的遍历算法：,先序遍历：,A B D E G C F,若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。,中序的遍历算法：,中序遍历：,D B G E A C F,若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,后序的遍历算法：,后序遍历：,D G E B F C A,先序遍历：,中序遍历：,后序遍历：,A B D G C E H F,B G D A H E C F,G D B H E F C A,例题,中序遍历：,先序遍历：,后序遍历：,a + b * c d e / f,- + a * b c d / e f,a b c d - * + e f / -,例题,( ( ),根据遍历序列画二叉树,由一棵二叉树的先序序列和中序序列或中序和后序能够唯一确定一棵二叉树。,先序序列：A B C D E F G H I 中序序列：B C A E D G H F I,练习,已知一棵二叉树的先序序列和中序序列，请画出该二叉树。,先序序列：A B C D E F G H I J 中序序列：C B E D F A H G J I,树和森林,树的存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟） 存储表示法,树的双亲表示法,以一组连续空间(数组)存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在数组中的位置.,typedef struct datatype data; int parent; Node; typedef Node Tree MAX_NODE_NUM ,#define MAX_NODE_NUM 100,C语言的类型描述:,孩子表示法,存储每个结点及其孩子信息。每个结点的所有孩子结点形成该结点的孩子链表。,孩子链表,孩子-兄弟表示法,struct TreeNode datatype data; struct TreeNode *children; struct TreeNode *next; typedef struct Tree;,C语言的类型描述:,结点结构:,每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。,孩子-兄弟表示法,树、森林与二叉树 之间的转换,将树转换成二叉树的方法 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构,树的先序遍历和后序遍历可以借用二叉树的先序遍历和中序遍历的算法来实现。,先序序列：ABEFGCDHI 后序序列：EFGBCHIDA,先序序列：ABEFGCDHI 中序序列：EFGBCHIDA 后序序列：GFEIHDCBA,树,二叉树,森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树,由此，树和森林的各种操作均可与二叉树的各种操作相对应。,应当注意的是，和树对应的二叉树，其左、右子树的概念 已改变为： 左是孩子，右是兄弟,把下面的树转化成二叉树。,A,B,C,D,E,F,G,H,I,练习,K,L,J,哈夫曼树与哈夫曼编码,相关概念,树的路径长度定义为： 树中每个结点的路径长度之和。,结点的路径长度定义为： 从根结点到该结点的路径上分支的数目。,树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点),结点的带权路径长度定义为： 从根结点到该结点的路径长度与结点上权的乘积。,设：a,b,c,d 的权值为： a=7, b=5, c=2, d=4; 下面三棵不同的树的带权路径长度为： (7+5+4+2）*2=36 (7+5)*3+4*2+2=46 7+5*2+(2+4)*3=35 第3棵树的带权路径长度最小。,最优二叉树 :设有n个权值w1,w2,w3,.,wn,构造有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树(赫夫曼树). 赫夫曼树的应用：判定问题。 例：将学生的百分制变成五级分制：设学生的成绩分布在五个等级上是不均匀的。,二、如何构造最优树,赫夫曼算法: (1)根据给定的n个权值w1,w2,w3,.,wn构成n棵二叉树的集合F=T1,T2,T3,.,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均为空. (2)在集合F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,新二叉树的根结点的权值为其左右子树上根结点的权值之和. (3)在集合F中删除这两棵树,同时将新得到的二叉树加入F中. (4)重复步骤(2)、(3),直到F中只含一棵树为止,这棵树就是一棵赫夫曼树.,9,例如: 已知权值 W= 5, 6, 2, 9, 7 ,5,6,2,7,5,2,7,6,9,7,6,7,13,9,9,16,29,0,0,0,0,1,1,1,1,00,01,11,100,101,(1)根据给定的n个权值w1,w2,w3,.,wn构成n棵二叉树的集合F=T1,T2,T3,.,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均为空.,(2)在集合F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,新二叉树的根结点的权值为其左右子树上根结点的权值之和.,(3)在集合F中删除这两棵树,同时将新得到的二叉树加入F中. (4)重复步骤(2)、(3),直到F中只含一棵树为止,这棵树就是一棵赫夫曼树.,哈夫曼编码 通信中的信息传递问题：在传递信息时，如何在能够识别的前提下，使传递的字符数最少。 例： 电报中的报文 “ABACCDA” 四个字符的编码问题。两位编码： 00 01 10 11 如果用不同长度的编码： 例用 0 1 00 01 前缀编码:对于不等长编码,若任一个字符的编码都不是另一个字符的编码的前缀,则这种编码称为前缀编码. 前缀编码使得字符编码的平均长度最短. 赫夫曼编码是一种前缀编码. 赫夫曼编码的方法: (1)把字符出现的频率作为权值,根据这些权值构造一棵赫夫曼树. (2)约定在赫夫曼树中,左分支表示字符0,右分支表示字符1,则从根结点到叶子结点的路径上的分支字符组成的字符串即为该叶子结点字符的编码.,已知某系统在通信联系中只可能出现8种字符：abcdefgh，其概率分别为0.05，0.29， 0.07， 0.08， 0.14，0.23,0.03，0.11，试据此构造哈夫曼树，要求： 1)画出构造哈夫曼树的过程； 2)求每个字符的哈夫曼编码。,例题,哈夫曼编码： a: 0110 b: 10 c: 1110 d: 1111,e: 110 f: 00 g: 0111 h: 010,设权值序列为8，5，3，4，7，据此构造一棵哈夫曼树。画出构造哈夫曼树过程。,练习,习 题 一,1. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 A15 B16 C17 D47 2. 深度为5的二叉树至多有_个结点。 A. 16 B. 32 C. 31 D. 10 3. 对一个满二叉树，m个树叶，n个结点，深度为h，则_ 。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1,答案：B C D,二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_。 A. 正确 B. 错误 5. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 6. 在一非空二叉树的中序遍历序列中，根结点的右边_。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点,答案：A D A,7. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论_是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对,答案：A,8. 有一棵树如图所示，回答下面的问题： 这棵树的根结点是_； 这棵树的叶子结点是_； 结点k3的度是_； 这棵树的度是_； 这棵树的深度是_； 结点k3的子女是_； 结点k3的父结点是_；,k1,k7,k5,k2,k4,k6,k3,1. k1 k2,k5,k7,k4 2 3 4 k5,k6 k1,9.一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图所示，则该二叉树的链接表示形式为_ _。,10. 深度为k的完全二叉树至少有_个结点。至多有_个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_。,2 k-1 、 2 k-1 、 2 k-1,11.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。,以数据集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。试为这八个字母设计哈夫曼编码。,习题二,1. 三个结点的二叉树的基本形态有 种，三个结点的树的基本形态有 种。 2一棵具有64个结点的完全二叉树的高度为 。 3. 设一棵二叉树的先序遍历序列为ABCDFEGH，中序遍历序列为BAFDCGEH，请完成下列要求： 1）画出该二叉树； 2）写出该二叉树的后序遍历序列； 3）将该二叉树转换成森林；,习题,4. 已知一棵二叉树的顺序存储结构如下图所示，图中“0”表示不存在的结点， 1）画出该二叉树； 2）求该二叉树的先序遍历序列和中序遍历序列； 3）将该二叉树转换成一棵树。 5. 设字符集为A，B，C，D，E，其对应的权值为7，5，2，4，9，据此构造哈夫曼树，要求： 1）画出构造哈夫曼树过程； 2）求每个字符的哈夫曼编码；,本章复习要点,1、树的基本概念； 结点、结点的度、树的度、叶子结点、分支结点、路径、孩子、双亲、结点的层次、树的深度、兄弟、堂兄弟 2、二叉树的基本概念：二叉树、满二叉树、完全二叉树； 3、二叉树的5个性质； 4、具有3个结点的二叉树的5种形态；3个结点的树的2种的形态； 5、理解二叉树的顺序存储结构；根据二叉树的顺序存储结构画二叉树； 6、二叉树的先序、中序和后序遍历；根据先序和中序遍历的序列画二叉树； 7、构造哈夫曼树，写出哈夫曼编码； 8、树、森林、二叉树的互相转换；,1. B 2. B 3. C 4. C,1. 由于二叉树中每个结点的度最大为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,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.不发生改变 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. bdgcefha 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.3所示的4棵二叉树，_不是完全二叉树。(A) (B) (C) (D) 图6.3,第八章 图,图的基本概念,图的定义：一个图G是由两个集合V和E组成，V是有限的非空顶点集，E是V上的顶点对所构成的边集，分别用V（G）和E（G）来表示图中的顶点集和边集。用二元组G=（V，E）来表示图G。 有向图与无向图 若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向的，则称G为无向图。,完全图 对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1) ，则称其为有向完全图。 邻接顶点 若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接，并称边（vi,vj）关联于顶点vi和vj，或称（vi,vj）与顶点vi和vj相关联。若（vi,vj）是一条弧，则称顶点vi邻接至顶点vj,顶点vj邻接至顶点vi,。弧（vi,vj）与顶点vi、vj关联。,顶点的度 一个顶点v的度是与它相关联（依附）的边的条数。,顶点 v 的入度 是以 v 为终点的有向边的条数。 顶点 v 的出度是以 v 为始点的有向边的条数。 有向图的顶点的度等于它的入度与出度之和。,子图 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。,路径 在图 G(V, E) 中, 若存在一个顶点序列 vp1, vp2, , vpm，使得(vi, vp1)、(vp1, vp2)、 .、(vpm, vj)均属于E，则称顶点vi到vj存在一 条路径。若一条路径上除了vi 和vj 可以相同外， 其余顶点均不相同，则称此路径为一条简单路径 。起点和终点相同的路径称为简单回路或简单环。,图的连通 在无向图G中，若两个顶点vi和vj之间有 路径存在，则称vi 和vj 是连通的。若G中任意两 个顶点都是连通的，则称G为连通图。非连通图的 极大连通子图叫做连通分量。,强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,权 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。,权图（网络）,生成树 一个连通图的生成树是它的极小 连通子图，在n个顶点的情形下，有n-1条 边。,生成林 若G是一个不连通的无向图，G的每个连通分量都有一棵生成树，这些生成树构成G的生成森林，简称生成林。,习 题,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 B,4. 一个有n个顶点的无向图最多有_条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5. 具有4个顶点的无向完全图有_条边。 A. 6 B. 12 C. 16 D. 20 6. 具有6个顶点的无向图至少应有_条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。 A. n B. n+1 C. n-1 D. n/2,C,A,A,C,图的存储表示,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,图的数组(邻接矩阵)存储表示,邻接矩阵表示顶点间相联关系的矩阵 定义：设G=(V,E)是有 n 个顶点的图，G的邻接矩阵A是如下的n阶方阵。,2）有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n 3）无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 4）有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和,图的邻接矩阵的性质,1）无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2,网的邻接矩阵, 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 ,无向图,有向图,AdjMatrix,AdjMatrix,练习,邻接表是图的一种链式存储结构。方法是对图中的每一个顶点建立一个依附于该顶点的边的表。而表头结点用一顺序结构(向量）的形式存储。,图的邻接表存储表示,例题： 画出下图的邻接表,有向图的邻接表和逆邻接表 在有向图的邻接表中，第 i 个边链表链接的边都是顶点 i 发出的边。也叫做出边表。在有向图的邻接表中不易找到指向该顶点的弧 在有向图的逆邻接表中，第 i 个边链表链接的边都是进入顶点 i 的边。也叫做入边表。在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧,邻接表,逆邻接表,有向图的邻接表,有向图的逆邻接表,例题 画出该有向图的邻接表和 逆邻接表,网络 (带权图) 的邻接表,图的遍历,图的遍历: 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,深度优先搜索,广度优先搜索,深度优先搜索遍历图,从图中的某一个顶点 v0 出发，访问此顶点，然后 依次从 v0 的没被访问的邻接点出发深度优先遍历图，直至图中所有和 v0 有路径相通的顶点都被访问到；若此时图中仍有顶点没有被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程。,深度遍历,根据图的形态做图的深度优先遍历,根据图的形态可以得出图的多个深度优先遍历序列。,0 a-,2 c -,6 g -,5 f -,1 b -,4 e -,7 h -,3 d,根据图的邻接表做深度优先遍历,从顶点a出发的深度优先遍历：,0,2,6,0,1,4,7,根据图的邻接表得到的深度优先遍历序列是唯一的。,方法：从图中的某一个顶点 v0 出发，访问v0之后，依次访问v0 的没被访问的邻接点，然后，分别从这些邻接点出发，广度优先遍历图，直至所有顶点都被访问；若此时图中仍有结点没有被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程。,遍历结果： V1- V2 - V3 -V4 - V5 - V6 - V7 - V8,广度优先搜索遍历图,遍历结果： V1- V3 - V2 -V6 - V7 - V4 - V5 - V8,先访问的顶点其邻接顶点也先被访问,从a出发根据邻接表广度优先遍历：,1,a-,c -,b -,g -,f -,e -,h,2,3,4,5,6,d -,7,8,根据图的邻接表得到的广度优先遍历序列是唯一的。,8.4 生成树 生成树 定义：所有顶点均由边连接在一起，但不存在回路的图叫生成树深度优先生成树与广度优先生成树 说明 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n-1条边 生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,最小生成树 ( minimum cost spanning tree ),假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？,问题：,构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法一：（普里姆算法）,普里姆(Prim)算法,基本思想：从连通网络 N = V, E 中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。,a,e,d,c,b,g,f,14,8,5,3,16,21,所得生成树权值和,= 14+8+3+5+16+21 = 67,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,克鲁斯卡尔 (Kruskal) 算法,基本思想：设有一个有 n 个顶点的连通网络 N = V, E , 最初先构造一个只有 n个顶点,没有边的非连通图 T = V, , 图中每个顶点自成一个连通分量。当在E 中选一条具有最小权值的边时, 若该边的两个顶点落在不同的连通分量上，则将此边入到 T 中; 否则将此边舍去，重新选择一条权值最小的边。如此重复下去,直到所有顶点在同一个连通分量上为止。,0,1,0,2,6,3,4,5,12,14,16,18,10,22,24,25,习 题,由V1，V2，V3，V4，V5，V6六个顶点构成的无向图的邻接矩阵如下表所示。 1）画出该无向图； 2）画出该无向图的邻接表存储结构。 3）根据所画邻接表，给出从定点 V1出发的深度和广度优先遍历序列。,深度遍历序列：V1 V2 V4 V5 V6 V3 广度遍历结果：V1 V2 V3 V4 V6 V5,习 题,一个有向图有5个顶点，6条弧。5个顶点编号为0，1，2，3，4；其弧用顶点对表示为，。要求： （1）画出该有向图； (2）建立该有向图邻接表存储结构； （3）写出从0号顶点出发的深度优先搜索与广度优先搜索的序列。,深度： 0 1 4 2 3； 广度： 0 1 2 4 3；,本章复习要点,1、基本概念； 2、图的邻接矩阵、邻接表； 3、图的深度优先遍历、广度优先遍历； 4、图的最小生成树：普里姆算法、克鲁斯卡尔算法；,第九章 查找,关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。,若此关键字能识别若干记录，则称之为“次关键字”。,基本概念,基本概念,查找（Searching）的定义是：给定一个关键字值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。,基本概念,查找表是由同一类型的数据元素(或记录)构成的集合。 对查找表经常进行的操作: 1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。,查找表的数据结构表示,若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表（Dynamic Search Table）。否则称之为静态查找表(Static Search Table)。 例如：词典、电话薄 若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。,顺序查找,二分查找,分块查找,线性表的查找,顺序查找(Sequential Search) 基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 既适用于顺序表，也适用于链表。,顺序查找,以顺序表或线性链表表示静态查找表 回顾顺序表的查找过程：,顺序查找表,ST.elem,假设给定值 kval = 64 要求 ST.elemi = kval, 问: i = ?,66,循环的判断条件： ST.elemi.key!= kval / 设置“哨兵” /从后往前找 for (int i=ST.length;ST.elemi.key!=kval;-i); return i;/ 找不到时，i为0 / Search_Seq,顺序查找的优点 算法简单，且对表的结构无任何要求，无论是用数组还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。 顺序查找的缺点 查找效率低。,二分查找又称折半查找，它是一种效率较高的查找方法。 二分查找要求： 1）线性表是有序表，即表中结点按关键字有序； 2）要用数组作为表的存储结构（顺序表）； 不妨设有序表是递增有序的。,二分查找,二分查找的基本思想是： 1）首先确定该区间的中点位置： mid = 2）然后将待查的K值与searchildhListmid.key比较： (1)若相等，则查找成功并返回此位置 (2)若searchildhListmid.key k，则在low到mid-1中继续查找； (3)若searchildhListmid.key k， 则在mid+1到high中继续查找。,二分查找,ST.elem,ST.length,例如: key = 64 的查找过程如下,low,high,mid,low,mid,high,mid,low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2。,ST.elem,ST.length,例如: key = 20 的查找过程如下,low,high,mid,low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2。,high,mid,low,mid,high,highlow 没找到,int bin_searchildh (DataNode searchildhList, int n, KeyType k ) int low = 1; high = n; / 置区间初值 while (low k) ) high = mid - 1; / 继续在前半区间进行查找 else low = mid + 1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 ,二分查找的优点和缺点,虽然二分查找的效率高，但是要将表按关键字排序。 二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。,练习,给出一个折半查找算法如下： 设记录R1，R2，.，Rn的关键字K1Ki，转第五步； 如果K=Ki，则查找成功 第四步【调整U】置Ui，返回第二步； 第五步【调整L】置Li；返回第二步；,分块查找是顺序查找和二分查找的折衷，也称索引顺序查找。将一个主表分成n个块，即n个子表，要求子表之间元素是按关键字有序排列的，而子表中元素可以无序，用每个子表最大关键字和指示块中第一个记录在表中位置建立索引表。,查找过程： 1）由索引确定记录所在块； 由于索引表按关键字有序，故可用顺序查找或折半查找 2）在顺序表的某个块内进行查找。 由于块内无序，只能用顺序查找,分块查找,树表的查找,二叉排序树 （二叉查找树）,1定义,2查找算法,3插入算法,4删除算法,5查找性能的分析,1定义：,二叉排序树或者是一棵空树；或者是具有如下特性的二叉树： （1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值； （3）它的左、右子树也都分别是二叉排序树。,是二叉排序树,不是二叉排序树,二叉排序树的查找算法,1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则继续在右子树上进行查找。,若二叉排序树为空，则查找不成功，否则：,例如:,二叉排序树,查找关键字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95 ,从上述查找过程可见，,在查找过程中，生成了一条查找路径:,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,二叉排序树的查找算法： Node* SearchBST(Node *tree, KeyType keyData，Node *p) /在二叉排序树tree中，查找关键字为keyData的元素 /若查找成功，则返回指向该元素的指针，否则返回空指针 Node *q; BOOL found=FALSE; q=tree; while(q) if( keyDataq-data.key) p=q; q=q-rchild; /在左子树中继续查找 else if( keyDatadata.key) p=q; q=q-lchild; /在右子树中继续查找 else found=TRUE ;break; if ( found ) return q; return NULL; ,练习,1.对有序表（5，8，10，14，18，19，20）进行折半查找，则： （1）若要查找10，需要与哪些元素比较？ （2）若要查找13，则需要与哪些元素比较？ 2.在如下的二叉排序树中进行查找，则： （1）查找87和23，分别需要与哪些元素比较？,二叉排序树是一个动态查找表，树的结构不是一次形成的；而是在查找的过程中，当树中不存在这一关键字时，不断的进行插入的结果。 根据动态查找表的定义，“插入”操作在查找不成功时才进行;,3二叉排序树的插入算法,若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。,例题： 已知关键字序列为：65，90，71，55，67，44，98，83，8，45，58，试用此序列构造一棵二叉排序树。,例： 设待查找的关键字序列为 45，24，53，45，12，24，90 则生成二叉排序树的过程如下：,45,24,53,12,90,算法：为了在查找不成功时返回插入位置，对上述的查找算法进行适当修改。 查找算法在查找不成功时给出结点的插入位置。,（1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。,4二叉排序树的删除算法,可分三种情况讨论：,和插入相反，删除在查找成功之后进行。在二叉排序树上删除一个结点，相当于在有序序列中删除一个记录，并要使删除节点之后该树仍是二叉排序树。,（1）被删除的结点是叶子结点,例如:,被删关键字 = 20,88,其双亲结点中相应指针域的值改为“空”,（2）被删除的结点只有左子树 或者只有右子树,其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。,被删关键字 = 40,80,（3）被删除的结点既有左子树，也有右子树,40,40,以其前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字 = 50,在二叉排序树中查找数据的过程，是走一条从根到该结点的路径的过程。但二叉排序树的结构与关键字的输入次序有关。 例：设关键字的输入次序为： 45，24，53，12，37，93 另一种输入次序为： 12, 24, 37, 45, 53, 92 设每个元素查找概率相等。,ASL1=1/6(1+2+2+3+3+ 3)=14 / 6 ASL2=1/6(1+2+3+4+5 +6)=21 / 6,在最好的情况下；平均查找长度为 |log 2n|+1; 在最坏情况下，平均查找长度为 （n+1)/2。,二叉排序树的查找分析,练习,依次输入数据3，7，1，4，6，生成一棵二叉排序树。 （1）画出生成后的二叉排序树； （2）假定每个元素的查找概率相同，试计算该二叉排序树的平均查找长度； （3）画出在此二叉排序树中删除7之后的树结构。,二叉平衡树是二叉查找树的另一种形式，其特点为：,树中每个结点的左、右子树深度之差的绝对值不大于1 。,例如:,是平衡树,不是平衡树,二叉平衡树,非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 Kn; 且 Ai-1 所指子树上所有关键字均小于Ki; Ai 所指子树上所有关键字均大于Ki; 树中所有叶子结点均不带信息，且在树中的同一层次上; 根结点或为叶子结点，或至少含有两棵子树; 其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树;,B-树,从根结点出发，沿指针搜索结点和在 结点内进行顺序（或折半）查找 两个过程 交叉进行。,查找过程：,若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；,若查找不成功，则返回插入位置。,B-树,查找：84，76，43,是B-树的一种变型,四、B+树,1B+树的结构特点：, 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；, 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值；, 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。,2查找过程,在 B+ 树上，既可以进行缩小范围的查 找，也可以进行顺序查找；, 在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束；,若在结点内查找时，给定值Ki， 则 应继续在 Ai 所指子树中进行查找；,50 96,15 50,62 78 96,71 78,84 89 96,56 62,20 26 43 50,3 8 15,sq,root,一、哈希表是什么？,以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。用这类方法表示的查找表，其平均查找长度都不为零 不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。 对于频繁使用的查找表，希望 ASL = 0。只有一个办法：预先知道所查关键字在表中的位置，即，要求：记录在表中位置和其关键字之间存在一种确定的关系。,哈希查找,但是，对于动态查找表而言，,因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 H(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 H(key) 为哈希函数。,1) 表长不确定；,2) 在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。,Zhao, Qian, Sun, Li, Wu, Chen, Han, Yan, Di 13 8 9 6 11 1 4 12 2,例如：对于如下 9 个关键字,设 哈希函数 H(key) = (Ord(第一个字母) -Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Yan,Di,问题: 若添加关键字 Zhou , 怎么办？,能否找到另一个哈希函数？,0 1 2 3 4 5 6 7 8 9 10 11 12 13,1) 哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的大小不超出允许范围即可; 对同一关键字可能得到同一哈希地址即： key1 key2，而 H(key1) = H(key2)。 这种现象称作“冲突”。具有相同函数值的关键字对该哈希函数来说叫做同义词 3) 一般情况下，冲突只能尽可能地少，而不能完全避免。 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突” 的方法。,从这个例子可见：,哈希表的定义:,根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。,二、构造哈希函数的方法,什么是一个“好”的哈希函数？ 对于关键字集合中的任一个关键字，经哈希函数映象到地址集合中任何一个地址的概率相等。称此类哈希函数为均匀的哈希函数。这样的哈希函数能使一组关键字均匀的分布在整个地址空间中，减少冲突。,几种构造哈希函数的方法： 1） 直接定址法 2) 数字分析法 平方取中法 4) 折叠法 5) 除留余数法 6) 随机数法,除留余数法 取关键字被某个不大于哈希表长 m 的数 p 除后所得余数为哈希函数。 H(key) = key %