数据结构-清华出版社_张世和第6章

第6章树和二叉树6.1树的定义和基本操作6.2二叉树6.3树和森林6.4哈夫曼树和判定树6.5应用举例及分析习题本章和下一章分别介绍两种重要的非线性结构：树和图。树形结构中结点之间有分支关系，又具有层次关系，它非常类似于自然界中的树。树形结构在现实世界中广泛存在，例如家谱、各单位的行政组织机构等都可用树来表示。树在计算机领域中也有着广泛的应用，DOS和Windows操作系统中对磁盘文件的管理就采用树形目录结构；在数据库中，树结构也是数据的重要组织形式之一。本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树的转换关系，最后介绍树的几个应用实例。6.1树的定义和基本操作6.1.1树的定义树(tree)是n(n≥0)个结点的有限集合。当n=0时，集合为空集，称为空树。在任意一棵非空树T中：①有且仅有一个特定的，称为根(root)的结点。②当n1时，除根结点以外的其余结点可分成m(m0)个互不相交的有限集合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树的定义具有递归性，递归定义描述了树的递归特性：即一棵树是由根及若干棵子树构成的，而子树又可由更小的子树构成。下面给出的几个结构都不是树，因为它们都不满足树的定义。图6.2(a)不是树，因为这三个结点中出现了两个可称为根的结点，而树只能有一个根结点。图6.2(b)和(c)的结构也不是树，如果把其中某个结点看成根结点的话，其余的结点构成的子树出现了相交的情况。从图6.1和图6.2可看出，树有层次关系，也有分支关系，树中无环路存在。在树中，只有根结点没有直接前驱，而根结点以外的其余结点均有一个且只有一个直接前驱。基于树的这一特点，我们在画树的示意图时一般都将根结点画在最上面，而结点之间的分支箭头就都省略了，前面图6.1(b)中的树通常画成图6.1(c)。图6.26.1.2基本术语树的结点包括一个数据元素及若干指向其子树的分支。结点拥有的子树个数称为结点的度(degree)。树中所有结点的度的最大值为该树的度。度为0的结点称为叶子结点(leaf)或终端结点。度不为0的结点称为非叶子结点或非终端结点。结点的子树的根称为该结点的孩子结点(child)，该结点是其孩子结点的双亲结点(parent)。具有同一双亲结点的孩子结点之间互称为兄弟(sibling)。某结点的祖先是指从根结点到该结点所经分支上的所有结点。以某结点为根的子树中的所有结点都称为该结点的子孙。结点的层次(level)从根开始算起，根为第一层，根的孩子为第二层，某结点所在的层从根开始向下计算。在树的同一层上而双亲结点不同的结点互为堂兄弟。树中结点的最大层次称为树的深度(depth)或高度。例如，图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。如果将树中结点的各个子树看成从左至右是有序的(即不能互换)，则称该树为有序树，否则称为无序树。当用树来描述家谱时，应将树看成是有序树，有序树中某结点最左边子树的根称为该结点的第一个孩子，最右边子树的根称为最后一个孩子。当用树来描述某单位的行政组织结构时，可将树看成是无序树。森林(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结点的第i个孩子结点的地址。(7)CREATE_TREE(T,T1,T2,…,Tk)建树操作。当k≥1，建立一棵以T为根，以T1,T2,…,Tk为第1,2,…,k棵子树的树。6.2二叉树二叉树是树的一个重要类型，许多实际问题抽象出来的数据结构往往是二叉树的形式，一般的树也可转换为二叉树，而且二叉树的存储结构及其操作都较为简单，因此二叉树显得特别重要。6.2.1二叉树的定义和基本操作二叉树(binarytree)是n(n≥0)个结点的有限集合，n=0时为空集，称为空二叉树；n≠0时，二叉树由一个根结点及两棵互不相交、分别称为左子树和右子树的二叉树组成。二叉树和树在概念上相同的是都有一个且仅有一个根结点，根结点无前驱结点，叶子结点无后继结点。不相同的是二叉树中每个结点的度小于等于2，而且二叉树的子树有左右子树之分。二叉树的定义也是一个递归定义，表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。由此，二叉树可以有五种基本形态，如图6.4所示。前面讨论的有关树的术语也都适用于二叉树。图6.4二叉树的基本操作和树的基本操作大致相同，主要的基本操作如下：(1)TREEEMPTY(BT)判二叉树空。若BT为空树，返回TRUE，否则，返回FALSE。(2)ROOT(BT)求根。返回二叉树BT的根结点地址。若BT为空树，返回一特殊值。(3)TREEDEPTH(BT)求二叉树的深度。返回二叉树BT的深度。(4)VALUE(BT,e)求结点。e是二叉树BT中的结点，函数返回e结点地址。(5)PARENT(BT,e)求结点的双亲。e是二叉树BT中的结点，当e是非根结点时，函数返回e结点的双亲结点地址。(6)LCHILD(BT,e)求结点的左孩子。e是二叉树BT中的结点，函数返回e结点的左孩子结点的地址。(7)RCHILD(BT,e)求结点的右孩子。e是二叉树BT中的结点，函数返回e结点的右孩子结点的地址。(8)CREATE_BT(BT,LBT,RBT)建二叉树操作。建立一棵以BT为根，以二叉树LBT、RBT分别为BT的左、右子树的二叉树。6.2.2二叉树的性质性质1二叉树第i层上的结点数目至多为2i-1(i≥1)。例如，一棵二叉树第4层上的结点数至多是24-1=23=8个。可用数学归纳法证明此性质：i=1时，只有一个根结点。显然2i-1=20=1，命题成立。假设对所有的j(1≤ji)，命题成立，即第j层上至多有2j-1个结点。可以证明j=i时，命题也成立。根据归纳假设，第i-1层上至多有2i-2个结点，由于二叉树的每一个结点的度最大为2，故在第i层上的结点数，至多是第i-1层上最大结点数的2倍，即2×2i-2=2i-1。性质2深度为k的二叉树至多有2k-1个结点(k≥1)。利用性质1可得，深度为k的二叉树的结点数至多为∑(第i层上的最大结点数)=∑2i-1=2k-1ki=1ki=1性质3在任何一棵二叉树中，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明设n1为二叉树中度为1的结点数，n为二叉树中总的结点数，则n=n0+n1+n2(6-1)设B为二叉树中的分支数目，从入支角度看，即前驱结点的角度看，二叉树中除了根结点外的其余结点都有一个且仅有一个前驱结点，即占有一个分支，则B=n-1(6-2)从出支角度看，即后继结点的角度看，度为0的结点无后继结点，即不占分支，度为1的结点有一个后继结点，即占有一个分支，度为2的结点有两个后继结点，即占有两个分支，所以B=n0×0+n1×1+n2×2=n1+2n2(6-3)由式(6-2)和(6-3)得n=n1+2n2+1(6-4)由式(6-1)和(6-4)得n0=n2+1为了介绍二叉树的性质4、性质5、性质6，首先介绍两种特殊形态的二叉树：完全二叉树(comlpetebinarytree)和满二叉树(fullbinarytree)。一棵深度为k且有2k-1个结点的二叉树称为满二叉树，图6.5(a)是一棵深度为4的满二叉树。满二叉树中每一层上的结点数都达到最大值。满二叉树中不存在度为1的结点，每一个结点均有两棵高度相同的子树，叶子结点都在最下面的同一层上。若在一棵深度为k(k1)的二叉树中，第1层到第k-1层构成一棵深度为k-1的满二叉树，第k层的结点不满2k-1个结点，而这些结点都满放在该层最左边，则此二叉树称为完全二叉树。图6.5(b)是一棵完全二叉树。图6.5(c)和图6.5(d)不是完全二叉树。完全二叉树中的叶子结点只可能出现在二叉树中层次最大的两层上。最下一层的结点一定是从最左边开始向右满放的。且若某个结点没有左孩子，则它一定没有右孩子。满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。图6.5性质4具有n个结点的完全二叉树的深度为log2n+1。证明设所求完全二叉树的深度为k，则它的前k-1层可视为深度为k-1的满二叉树，共有2k-1-1个结点，所以该完全二叉树的总结点数n一定满足下列式子：n2k-1-1(6-5)根据性质2，可确定n≤2k-1(6-6)由式(6-5)和(6-6)得2k-1-1n≤2k-12k-1≤n2k于是k-1≤log2nk(6-7)因为k是整数，所以k-1=log2n，k=log2n+1性质5对一棵有n个结点的完全二叉树的结点按层自左向右编号，则对任一编号为i(1≤i≤n)的结点有下列性质：(1)若i=1，则结点i是二叉树的根，若i1，则结点i的双亲结点是i/2；(2)若2i≤n，则结点i有左孩子，左孩子的编号是2i，否则结点i无左孩子，并且是叶子结点；(3)若2i+1≤n，则结点i有右孩子，右孩子的编号是2i+1，否则结点i无右孩子。这个性质是一般二叉树顺序存储的重要基础。性质6对一棵有n个结点的完全二叉树的结点按层自左向右编号，从编号为1的根结点开始到编号为n/2的结点为止，都是有孩子结点的非叶子结点，余后的结点均是叶子结点。n/2编号的结点可能只有左孩子结点，可能是既有左孩子结点又有右孩子结点。对性质5和性质6，读者可在任何一棵完全二叉树上获得验证。6.2.3二叉树的存储结构1．顺序存储结构顺序存储就是用一组地址连续的存储单元来存放一棵二叉树的结点。显然，必须要按规定的次序来存放，这种次序应能反映结点之间的逻辑关系(父子关系)，否则二叉树上的基本操作在顺序存储结构上难以实现。若对任意一棵完全二叉树上的结点按层自左向右一一存入向量中，根据上述性质5可知，完全二叉树中结点之间的逻辑关系清楚地通过结点在向量中的序号位置准确地反映出来。图6.6(a)就是一棵完全二叉树的顺序存储结构示意图。对于一般二叉树只能将其“转化”为完全二叉树后，按照完全二叉树的顺序存储方式将结点存入向量中。转化的方法是在非完全二叉树的“残缺”位置上增设“虚结点”。如图6.6(b)所示是一棵一般二叉树，只有将它“完全化”以后将结点顺序存入向量中才能通过结点的序号位置来确定结点之间的逻辑关系。图中“∧”表示不存在此结点，上述方法解决了一般二叉树的顺序存储问题，但这种存储方法有时会造成存储空间的浪费。最坏的情况下，一个深度为k的且只有k个结点的