文档介绍：第第5 5章章树树 树的概念 二叉树的定义 二叉树的性质 二叉树的存储结构 二叉树的遍历 线索二叉树 树和二叉树的转换及树的存储结构 哈夫曼树及其应用 树的概念树的概念? 树的定义?树是一种数据结构,表示为 TREE= (D,R); ?其中: D是具有相同特性的数据元素的集合; R 是元素集合 D上的关系集合,如果 D中只含有一个数据元素,则 R为空集。?或者用递归定义为: ?树是 N( N>0 )个结点的有限集合,其唯一关系具有下列属性: ?集合中存在唯一的一个结点,称为树根,该结点没有前驱;除根结点外,其余结点分为 M (M≥0)个互不相交的集合,其中每一个集合都是一棵树,并称其为根的子树。 树的概念树的概念? 基本术语?一个结点的子树个数称为该结点的度( degree ) ?一棵树中结点度的最大值称为该树的度?度为零的结点称为叶子( leaf )或者终端结点?度不为零的结点称为分支结点或者非终端结点?除根结点之外的分支结点统称为内部结点?树中结点的后继结点称为儿子( child )或者儿子结点, 简称儿子?结点的前驱结点称为儿子的双亲( parents )或者父亲结点,简称父亲?同一个父亲的儿子互称为兄弟( sibling ) 树的概念树的概念?若树中存在一个结点序列 k 1k 2k 3…k j,使得 k i是k i +1的父亲(1≤i<j), 则称该结点序列是从 k 1到k j的一条路径(path )或者道路?路径的长度等于 j-1 ,它是该路径所经过的边(即连接两个结点的线段)的数目?若树中结点 k到k s存在一条路径,则称 k是k s的祖先(Ancestor ), k s是k的子孙( Descendant ) ?结点的层数( level )是从根开始算起的。设根结点的层数为 1,其余结点的层数等于其父亲结点的层数加 1 ?树中结点的最大层数称为树的高度( Height )或者深度(Depth ) 树的概念树的概念?若把树中每个结点的各子树看成从左到右有次序的(即不能互换),则称该树为有序树( Ordered Tree ); 否则称为无序树( Unordered Tree ) ?森林( Forest )是m(m≥0)棵互不相交树的集合?树形结构是非线性结构?祖先与子孙的关系则是对父子关系的延伸,其定义了树中结点的纵向次序?如果规定 k 1和k 2是兄弟,且 k 1在k 2的左边,则 k 1的任一子孙都在 k 2的任一子孙的左边,则定义了树中结点的横向次序 二叉树的定义二叉树的定义?二叉树是由 n(n≥0)结点的有限集合,此集合或者为空, 或者由一个根结点加上两棵分别称为左、右子树的,互不相交的二叉树组成?二叉树可以为空集,因此根可以有空的左子树或者右子树,亦或者左、右子树皆为空?从二叉树定义中可以看出,二叉树结构与一般树结构区别如下: (1 )二叉树可以为空树,即不包含任何结点;一般树至少应有一个结点。(2)二叉树区别于度数为 2的有序树,在二叉树中允许某些结点只有右子树而没有左子树;而有序树中,一个结点如果没有第一子树就不可能有第二子树的存在。 二叉树的性质二叉树的性质? 二叉树性质?性质 1 二叉树第 i(i≥1)层上的结点数最多为 2 i-1?性质 2 高度为 k的二叉树最多有 2 k -1个结点?性质 3 对任何二叉树 T,设n 0、n 1、n 2分别表示度数为 0、1、2的结点个数,则 n 0 =n 2 +1 1 log 2?n 二叉树的性质二叉树的性质?性质 4 具有 n个结点的完全二叉树(包括满二叉树)的高度为(或者) ?性质 5 满二叉树原理非空满二叉树的叶结点数等于其分支结点数加 1 ?性质 6 一棵非空二叉树空子树的数目等于其结点数目加 1 ?? 1 log 2?n?? 1 log 2?n 二叉树的性质二叉树的性质? 二叉树的抽象数据类型?下列给出一个二叉树结点的 JAVA 接口,称之为 BinNode 。 BinNode 类中存储了指向 Object 类的引用。创建二叉树时, 可以根据需要而采用实际的数据类型。成员函数包括返回元素的值,返回左、右结点指针,设置元素的值,以了标志该结点是否为叶结点。?interface BinNode { // 二叉树结点的抽象数据类型?//返回并设置元素值?public Object element(); ?public Object setElement (Objec