第9-10讲（树与二叉树）.ppt

树与二叉树 二叉树的应用 堆排序(Heap Sort)? 基本思想：堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。 * 信息学奥赛进阶教程（第9-10讲） 栈、队列属于线性结构。在这种结构中，不管其存储方式（顺序和链式）如何，数据元素的逻辑位置之间呈线性关系，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。 但也有很多问题数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个结点（数据元素）有多于一个前驱或后继的数据结构称为非线性结构。具有非线性结构特征的数据结构有两种 ????????????? ⑴树，⑵图 树 一、.树的概念 1、树的定义 树是一种常见的非线性的数据结构。树的递归定义如下： 树是n(n0)个结点的有限集，这个集合满足以下条件： ⑴有且仅有一个结点没有前驱（父亲结点），该结点称为树的根； ⑵除根外，其余的每个结点都有且仅有一个前驱； ⑶除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）； 由上述定义可知，树结构没有封闭的回路。 2、结点的分类 结点一般分成三类 ⑴根结点：没有父亲的结点。在树中有且仅有一个根结点。 ⑵分支结点：除根结点外，有孩子的结点称为分支结点。b，c，x，t，d，i。分支结点亦是其子树的根； ⑶叶结点：没有孩子的结点称为树叶。w，h，e，f，s，m，o，n，j，u为叶结点。 根结点到每一个分支结点或叶结点的路径是唯一的。从根r到结点i的唯一路径为rcti。 3、有关度的定义 ?? ?⑴结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。 ?? ⑵树的度：所有结点中最大的度称为该树的度(宽度）。图中树的度为3。 4、树的深度（高度） 树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。 树中最大的层次称为树的深度，亦称高度。图中树的深度为5。 二、树的表示方法和存储结构 1、树的表示方法 树的表示方法一般有两种： ?????⑴自然界的树形表示法：用结点和边表示树，例如下图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。 ?⑵括号表示法： 先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式 （r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u））） 2、树的存储结构 Const n=树的度； max=结点数的上限； Type node=record {结点类型} data：integer； {数据域} ch：array[1‥n] of integer； {指向各儿子的下标} end； treetype=array[1..max]of node； Var tree：treetype； {树数组} ⑴静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n 为树的度)的数组，分别存储该结点的每一个儿子的下标 树的存储结构一般有两种 例如图的树，其记录数组如下。其中Tree[i].ch[j]=0说明结点i的第j个儿子不存在。(编号按层编号) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ⑵动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成，其表示方法如下： Const n=树的度； Type treetype=↑node； {结点类型} node=record