数据结构与算法分析 第5章

《数据结构与算法分析 第5章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章树5.1树的概念5.2二叉树的定义5.3二叉树的性质5.4二叉树的存储结构5.5二叉树的遍历5.6线索二叉树5.7树和二叉树的转换及树的存储结构5.8哈夫曼树及其应用5.1树的概念5.1.1树的定义树是一种数据结构，表示为TREE=（D，R）；其中：D是具有相同特性的数据元素的集合；R是元素集合D上的关系集合，如果D中只含有一个数据元素，则R为空集。或者用递归定义为：树是N（N>0）个结点的有限集合，其唯一关系具有下列属性：集合中存在唯一的一个结点，称为树根，该结点没有前驱；除根结点外，其余结点分为M（M≥0）

2、个互不相交的集合，其中每一个集合都是一棵树，并称其为根的子树。5.1树的概念5.1.2基本术语一个结点的子树个数称为该结点的度（degree）一棵树中结点度的最大值称为该树的度度为零的结点称为叶子（leaf）或者终端结点度不为零的结点称为分支结点或者非终端结点除根结点之外的分支结点统称为内部结点树中结点的后继结点称为儿子（child）或者儿子结点，简称儿子结点的前驱结点称为儿子的双亲（parents）或者父亲结点，简称父亲同一个父亲的儿子互称为兄弟（sibling）5.1树的概念若树中存在一个结点序列k1k2k3…k

3、j，使得ki是ki+1的父亲（1≤i＜j），则称该结点序列是从k1到kj的一条路径（path）或者道路路径的长度等于j-1，它是该路径所经过的边（即连接两个结点的线段）的数目若树中结点k到ks存在一条路径，则称k是ks的祖先（Ancestor），ks是k的子孙（Descendant）结点的层数（level）是从根开始算起的。设根结点的层数为1，其余结点的层数等于其父亲结点的层数加1树中结点的最大层数称为树的高度（Height）或者深度（Depth）5.1树的概念若把树中每个结点的各子树看成从左到右有次序的（即不能互换

4、），则称该树为有序树（OrderedTree）；否则称为无序树（UnorderedTree）森林（Forest）是m（m≥0）棵互不相交树的集合树形结构是非线性结构祖先与子孙的关系则是对父子关系的延伸，其定义了树中结点的纵向次序如果规定k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边，则定义了树中结点的横向次序5.2二叉树的定义二叉树是由n（n≥0）结点的有限集合，此集合或者为空，或者由一个根结点加上两棵分别称为左、右子树的，互不相交的二叉树组成二叉树可以为空集，因此根可以有空的左子树或

5、者右子树，亦或者左、右子树皆为空从二叉树定义中可以看出，二叉树结构与一般树结构区别如下：（1）二叉树可以为空树，即不包含任何结点；一般树至少应有一个结点。（2）二叉树区别于度数为2的有序树，在二叉树中允许某些结点只有右子树而没有左子树；而有序树中，一个结点如果没有第一子树就不可能有第二子树的存在。5.3二叉树的性质5.3.1二叉树性质性质1二叉树第i（i≥1）层上的结点数最多为2i-1性质2高度为k的二叉树最多有2k-1个结点性质3对任何二叉树T，设n0、n1、n2分别表示度数为0、1、2的结点个数，则n0=n2+1

6、5.3二叉树的性质性质4具有n个结点的完全二叉树（包括满二叉树）的高度为（或者）性质5满二叉树原理非空满二叉树的叶结点数等于其分支结点数加1性质6一棵非空二叉树空子树的数目等于其结点数目加15.3二叉树的性质5.3.2二叉树的抽象数据类型下列给出一个二叉树结点的JAVA接口，称之为BinNode。BinNode类中存储了指向Object类的引用。创建二叉树时，可以根据需要而采用实际的数据类型。成员函数包括返回元素的值，返回左、右结点指针，设置元素的值，以了标志该结点是否为叶结点。interfaceBinNode{//

7、二叉树结点的抽象数据类型//返回并设置元素值publicObjectelement();publicObjectsetElement(Objectv);5.3二叉树的性质//返回并设置左孩子publicBinnodeleft();publicBinnodesetLeft(BinNodep);//返回并设置右孩子publicBinnoderight();publicBinnodesetRight(BinNodep);//判断是否为叶结点publicbooleanisLeaf();}//interfaceBinNode5

8、.4二叉树的存储结构5.4.1二叉树顺序存储结构二叉树的顺序存储结构是把二叉树的所有结点按照一定的次序顺序存储到一组包含n个存储单元的空间中二叉树顺序存储的原则是：不管给定的二叉树是不是完全二叉树，都看作完全二叉树，即按完全二叉树的层次次序（从上到下，从左到右）把各结点依次存入数组中5.4二叉树的存储结构在顺序存储结构中，由某结点的存储单元地址