性质3高度为的m次树至多有m个结点。 证明:由树的性质2可知,第层上最多结点数为 m1(i=1,2 h),显然当高度为h的m次树 (即度为m的树)上每一层都达到最多结点数时,整 个m次树具有最多结点数,因此有: 整个树的最多结点数=每一层最多结点数之和 =m+m1+m2++mh-1=m-1
性质3 高度为h的m次树至多有 个结点。 证明：由树的性质2可知，第i层上最多结点数为 mi-1（i=1，2，…，h），显然当高度为h的m次树 （即度为m的树）上每一层都达到最多结点数时，整 个m次树具有最多结点数，因此有： 整 个 树 的 最 多 结 点 数 = 每 一 层 最 多 结 点 数 之 和 =m0+m1+m2+…+mh-1 = 。 1 1 − − m m h 1 1 − − m m h
性质4具有n个结点的m次树的最小高度为 「logn(an(m1)+1)l。 证明:设具有n个结点的m次树的高度为h,若在 该树中前h-1层都是满的,即每一层的结点数都等于 m个(1si≤h-1),第h层(即最后一层)的结点数 可能满,也可能不满,则该树具有最小的高度。其高 度h可计算如下:
性质4 具有n 个结点的 m次树的最小高度 为 logm(n(m-1)+1)。 证明：设具有n个结点的m次树的高度为h，若在 该树中前h-1层都是满的，即每一层的结点数都等于 mi-1个（1≤i≤h-1），第h层（即最后一层）的结点数 可能满，也可能不满，则该树具有最小的高度。其高 度h可计算如下：
根据树的性质3可得:n 乘(m-1)后得:m1<n(m-1)+1≤m 以m为底取对数后得:h-1<ogn(n(m-1)+1)≤h 即logn(n(m-1)+1)≤h<logm(n(m-1)+1)+1 因h只能取整数,所以 h= logm(n(m-1)+1) 结论得证
根据树的性质3可得： ＜n≤ 乘(m-1)后得： mh-1＜n(m-1)+1≤mh 以m为底取对数后得：h-1＜logm(n(m-1)+1)≤h 即 logm(n(m-1)+1)≤h＜logm(n(m-1)+1)+1 因h只能取整数，所以 h=logm(n(m-1)+1) 结论得证。 1 1 1 − − − m m h 1 1 − − m m h
例1含个结点的三次树的最小高度是多少? 解:设含n个结点的(为完全三次树时高度最小)的三 次树的最小高度为h,则有 1+3+9+,+3h-2+1<n<1+3+9+,+3h-1 (31-1)/2+1≤n(3b-1)2 3h-1<2n-1<3h-2 即:h=og3(2n-1)+1 或 1+3+9++3h2<n<1+3+9++3h-1 (3-1)/2<n≤(3h-1)2 3h-1<2n+1<3h 即:h=「ogs2n+1)
例7.1 含n个结点的三次树的最小高度是多少？ 解：设含n个结点的(为完全三次树时高度最小)的三 次树的最小高度为h，则有： 1+3+9+…+3 h-2+1≤n≤1+3+9+…+3 h-1 (3 h-1 -1)/2 +1≤n≤ (3 h -1)/2 3 h-1 ≤2n-1≤ 3 h -2 即：h=log3 (2n-1)+1 或： 1+3+9+…+3 h-2＜n≤1+3+9+…+3 h-1 (3 h-1 -1)/2 ＜n≤ (3 h -1)/2 3 h-1＜2n+1≤3 h 即：h= log3 (2n+1)
7.1.5树的基本运算 树的运算主要分为三大类: 第一类,寻找满足某种特定关系的结点,如寻 找当前结点的双亲结点等; 第二类,插入或删除某个结点,如在树的当前 结点上插入一个新结点或删除当前结点的第个孩 子结点等 第三类,遍历树中每个结点,这里着重介绍
7.1.5 树的基本运算 树的运算主要分为三大类： 第一类，寻找满足某种特定关系的结点，如寻 找当前结点的双亲结点等； 第二类，插入或删除某个结点，如在树的当前 结点上插入一个新结点或删除当前结点的第i个孩 子结点等； 第三类，遍历树中每个结点，这里着重介绍