数据结构-第八周-树的存储方法ppt课件

数据结构与算法,引入：,逻辑结构,逻辑结构是对数据对象中数据元素之间逻辑关系描述。,数据对象是具有相同性质的数据元素的集合。,数据对象,逻辑结构,根据数据元素之间逻辑关系的不同，逻辑结构分为以下四类：,四类基本的逻辑结构集合结构、线性结构、树型结构、图状结构,集合结构,定义：集合结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。,例如：,线性结构,定义：线性结构中的数据元素之间存在着一对一的线性关系。,线性结构特点,数据元素的非空有限序列中，存在唯一的首元素和唯一的尾元素，首元素无直接前驱，尾元素无直接后继，其它每个数据元素均有唯一的直接前驱和唯一的直接后继。,线性结构,线性表、栈、队列的逻辑结构都是线性结构,树型结构,定义：树型结构中的数据元素之间存在着一对多的层次关系。,图状结构,定义：图状结构中的数据元素之间存在着多对多的任意关系。,例如：,但现实生活中的许多事物之间的关系并非只是一对一的关系。,在前面的内容中，我们学习了线性结构，线性结构的逻辑特点是数据元素之间存在着一对一的逻辑关系。,例如：一个家庭成员之间的关系：,例：一个学校的组织结构,学院,磁盘目录结构,树型结构特点,树型结构是一种非线性的逻辑结构，数据元素之间具有一对多的层次关系。,树的定义,树：n（n0）个结点的有限集合。当n0时，称为空树；当n0时，称为非空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为根的结点；当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的有限集合T1,T2,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。,树的定义是采用递归定义，树的概念中又用到了树的概念。,A,只有根结点的树,根,每棵子树也是树，每棵子树也有自己的根节点和若干子树,树的逻辑结构的特点,1、树是一种分支或层次结构，每个结点都有且仅有一个直接前驱（除了根结点），每个结点都零个或多个直接后继。（一对多）。2、除根结点外的其它结点，都存在唯一一条从根到该结点的路径。,(a)一棵树结构(b)一个非树结构(c)一个非树结构,树形表示法嵌套圆括号表示法缩进表示法嵌套集合表示法,树的表示方法,树形表示法：,直观形象,嵌套圆括号表示法：,根作为由子树森林组成的表的名字写在表的左边,A（B，C（E,F,G,H），D）,缩进表示法：,嵌套集合表示法：,B,D,E,G,F,H,树的基本术语,结点：结点是指树中的一个数据元素。结点的度：结点所拥有的子树的个数。树的元数：树中限制各结点度的最大值为m。二元树(m=2)、三元树(m=3),叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。,树的基本术语,孩子、双亲：树中某结点的子树的根结点称为这个结点的孩子结点（或儿子结点），这个结点称为它孩子结点的双亲结点（或父亲结点）；兄弟：具有同一个双亲的孩子结点互称为兄弟。,树的基本术语,祖先结点：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。子孙结点：在某一结点的子树中的所有结点是这个结点的子孙。,树的基本术语,结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点中的最大层次是这棵树的高度，也称高度。,树的基本术语,层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。,树的基本术语,有序树、无序树：如果一棵树中结点的各子树从左到右是有次序要求的，称这棵树为有序树；反之，对次序无要求，可任意排列，称为无序树。,数据结构中讨论的一般都是有序树,树的基本术语,森林：m(m0)棵互不相交的树的集合。,树的基本术语,三棵树组成的森林,已知一棵树的集合为,，请画出这棵树，并回答下列问题：（1）哪个是根结点？结点C的度是多少？（2）哪些是叶子结点？（3）哪个是结点G的双亲？（4）哪些是结点G的祖先？（5）哪些是结点G的孩子？（6）哪些是结点E的子孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？（8）结点B和N的层次号分别是什么？（9）树的深度是多少？树的元数是多少？（10）以C为根的子树的深度是多少？,树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲结点,无后继,无孩子结点,一个前驱,一个后继,一个双亲,多个孩子,一对一一对多,二叉树的定义,二叉树是n(n0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。,二叉树的特点,每个结点最多有两棵子树；（不存在度大于2的结点）；二叉树是有序的，左子树和右子树次序不能颠倒（有序树）,注意：二叉树和树是两种树结构。例如：上面两个树按一般树的定义它们是同一个树；而对于二叉树来讲，它们是不同的两个树。,二叉树的五种形态,练习：如果只有三个结点，二叉树形态如何？,根结点同时有左右子树的二叉树,根结点仅有右子树的二叉树,空的二叉树,仅有根结点的二叉树,根结点仅有左子树的二叉树,具有3个结点的树和具有3个结点的二叉树的形态,特殊的二叉树,斜树1.所有结点都只有左子树的二叉树称为左斜树；2.所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。,1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。,斜树的特点：,满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树（即：所有的分支结点的度数都为2），并且所有叶子结点都在同一层上。,满二叉树的特点：,叶子只能出现在最下一层；只有度为0和度为2的结点。,特殊的二叉树,满二叉树,不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多,特殊的二叉树,完全二叉树一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1in）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。,特殊的二叉树,在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点,特殊的二叉树,1.叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面；2.完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。3.深度为k的完全二叉树在k-1层上一定是满二叉树。4.在同样结点个数的二叉树中，完全二叉树的深度最小。,完全二叉树的特点,特殊的二叉树,二叉树的基本性质,性质1二叉树的第i层上最多有2i-1个结点（i1）,证明：使用归纳法证明。,二叉树的基本性质,性质1二叉树的第i层上最多有2i-1个结点（i1）,证明：当i=1时，第1层只有一个根结点，而2i-1=20=1，结论显然成立。假定i=k（1ki）时结论成立，即第k层上至多有2k-1个结点，则i=k+1时，因为第k+1层上的结点是第k层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第k+1层上最大结点个数为第k层上的最大结点个数的二倍，即22k-12k。结论成立。,性质2一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。,证明：由性质1，深度为k的二叉树中结点个数最多=2k-1；每一层至少要有一个结点，因此深度为k的二叉树，至少有k个结点。,深度为k且具有2k-1个结点的二叉树一定是满二叉树，深度为k且具有k个结点的二叉树不一定是斜树。,性质3在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0n21,证明:设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：nn0n1n2在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有：nn12n21因此可以得到：n0n21。,n个结点的满二叉树有多少个叶子结点？,性质3在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0n21。,性质4具有n个结点的完全二叉树的深度为log2n+1,证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立2k-1n2k,因此，k-1log2n1，则结点i的双亲结点的编号为i/22）如果2in，则结点i的左孩子结点的编号为2i；如果2in，则结点i无左孩子结点(结点i为叶子结点)；3）如果2i+1n，则结点i的右孩子结点的编号为2i+1；如果2i+1n，则结点i无右孩子结点。,对一棵具有n个结点的完全二叉树中从1开始按层序编号，则结点i的双亲结点为i/2结点i的左孩子为2i；结点i的右孩子为2i1。,练习：一棵深度为6的满二叉树有个叶子和个分支结点。练习：设一棵完全二叉树具有36个结点，则此完全二叉树有个叶子结点，有个度为2的结点。,为何重点研究二叉树？,问题转化：1、二叉树的结构简单，规律性最强。2、可以将树转换为唯一对应的二叉树，从而利用二叉树解决树的有关问题。,转换步骤：把结点的第一孩子做为其左孩子把结点的右邻近兄弟转为其右孩子,A,二叉树,1、将树转换为二叉树,由于根结点没有兄弟，所以普通树转换成二叉树后，二叉树根结点没有右树,2、将二叉树转换为树,转换步骤：把所有右孩子都变成其双亲的兄弟,A,3、森林转换为二叉树,转换步骤：各树要先各自转为二叉树依次连接到前一个二叉树的右子树上,A,E,G,步骤：1、将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线断开，使之变成孤立的二叉树。2、将孤立的二叉树转换成树,4、二叉树转换为森林,树的存储结构,实现树的存储结构，关键是什么?,树中结点之间的逻辑关系是什么?,思考问题的出发点：如何表示结点的双亲和孩子,如何表示树中结点之间的逻辑关系。,存储结构?,数据元素以及数据元素之间的逻辑关系在存储器中的表示。,普通树有三种常用存储方式：双亲表示法孩子表示法孩子兄弟表示法,1、用双亲表示法来存储树,方法：用一组连续空间来存储树的结点，数组中的一个数组元素对应树中的一个结点，内容包括结点的数据信息以及该结点的双亲在数组中的下标。,下标dataparent,方便下层到上层搜索。,双亲表示法,容易由孩子结点找到双亲结点。缺点：求结点的孩子时需要遍历整个存储结构,typedefstructElemtypedata;intparent;/双亲位置域PTNode;,#defineMAXSIZE100,结点结构:,typedefstructPTNodeNodesMAXSIZE;intr,n;/根结点的位置和结点个数PTree;,树结构:,A,B,C,D,E,F,G,0A-11B02C03D04E25F26G5,r=0n=7,dataparent,链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。,如何表示孩子？,孩子链表表示法,缺点：浪费空间,A,B,C,D,E,F,G,H,I,优点：1、只需一个指针指向根结点；2、方便查看孩子节点,1、某结点的第一个孩子是惟一的2、某结点的右兄弟是惟一的,孩子兄弟表示法,typedefstructTNodeElemTypedata;structTNode*firstchild,*rightsibing;TNode,*tptr;,结点结构,data：数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；rightsibing：指针域，指向该结点的右兄弟结点。,孩子兄弟表示法,root,由root指针找到根结点。由结点的firstchild域找到其第一个孩子结点由结点的rightsibing域找到其右兄弟结点,孩子兄弟表示法,顺序存储结构,二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系双亲孩子关系。,如何利用数组下标来反映结点之间的逻辑关系?,利用性质5完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系。,二叉树的存储结构,完全二叉树的顺序存储,以编号为下标,对一棵具有n个结点的完全二叉树中从1开始按层序编号，则结点i的双亲结点为i/2结点i的左孩子为2i；结点i的右孩子为2i1。,一般二叉树的顺序表示,一般二叉树的顺序存储,以编号为下标,按照完全二叉树编号,优点：可以由双亲结点快速找到孩子节点，由孩子结点快速找到双亲结点。,一棵斜树的顺序存储会怎样呢？,性质2：一棵深度为k的二叉树，最多有2k-1个结点,一棵二叉树改造后成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。,二叉树的顺序存储结构一般仅存储完全二叉树,一个深度为k的右斜树，顺序存储k个结点需分配多少个存储单元呢？,二叉树的双链式存储,基本思想：每个结点包含1个数据域，2个指针域，分别指向该结点的左孩子结点和右孩子结点。,结点结构：,其中，data：数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。,typedefstructNode/结点结构ElemTypedata;structNode*lchild,*rchild;BNode,*BiTree;/结点类型别名和指针类型别名,二叉树的