4广义表表示法 对图6-1(c)的树结构,广义表表示法可表示为: (A(B(E (J, K, L), F), C(G), D(H (M),I))) 614树的性质 入性质1树中的结点数等于所有结点的度加1 证明:根据树的定义,在一棵树中,除根结点以外,每 个结点有且仅有一个直接前驱,也就是说,每个结点与 指向它的一个分支一一对应,所以,除根结点以外的结 点数等于所有结点的分支数(即度数),而根结点无直 接前驱,因此,树中的结点数等于所有结点的度数加1
4.广义表表示法 对图6-1（c）的树结构，广义表表示法可表示为： （A（B（E（J，K，L），F），C（G），D（H （M），I））） 6.1.4 树的性质 性质1 树中的结点数等于所有结点的度加1。 证明：根据树的定义，在一棵树中，除根结点以外，每 个结点有且仅有一个直接前驱，也就是说，每个结点与 指向它的一个分支一一对应，所以，除根结点以外的结 点数等于所有结点的分支数（即度数），而根结点无直 接前驱，因此，树中的结点数等于所有结点的度数加1
性质2度为k的树中第层上最多有k1个结点(1)。 下面用数学归纳法证明: 对于i=1,显然成立,假设对于i1层,上述条件成立, 即第i-1层最多有k2个结点, 对于第层,结点数最多为第i1层结点数的k倍(因为 度为k),故第j层的结点数为k2*k=k1 性质3深度为h的k叉树最多有k-个结点 证明:由性质2可知,若每一层的结点数最多,则整 个k叉树结点数最多,共有∑k=k0+k1+.+kh k 当K叉树上的结点数达到1时,称为满K叉 树
性质 2 度为k的树中第i层上最多有k i-1个结点（i≥1）。 下面用数学归纳法证明： 对于i=1，显然成立，假设对于i-1层，上述条件成立， 即第i-1层最多有k i-2个结点， 对于第i层，结点数最多为第i-1层结点数的k倍（因为 度为k），故第i层的结点数为k i-2*k= k i-1 。 1 1 − − k k h 性质3 深度为h的 k叉树最多有 个结点。 1 1 − − k k h 1 1 − − k k h 证明：由性质2可知，若每一层的结点数最多，则整 个 k 叉 树 结 点 数 最 多 ， 共 有 =k0+k1+…+kh- 1= 。 当一棵K叉树上的结点数达到 时，称为满K叉 树。 = − h i i k 1 1
性质4具有n个结点的k叉树的最小深度为log(n(k (请注意,「x表示取不小于x的最小整数,或叫做对x上 取整。) 证明:设具有n个结点的k叉树的深度为h,即在该树的前 h-1层都是满的,即每一层的结点数等于k个(1≤-h1) 第h层(即最后一层)的结点数可能满,也可能不满,这 时,该树具有最小的深度。由性质3知道,结点数n应满 hn足下面条件: 下通过转换为:kh1<n(k-1)+1≤k,再取以k为底的 对数后,可以得到 h-1<log, (n(k-1)+1<h, Ep A: log,(n(k-1)+1)<h<log, (n(k )+1)+1,而h只能取整数,所以,该k叉树的最小深度为 「log(n(k-1)+1)1
性质4 具有n个结点的k叉树的最小深度为logk (n(k- 1)+1)。 1 1 1 − − − k k h 1 1 − − k k h （请注意，x 表示取不小于x的最小整数，或叫做对x上 取整。） 证明：设具有n个结点的k叉树的深度为h，即在该树的前 面h-1层都是满的，即每一层的结点数等于k i-1个(1≤i≤h-1)， 第h层（即最后一层）的结点数可能满，也可能不满，这 时，该树具有最小的深度。由性质3知道，结点数n应满 足下面条件： <n≤ ，通过转换为：k h-1<n(k-1)+1≤kh ，再取以k为底的 对数后，可以得到： h-1<logk (n(k-1)+1)≤h，即 有：logk (n(k-1)+1)≤h<logk (n(k- 1)+1)+1，而h只能取整数，所以，该k叉树的最小深度为 h=logk (n(k-1)+1)
6.2二叉树 621二叉树的定义 二叉树的定义 和树结构定义类似,二叉树的定义也可以递归形式给 入出: 二叉树是n(n0)个结点的有限集,它或者是空集 (n=0),或者由一个根结点及两棵不相交的左子树和 右子树组成。 二叉树的特点是每个结点最多有两个孩子,或者说, 在二叉树中,不存在度大于2的结点,并且二叉树是有 序树(树为无序树),其子树的顺序不能颠倒,因此, 二叉树有五种不同的形态,参见图6-5
6.2 二叉树 6.2.1 二叉树的定义 1．二叉树的定义 和树结构定义类似，二叉树的定义也可以递归形式给 出： 二叉树是n（n≥0）个结点的有限集，它或者是空集 （n=0），或者由一个根结点及两棵不相交的左子树和 右子树组成。 二叉树的特点是每个结点最多有两个孩子，或者说， 在二叉树中，不存在度大于2的结点，并且二叉树是有 序树（树为无序树），其子树的顺序不能颠倒，因此， 二叉树有五种不同的形态，参见图6-5
(e) 图6-5二叉树的五种不同的形态
L R L R Ø (a) (b) (c) (d) (e) 图 6-5 二叉树的五种不同的形态