等级考试公共基础考点分析之数据结构与算法(9)

文章作者 100test 发表时间 2007:03:10 16:45:31
来源 100Test.Com百考试题网

1.6 树与二叉树
考点16 树的定义
　　树是由n( n≥0)个结点组成的有限集合。若n =0，称为空树；若n>0，则：
　　 (1)有一个特定的称为根(root)的结点。它只有直接后件，但没有直接前件；
　　 (2)除根结点以外的其他结点可以划分为m(m≥0)个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti(i=0，1，…，m-l)又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前件，但可以有0个或多个直接后件。
　　树型结构具有如下特点：
　　 (1)助每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根；
　　 (2)每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点；
　　 (3)一个结点所拥有的后件个数称为树的结点度；
　　 (4)树的最大层次称为树的深度。
　　在计算机中，可以用树结构来表示算术表达式，用树来表示算术表达式的原则是：
　　 (1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点；
　　 (2)运算符的每一个运算对象在树中为该运算符结点的子树(在树中的顺序为从左到右)；
　　 (3)运算对象中的单变量均为叶子结点。
　　树在计算机中通常用多重链表表示。
考点17 二叉树的定义及其基本性质
　　1什么是二叉树
　　二叉树(binary tree)是由n(≥0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。
　　二叉树具有如下两个特点：
　　 (1)非空二叉树只有一个根结点；
　　 (2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
　　二叉树的每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树(树为无序树)，其子树的顺序不能颠倒，因此，二叉树有5种不同的形态
　　在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点)
　　2二叉树的基本性质
　　性质1：在二叉树的第入层上至多有2k-1个结点(k≥1)。
　　性质2：深度为m的二叉树至多有2m-1个结点。
　　深度为m的二叉树的最大的结点数是为二叉树中每层上的最大结点数之和，由性质1得到最大结点数。
　　
　　性质3：对任何一棵二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个。
　　如果叶子结点n0，度为2的结点数为n2，则n0=n2 l。
　　设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有
　　N=n0 n1 n (1)
　　再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设m为二叉树中的分支总数，则有
N=m 1 (2)
　　又由于二叉树中这m个分支是分别由非叶子结点射出的。其中度为1的每个结点射出1个分支，度为2的每个结点射出2个分支。因此，二叉树中所有度为1与度为2的结点射出的分支总数为n1 2n2 ，而在二叉树中，总的射出分支数应与总的进入分支数相等，即
m=n1 2n2 (3)
将(3)代入(2)式有
N=n1 2n2 1
比较(1)和(4)并化简得
n0=n2 1
　　性质4：具有n个结点的完全二叉树的深度至少为[log2n] 1，其中[log2n]表示log2n的整数部分。
　　3满二叉树与完全二叉树
　　(l)满二叉树
　　满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。深度为k的二叉树具有2k-1个结点。即在满二叉树的第k层上有2k-1个结点。
　　从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m-1个结点。
　　(2)完全二叉树
　　完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。