根据树的性质3可得:m<m m-1 乘(m-1)后得: mr1<n(m1)+1≤mr 以m为底取对数后得:h-1< logm(m(m1)+1)≤h 即ogn(n(m1)+1)≤h<logn(m(m1)+1)+1 因h只能取整数,所以 h= log(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
例、含n个结点的三次树的最小高度是多少?最大高度是 多少? 解:设含n个结点的(为完全三次树时高度最小)的三次 树的最小高度为h,则有: 1+3+9+,+34-2<K1+3+9+,+34-1 (341-1)/2<(3h-1)/2 3h-1<2n1<3h 即:h=「log3(2n+1 最大高度为n-2。 Q ○○○
例、含n个结点的三次树的最小高度是多少？最大高度是 多少？ 解：设含n个结点的（为完全三次树时高度最小）的三次 树的最小高度为h，则有： 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) 最大高度为n-2。 …
6.1.5树的基本运算 树的运算主要分为三大类 第一类,寻找满足某种特定关系的结点,如寻找当前结 点的双亲结点等; 第二类,插入或删除某个结点,如在树的当前结点上插 入一个新结点或删除当前结点的第论孩子结点等; 第三类,遍历树中每个结点,这里着重介绍
6.1.5 树的基本运算 树的运算主要分为三大类： 第一类，寻找满足某种特定关系的结点，如寻找当前结 点的双亲结点等； 第二类，插入或删除某个结点，如在树的当前结点上插 入一个新结点或删除当前结点的第i个孩子结点等； 第三类，遍历树中每个结点，这里着重介绍
树的所 树的遍历运算是指按某种方式访问树中的每一个结点且 每一个结点只被访问一次 有以下三种遍历方法: ●先根遍历 ●后根遍历 ●层次遍历 注意:先根和后根遍历算法都是递归的
树的遍历运算是指按某种方式访问树中的每一个结点且 每一个结点只被访问一次。 树的遍历 有以下三种遍历方法： 先根遍历 后根遍历 层次遍历 注意：先根和后根遍历算法都是递归的。 A B C D E F G H I J K
先根遍历: 若树不空,则先访问根结点,然后依次先根遍历各棵子树 先根遍历的顶点访问次序 ABEFCDGHIJK
先根遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 先根遍历的顶点访问次序： A B E F C D G H I J K A B C D E F G H I J K