[工学]04第二章 基本数据结构及其运算下_40学时.ppt

计算机软件技术基础 第二章 数据结构及其运算（下） 2.5 树与二叉树 线性结构中，不管其存储结构如何，数据元素的逻辑位置之间呈线性关系，每一个数据元素通常只有一个前件和一个后件（第一个元素无前件，最后一个元素无后件）。 有些问题，数据元素之间的逻辑关系不能用线性结构明确、方便地描述出来。 例如，一张普通的书目分类单。 图示 书目分类表 分析 非线性结构：至少存在一个结点（数据元素）有多于一个前件或后件的数据结构。 树结构：每一个结点可能有多个后件，但它们的前件却只有一个（第一个结点无前件）。 树结构表示了数据元素之间的层次关系。 2.5.1 树的基本概念 树（tree）是一种常见的非线性数据结构。 树（Tree)的递归定义： 树是n ( n≥0 ) 个结点的有限集。如果 n = 0，称为空树； 如果 n0，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继（后件），但没有直接前驱（前件）； 当n1，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1, T2 ,…, Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。 结点的度(degree)：结点拥有子树数。 叶结点(leaf)：又称为终端结点。度为0的结点。 内部结点：除了根结点与叶子结点以外的所有结点。 树的度：树内各结点的最大值。 孩子(child)：结点的子树的根称为该结点的孩子。 双亲(parent)：相应的该结点为其孩子的双亲结点。 兄弟(sibling)：同一个双亲的孩子之间互称兄弟。 祖先(ancestor)：从根到该结点所经分支上的所有结点。 有一个唯一没有前件（父结点）的结点，称为根。 除了根结点以外，每一个结点都有唯一的前件。 除了根结点以外，每一个结点都通过唯一的途径连到根上。这个途径由根开始，末端就在该结点上，且除根以外，每一个结点都是此途径上的前一个结点的后件（子结点）。 子孙（descendant）：以某结点为根的子树中的任一结点都称为该结点的子孙。 结点层次(level)：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第h层，则其子树的根就在第h+1层。 树的深度（高度）：树中结点的最大层次称为树的深度或高度。 有序树/无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则成为无序树。 算术表达式的树结构表示 在一个算术表达式中，有运算符和运算对象。 举例： 运算符的分类：单目运算符、双目运算符、三目运算符、…、多目运算符。 利用有序树表示一个表达式 利用有序树可以很方便地表示一个表达式。规则如下： 表达式中的运算符为有序树的根结点或内部结点； 每一运算符的所有运算对象为该运算符结点的子树； 所有单变数为叶子结点。 举例 表达式 图示 a*(b+c/d)-e**g*f(x,y,z)的有序树表示 一个表达式的有序树可能不是唯一的 图示 a*b+c*d-(g+h)的表达式树 树的存储方式 树在计算机中通常用多重链表表示。 多重链表中的每一个结点描述了树中对应的结点； 而每个结点的链域数随树中该结点的度而定。 图2.43 树链表中结点的结构（第116页） 分析 由于树中每个结点的度一般是不相同的，所以多重链表中各个结点的链域个数是不相同的。 简化方法：取树的度数作为每个结点的链域个数。 可以验证： 如果用定长结点表示树中的每一个结点，则在一棵具有n个结点且度为k的树中，必定存在 个空链域。 举例 如果用定长结点表示树中的每一个结点，则在一棵具有n个结点且度为k的树中，必定存在 个空链域。 2.5.2 二叉树及其基本性质 1. 什么是二叉树 定义：一棵二叉树是结点的一个有限集，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树L和右子树R的互不相交的二叉树组成。 特点：每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）。 二叉树的五种基本型态： 二叉树的五种基本形态：(a)空二叉树；(b)只有一个根结点的二叉树；(c)只有左子树的二叉树； (d)只有右子树的二叉树；(e)左、右子树均有的二叉树。 二叉树的主要运算 查找二叉树中某个（些）特定结点； 按某种规律有哪些信誉好的足球投注网站二叉树中的全部结点； 找出二叉树中某个结点的前件或者后件； 从二叉树中删去某个子树； 用某二叉树替换指定的树叶。 2. 二叉树的基本性质 性质1 在二叉树的第 i 层上至多有 2i －1个结点。(i ? 1) 性质2 深度为 k 的二叉树至多有 2 k-1个结点(k ? 1)。 性质3 对任何一棵二叉树T, 如果其叶