性质3高度为h的m次树至多有m个结点 证明: 由树的性质2可知第层上最多结点数为m1 (i=1,2h),显然当高度为h的m次树(即度为m的树 上每一层都达到最多结点数时整个m次树具有最多结 点数因此有: 整个树的最多结点数=每一层最多结点数之和 h-1m-1 +mltm.+m m-1
11 证明： 由树的性质2可知,第i层上最多结点数为mi-1 (i=1,2,…,h),显然当高度为h的m次树(即度为m的树) 上每一层都达到最多结点数时,整个m次树具有最多结 点数,因此有： 整个树的最多结点数 = 每一层最多结点数之和 性质3:高度为h的m次树至多有 个结点。 1 1 − − m m h 1 0 1 2 = + + + = − m m m m … h 1 1 − − m m h
性质4 具有n个结点的m次树的最小高度为gn(m(m-1)+) 证明:设具有n个结点的m次树的高度为h若在该树中 前h-1层都是满的即每一层的结点数都等于m1个 (1≤i≤h-1)第h层(即最后一层)的结点数可能满也可 能不满则该树具有最小的高度。由此可得如下关系 m-/<nx今h-1 n-1 去分母并取对数后得:h-1<0gn(nⅧm1)+)sh Bp log (n(m-1)+1)<h< log (n(m-1)+1)+1 因h只能取整数,故h=|0g(n(m-+17
证明：设具有n个结点的m次树的高度为h,若在该树中 前h-1层都是满的,即每一层的结点数都等于mi-1个 (1≤i≤h-1),第h层(即最后一层)的结点数可能满,也可 能不满,则该树具有最小的高度。由此可得如下关系： 性质4: 具有n个结点的m次树的最小高度为logm (n(m−1) +1) 1 1 1 1 1 − − < − − − m m n m m h h 因h只能取整数，故 h=logm (n(m−1)+1) h n m h m 去分母并取对数后得： −1< log ( ( −1) +1) 即 log (n(m − 1) + 1) h < log (n(m − 1) + 1) + 1 m m h −1 <logm (n(m −1) +1) h
判断题 (1)树状结构中的每个结点都有一个前驱。(F (2)度为m的树中至少有一个度为m的结点。(T) 填空题 (1)高度为h,度为m的树中至少有m1个结点 至多有个结点。 (2)一颗共有n个结点的树,其中所有分支结点的 度均为k,则该树中的叶子结点个数为n(-1)+1/k (3)一颗含有n个结点的k叉树,可能达到的最大 深度为-+1和最小深度为Logg(k1)+1 13
13 (1) 树状结构中的每个结点都有一个前驱。 (2) 度为m的树中至少有一个度为m的结点。 判断题 填空题 (1)高度为h，度为m的树中至少有______个结点， 至多有______个结点。 (2) 一颗共有n个结点的树，其中所有分支结点的 度均为k，则该树中的叶子结点个数为_____。 (3) 一颗含有n个结点的k叉树，可能达到的最大 深度为_____和最小深度为_____ 。 (F) (T) h+m-1 1 1 − − m m h n-k+1 [n(k-1)+1]/k Logk (n(k-1)+1)
715树的基本运算 树的运算主要分为三大类 >第一类寻找满足某种特定关系的结点 如寻找当前结点的双亲结点等; >第二类插入或删除某个结点如在树的 当前结点上插入一个新结点或删除当前 结点的第个孩子结点等; 第三类遍历树中每个结点。 14
14 7.1.5 树的基本运算 树的运算主要分为三大类： ➢ 第一类,寻找满足某种特定关系的结点, 如寻找当前结点的双亲结点等； ➢ 第二类,插入或删除某个结点,如在树的 当前结点上插入一个新结点或删除当前 结点的第i个孩子结点等； ➢ 第三类,遍历树中每个结点
树的遍历运算是指按某种方式访问树中的每一个结 点且每一个结点只被访问一次。树的遍历运算的算法主 要有先根遍历和后根遍历两种。 1.先根遍历 先根遍历过程为: B D (1)访问根结点; E FIGCH (2)按照从左到右的次序先 根遍历根结点的每一棵子树。 ABEFCGdHMIJ
树的遍历运算是指按某种方式访问树中的每一个结 点且每一个结点只被访问一次。树的遍历运算的算法主 要有先根遍历和后根遍历两种。 1. 先根遍历 先根遍历过程为： (1)访问根结点； (2)按照从左到右的次序先 根遍历根结点的每一棵子树。 A B E F C G D H M I J A B C D E F G H I J M