【PPT】-第2章非线性数据结构树和图.ppt
《【PPT】-第2章非线性数据结构树和图.ppt》由会员分享,可在线阅读,更多相关《【PPT】-第2章非线性数据结构树和图.ppt(95页珍藏版)》请在三一文库上搜索。
1、第2章 非线性数据结构 树和图,西安交通大学计教中心 ,第2页/91,树形结构,树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在,并应用于: 人类社会的族谱、家谱、行政区域划分管理; 各种社会组织机构; 在计算机领域中,用树表示源程序的语法结构; 在OS中,文件系统、目录等组织结构也是用树来表示的。,第3页/91,树的逻辑结构,树是一种数据结构,可用二元组表示为: Tree=(D,R) 其中: D 是具有相同特性的数据元素的集合; R 是数据元素间逻辑关系的集合,且满足: 在D中存在唯一的称为根的数据元素,没有前趋; D中其余数据元素都有且只有一个前趋; D中所有元素,或有若
2、干个互不相同的后继(子树),或无后继(叶结点); 则称Tree为树。,第4页/91,树的递归定义:,树是由n个具有相同特性的数据元素组成的集合。若n=0,则称其为空树。一棵非空树T必须满足: 1)其中有一个特定的元素称为T的根root。 2)除根以外的集合可被划分为m个不相交的子集T1,T2,Tm,其中每个子集都是树。它们称为根root的子树。,第5页/91,树结构举例,C1(章) BOOK 1.1(节) 1.2 C1 C2 C3 C2 2.1 1.1 1.2 2.1 2.2 2.3 2.11 2.12 2.2 2.1.1 2.1.2 2.3 C3,书目录 目录树 树结构,第6页/91,与树相
3、关的术语, 结点:在树结构中一般把数据元素及其若干指向子树的分支称为结点。 结点的度:结点拥有的非空子树的个数。 树的度:树中所有结点的度的最大值。 叶子结点:度为0的结点。 分支结点:至少有一个非空子树的结点。 孩子结点和父结点:某结点所有子树的根结点都称为该结点的孩子结点,同时该结点也称为其孩子结点的父结点。,第7页/91, 兄弟结点:具有相同父结点的结点互为兄弟结点。 结点的层次:根结点的层次为1,其子结点的层次为2。依次类推,子结点的层次总比父结点多一层。 树的深度:树中结点所在的最大层次。 有序树和无序树:将树中各结点的子树看成自左向右有序的,则称该树为有序树。否则称为无序树。 森林
4、:由零棵或有限棵互不相交的树组成的集合。,第8页/91,二叉树的定义,二叉树是另一种树形结构: Binary_Tree =( D,R) 其中: D 是具有相同性质的数据元素的集合; R 是在D上某个两元关系的集合,且满足: D中存在唯一称为根的数据元素,没有前趋; D中其余元素都有且仅有一个前趋; 每个结点至多只有两个子树; D中元素,或有两个互不相交后继,或无后继; 左、右子树分别又是一棵二叉树。,第9页/91,二叉树的五种基本形态,(a) (b) (c),(d) (e),O 空结点,O 单个结点,右子树为空的二叉树,左子树为空的二叉树,左、右子树非空的二叉树,第10页/91,二叉树与树的区
5、别,表达形式(对3个结点) 普通树 二叉树 (a) (b) (c) (d) (e),O,O,O,O,O,O,有两种不同形式,(a),(b),O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,有五种不同形式,第11页/91,二叉树与树的区别(二),观念 二叉树的子树有顺序关系,分左子树和右子树,而树则无此区分; 二叉树的分支度一定为0、1或2,而树的度可大于2。,第12页/91,特殊二叉树,满二叉树 完全二叉树 平衡二叉树 二叉排序树,第13页/91,满二叉树,当二叉树每个分支结点的度都是2,且所有叶子结点都在同一层上,则称其为满二叉树。 若k为二叉树T的深度,且T中共有2k-1个结点
6、(k 1),则称T为满二叉树。 (a) 满二叉树 (b)非满二叉树,第14页/91,完全二叉树,从满二叉树叶子所在的层次中,自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树。 (a)完全二叉树 (b) 非完全二叉树,叶结点只可能出现在层次最大的两层上。,第15页/91,平衡二叉树,二叉树上任一结点的左子树深度减去右子树深度的差值,称为该结点的平衡因子。 任意结点左、右子树的深度之差的绝对值1 ,这样的树称为平衡二叉树。,(a)平衡二叉树 (b)非平衡二叉树,第16页/91,二叉排序树定义,二叉排序树 或者是空二叉树; 或者是: 左子树上所有结点的值均小于根结点的值; 右子树上所有结点的值
7、均大于等于根结点的值; 左、右子树本身又是一棵二叉排序树。,10,5,7,11,14,18,15,15,14,18,5,10,12,13,7,(a)二叉排序树 (b)非二叉排序树,第17页/91,二叉树的性质一,二叉树的第i层上至多有2i-1个结点( i 1)。,利用归纳法证明: i=1时,只有一个结点,对的; 假设对所有的j,1 j i,命题成立, 即在第j层上,至多有2j-1 个结点。 由归纳假设,第i-1层上至多有2i-2 个结点。由于二叉树的每个结点的度至多为2,故第i层上的最大结点数为第i-1层上的最大结点数的2倍,即 22i-2 = 2i-1。,第18页/91,二叉树的性质二,深度
8、为h的二叉树上至多含2h-1个结点(h1)。,证明:由性质一可见,深度为h的二叉树的最大结点数为:,第19页/91,包含n(n0)个结点的二叉树总的分支数为n-1。,二叉树的性质三,证明: 二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子结点与父结点间有且只有一个分支,即除根外每个结点对应一个分支,因此二叉树总的分支数为n-1。,第20页/91,任意二叉树,若含有n0个叶结点、n2个度为2的结点,则必存在关系式n0=n2+1 。,二叉树的性质四,证明:设二叉树含有n1个度为1的结点,则二叉树结点总数显然为: n0 + n1 + n2 (2-2),再看树的分支数,n2个度为2的结点必然
9、有2n2个分支,n1个度为1的结点必然有n1个分支。又因为除根结点外,其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为:,1 + n1 + 2n2 (2-3) 由(2-2)和(2-3)两式可知:n0=n2+1,第21页/91,具有n个结点的完全二叉树的深度为 log2(n)+1。,二叉树的性质五,证明: 假设二叉树的深度为h, 则必有2h-1-1n2h-1, 于是有2h-1n+12h,也就是 2h-1n2h, 从而得到h-1log2(n)h, 于是h=log2(n)+1。,第22页/91,若对含n个结点的完全二叉树从上到下、从左至右进行1至n的编号,则对二叉树中任
10、意一个编号为i的结点: 若i=1,则该结点是二叉树的根,无父结点。否则,编号为i/2的结点为其父结点; 若2in,则该结点无左孩子。否则,编号为2i的结点为其左孩子结点; 若2i+1n,则该结点无右孩子。否则,编号为2i+1的结点为其右孩子结点。 证明:通过对i进行归纳即可得证。,二叉树的性质六,第23页/91,验证性质六,第i个结点就存放在第i个位置上; 第i个结点(i1)的父结点就存放在第 i/2个位置; 第i个结点的左子结点就存放在第2*i的位置;右子存放在第2*i+1的位置(若2i+1n )。,第24页/91,二叉树的链式存储,结点定义: struct BinTreeNode Elem
11、Type data; struct BinTreeNode *leftChild, *rightChild; ; struct BinTreeNode *root; / 定义根结点指针 这里leftChild和rightChild分别为某一结点指向其左孩子和右孩子的指针。对于叶结点或一个新生成的结点而言,其左孩子和右孩子指针都为空值。,第25页/91,利用这种结点形式存储的树一般称为二叉链表。从根结点出发,可以访问二叉树的任何结点。为了能够访问二叉树,必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。,第26页/91,二叉树的遍历,遍历(Traversing)是树形结构的一种重要运
12、算,即按一定的次序系统地访问结构中的所有结点,使每个结点只被访问一次。,遍历的方法很多,常用的有: 前序法(PreOrder) 中序法(InOrder) 后序法(PostOrder),第27页/91,前序法(PreOrder),方法描述: 从根结点a开始访问, 接着访问左子结点b, 最后访问右子结点c。 即:,根,左子,右子,a b c,第28页/91,中序法(InOrder),方法描述: 从左子结点b开始访问, 接着访问根结点a, 最后访问右子结点c。 即:,根,左子,右子,b a c,第29页/91,后序法(PostOrder),方法描述: 从左子结点b开始访问, 接着访问右子结点c, 最
13、后访问根结点a。 即:,根,左子,右子,b c a,第30页/91,二叉树的遍历举例,前序遍历序列: 中序遍历序列: 后序遍历序列:,DGEBHIFCA,DBGEACHFI,ABDEGCFHI,第31页/91,二叉树遍历算法(递归、前序法),void PreOrder(BinTreeNode *t) if (t) Visit( t ); /访问根结点 PreOrder( t-leftChild ); /遍历左子树 PreOrder( t-rightChild ); /遍历右子树 ,前序遍历二叉树的序列为: A B C D E F,第32页/91,二叉树遍历算法(递归、前序法验证),打印A 取A
14、.左子(B) 打印B 取B.左子(C) 打印C 取C.左子(空) 取C.右子(空) 取B.右子(D) 打印D 取D.左子(E) 打印E 取E.左子(空) 取E.右子(空) 取D.右子(F) 打印F 取F.左子(空) 取F.右子(空) 取A.右子(空) 结束,A,B,C,D,E,F,第33页/91,(2)中序遍历 对一颗非空二叉树进行中序遍历时,首先按中序遍历方式访问左子树,然后访问根结点,最后按中序遍历方式访问右子树。中序遍历算法如下: void InOrder(BinTreeNode *t) if(t) ,InOrder( t-leftChild ); / 遍历左子树 Visit( t );
15、 / 访问根节点 InOrder( t-rightChild ); / 遍历右子树,第34页/91,(3)后序遍历 对一颗非空二叉树进行中序遍历时,首先按后序遍历方式访问左子树,然后按后序遍历方式访问右子树,最后访问根结点。后序遍历算法如下: void PostOrder(BinTreeNode *t) if(t) ,PostOrder( t-leftChild ); / 遍历左子树 PostOrder( t-rightChild ); / 遍历右子树 Visit( t ); / 访问根节点,第35页/91,表达式树及应用,在计算机中对表达式进行分析和计算是一项重要的任务。 举例,用二叉树表示
16、表达式: a + b * ( c - d ) 前序遍历序列: 中序遍历序列: 后序遍历序列: 分析: 每个叶结点为运算对象; 每个非叶结点为运算符; 每个子树对应一个子表达式。 表达式处理一般采用后序法,也称“逆波兰”法。 表达式处理规则: 见运算数入栈; 见运算符,取两个栈顶元素运算后再压栈; 直到处理结束。,第36页/91,表达式树应用举例,(1) a b c d 入栈,(2)遇-,c d 出栈, 运算后再压栈;,(3)遇*,(c - d)和 b 出栈,运算后再压栈;,(4)遇+,b*(c-d)和a出栈,运算后再压栈;,(5)e f 入栈,(6)遇/,f e 出栈, 运算后再压栈;,(7)
17、遇-,a+b*(c-d) 和e/f出栈,运算后再压栈。,第37页/91,图的基本概念,图的来源:通信网、交通网等,它表现了数据对象间多对多的联系。在该结构中,数据元素一般称为顶点。 图的定义: 图是对结点的前趋和后继个数不加限制的一种数据结构,它是由顶点集合及顶点间的关系集合组成。一般记作: Graph( V, E ) 其中:V是顶点的有限非空集合;E是顶点之间关系的有限集合。,第38页/91,图例,设图G1 = (V,E) V=v1,v2,v3,v4 E=(v1,v2),(v1,v3), (v2,v1),(v2,v3), (v2,v4),(v3,v1), (v3,v2),(v4,v2) ,第
18、39页/91,有向图、无向图,有向图(Digraph) 图G中顶点的偶对若是有向的,称为有向图。如图G2所示。为示区别, 其偶对用表示。 例 G2=(V,E) V= 1,2,3,4 E=1,2,1,3, 3,4,4,1 无向图(Undigraph) 图G中顶点的偶对若是无向的,称为无向图,其偶对用(vx,vy)表示,如图G1所示。,第40页/91,边、弧,边(Edge) 顶点间的关系可描述为顶点的偶对,也称为顶点的边。记为:(Vx,Vy)。边是无序的,可看成是(Vx,Vy),也可看成是(Vy,Vx)。 弧(Arc) 若顶点间的边是有方向性(有序)的,则称该偶对为弧。记为:Vx,Vy。弧是有序的
19、,Vx,Vy表示从Vx到Vy。 弧头(Head)弧的终点(TerminaL Node)称为弧头(方向前方)。 弧尾(Tail)弧的起始点(Initial Node)称为弧尾(方向后方)。 弧 Vx,Vy表示为,,第41页/91,顶点、邻接点,顶点(Vertex)图中的数据元素(结点)称为顶点。如图G1、G2中的1、2,1,2。 邻接点(Adjacent)无向图中,若边(x,y) E,则x和y互为邻接点;有向图中,若弧x,y E,则y是x的邻接点,反之,不是。,Vx,Vy,x、y互为邻接点,Vx,Vy,y是x的邻接点,第42页/91,顶点的度(Degree),无向图中,顶点的度是以该顶点为一个端
20、点的边的条数。例如,G1中V2的度为3,V4的度为1。 有向图中,以某顶点为弧头的弧的数目称为该顶点的入度(Indegree)。例如G2中顶点1的入度为1。以某顶点为弧尾的弧的数目称为该顶点的出度(Outdegree)。例如G2中顶点1的出度为2。该顶点的度=入度+出度。例如,G2中顶点1的度=2+1=3。,第43页/91,路径、长度,路径(Path) 在图中,从顶点Vx到顶点Vy的顶点序列(Vx,V1,V2,,Vn,Vy)称为从Vx到Vy的路径。路径可能是不唯一的。例如,G1中,V1到V3的路径为:(V1V2V3)或(V1V3);而G2中,1到4的路径为。 长度(Length) 路径的长度是
21、该路径上边或弧的数目。例如,G1中V1到V3的长度为1或2;而G2中1到4的长度为2。,1,3,2,4,G2,o,o,o,o,v1,v2,v3,v4,G1,第44页/91,连通图、强连通图、连通分量,连通图(Connected Graph) 在无向图中,若每一对顶点间都有路径,称此图是连通图。如图G3所示。 连通分量(Connected Component) 无向图中的极大连通子图称为连通 分量。 强连通图(Strongly Connected Graph) 在有向图中,若每对顶点Vx到Vy间都存在Vx到Vy,及从Vy到Vx的路径,则称此图是强连通图。如图G4所示。,第45页/91,子图、生成
22、树,子图 有两个图G和G1,若V1V,E1 E,即V1中的顶点都属于V中的顶点,E1中的关系都属于E中的关系,则称G1是G的子图。G =(V,E),G1=(V1,E1) (图的部分顶点和部分边组成的图) 生成子图、生成树 设G是一个连通图,G中任一包含G的所有顶点的子图称为生成子图。如果该子图是树,则称为G的生成树。G的生成树不是唯一的。一棵有n个顶点的生成树,有且仅有n-1条边(弧)。 (子图包含所有顶点,但不一定包含所有边),第46页/91,网、权,权(Weight) 若图的边或弧带有与之相关的数,称此数为该边或弧的权。权通常用来表示从一个顶点到另一个顶点的距离或费用。 网(Network
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- PPT 非线性 数据结构
链接地址:https://www.31doc.com/p-3102509.html