1个结点.ppt

　第6章　树和二叉树 【本章教学目的、要求】 1、理解树的定义和基本操作； 2、理解二叉树和哈夫曼树的定义及其特点； 3、理解常见实例的编程思想。 主要内容 6.0 前言 6.1 树的定义和基本操作 6.2 二叉树 6.3 哈夫曼树和判定树 6.4 应用举例及分析 习题 6.0 前言 树形结构中结点之间有分支关系，又具有层次关系，它非常类似于自然界中的树。树形结构在现实世界中广泛存在： 例如家谱、各单位的行政组织机构等都可用树来表示。 树在计算机领域中也有着广泛的应用： DOS和Windows操作系统中对磁盘文件的管理就采用树形目录结构。 在数据库中，树结构也是数据的重要组织形式之一。本章重点讨论二叉树的存储结构及其各种操作。 6.1 树的定义和基本操作 6.1.1 树的定义 6.1.2　基本术语 6.1.3　树的基本操作 6.1.1 树的定义（1） 树(tree)是n (n ≥ 0)个结点的有限集合。当n = 0时，集合为空集，称为空树。在任意一棵非空树T中： ① 有且仅有一个特定的，称为根(root)的结点。 ② 当n 1时，除根结点以外的其余结点可分成m (m 0)个互不相交的有限集合T1，T2，…，Tm。其中每一个集合本身又是一棵树，并称其为根的子树(subtree)。 例如，图6.1 (a)是只有一个根结点的树，(b)是有13个结点的树，其中A是根结点，其余结点分成三个互不相交的子集： T1 = {B, E, F, K, L}，T2 = {C, G}，T3 = {D, H, I, J, M}。T1, T2, T3都是根的子树，它们本身也是一棵树。 6.1.1 树的定义（2） 树的定义具有递归性，递归定义描述了树的递归特性： 即一棵树是由根及若干棵子树构成的，而子树又可由更小的子树构成。 在树中，只有根结点没有直接前驱，而根结点以外的其余结点均有一个且只有一个直接前驱。 基于树的这一特点，我们在画树的示意图时一般都将根结点画在最上面，而结点之间的分支箭头就都省略了，前面图6.1(b)中的树通常画成图6.1 (c)。 图6.1 树的示例 6.1.2　基本术语（1） 树的结点：包括一个数据元素及若干指向其子树的分支。 结点的度(degree)：结点拥有的子树个数称为。 树中所有结点的度的最大值为该树的度。 度为0的结点称为叶子结点(leaf)或终端结点。 度不为0的结点称为非叶子结点或非终端结点。 孩子结点(child)：结点的子树的根；该结点是其孩子结点的双亲结点(parent)。 具有同一双亲结点的孩子结点之间互称为兄弟(sibling)。 某结点的祖先是指从根结点到该结点所经分支上的所有结点。 6.1.2　基本术语（2） 以某结点为根的子树中的所有结点都称为该结点的子孙。 结点的层次(level)从根开始算起，根为第一层，根的孩子为第二层，某结点所在的层从根开始向下计算。 在树的同一层上而双亲结点不同的结点互为堂兄弟。 树中结点的最大层次称为树的深度(depth)或高度。 6.1.2　基本术语（3） 例如，图6.1(c)中，A是根结点，A的度为3，E的度为2，L的度为0。结点K，L，F，G，M，I，J都是叶子结点，其他都是非叶子结点。A有三棵子树，这三棵子树的根B，C，D是A的孩子结点，A是B，C，D的双亲结点。H，I，J的双亲是D，所以H，I，J三个结点互为兄弟结点。H和G都在树的同一层上，但它们的双亲不是同一个结点，所以它们是堂兄弟关系。树的最大层次共四层，因此该树的深度为4。 6.1.2　基本术语（4） 如果将树中结点的各个子树看成从左至右是有序的(即不能互换)，则称该树为有序树，否则称为无序树。 当用树来描述家谱时，应将树看成是有序树，有序树中某结点最左边子树的根称为该结点的第一个孩子，最右边子树的根称为最后一个孩子。当用树来描述某单位的行政组织结构时，可将树看成是无序树。 森林(forest)是m(m≥0) 棵互不相交的树的集合，树和森林的概念很密切，删去一棵树的根，就得到一个森林。图6.3就是一个森林的例图。 图6.3 森林示例 6.1.3　树的基本操作 （1） TREEEMPTY(T)判树空。若T为空树，返回TRUE，否则返回FALSE。 （2） ROOT(T) 求根。返回树T的根结点地址。若T为空树，返回一特殊值。 （3） TREEDEPTH(T) 求树的深度。返回树T的深度。 （4）VALUE(T, e) 求结点。e是树T中的结点，函数返回e结点地址。 （5） PARENT(T, e) 求结点的双亲。e是树T中的结点，当e是非根结点时，函数返回e结点的双亲结点地址。 （6）CHILD(T, e, i) 求结点的孩子。e是树T中的结点，函数返回e结点的第