树的性质及其证明

目录

性质  1

● 性质

●证明  

例子:

性质2

性质3

性质4

例子

---

性质  1

● 性质

        • 树中的节点数等于所有节点的度数加 1

●证明  

 

---

● (树的定义)在一棵树中, 除数根节点外,每个节点有且仅有一个前驱节点.
● (理解)每个节点与指向它的一个分支一一对应
● (推导)除树根之外的节点数等于所有节点的分支数
● (节点度的定义)节点的子树的个数称为该节点的度
● (结论) 树中的节点数等于所有节点的度数加一

例子:

● 一棵度为4的树T中 ,若有20个度为4的节点,10个度为3的节点,1个度为2的节点,10个度为1的节点 ,则树T的叶子节点
个数是_____.
A,41 B,82 C,123 D,122
● 解:
    • 树T中的节点数 : 20*4+10*3+1*2+10*1+1 = 123
    • 除叶节点(度为0的节点)外的节点数 : 20+10+1+10 = 41
    • 剩余的叶节点个数: 123-41 = 82, 选B

性质2

● 性质
    • 度为m的树中第 i 层(i>=1)上至多有m^i-1个节点

● 证明(采用数学归纳法)
    • 由题意得
        树的度为 m ,说明此数的一个节点上,最多有 m 个节点 
   • 对于第一层,因为树中的第一层上只有一个节点,即整个树的根节点，而由 i = 1 代入

        m^(i-1), 得m^(1-1) = m^0 =1,有一个节点,显然结论成立
    • 假设对于第(i-1)层(i>1)命题成立 , 即度为m的树中第(i-1)层上至多有m^(i-2)个节点
    • 根据树的度的定义 , 度为m的树中每个节点至多有m个孩子节点,

        所以第 i 层至多为m^(i-2) * m = m^(i-1)个节点,
      这与命题相同,故命题成立

性质3

● 性质
    • 高度为 h 的m次树至多 有 (m^h -1)/(m-1)个节点

---

● 证明
    • 由题意可知, m次树,每个节点最多有m个后继节点,
    • 由性质2可知 ,第i层上最多节点数为m^(i-1) ,(i=1,2,...,h)
    • 当高度为 h 的m次树(即度为m的树)上每一层都达到最多节点数时,整个m次树具有最多节点数
    • 所以整个树的最多节点数
        = 每一层的最多节点数之和
        = m^0 + m^1 + m^2+...+m^(h-1)
        = ( m^h -1)/( m - 1 )
以上是等比数列 ,我们利用公式求和即可
    ①Sn = m^0 + m^1 + m^2+...+m^(h-1)
    ②m*Sn =  m^1 + m^2+...+m^(h-1)+m^h
    ①-② ,得 (1-m)Sn = m^0 - m^h 
    化简得, Sn = (m^h -1)/( m - 1 ) 

性质4

● 性质
    • 具有n个节点的m次树的最小高度h为⌈㏒ₘ(n(m-1)+1)⌉

● 证明
    • 设具有 n 个节点的m次树的高度为h, 若在该数中前h-1层都是满的,即每一层的节点数都等于m^(i-1)个(1<=i<=h-1),
      则该树具有最小的高度,第h层(即最后一层)的节点数可能满,也可能不满
    • 所以,当已知节点数 , 因为要求最小高度,所以 1~(h-1)层都是满的, 所以前面的层的节点数可以确定,由性质3,得出 
    h层前面的所有节点个数是: m^(h-1)/(m-1) 个
    第 h 层的节点是 , 可能不满, 所以m次数的节点 ,介于之间
    • 其高度 h 可计算如下:
        即 
        m^(h-1)/(m-1)  <  n   <=  (m^h-1)/(m-1)
    我们将其化简即可得到
        h = ⌈㏒ₘ(n(m-1)+1)⌉

化简过程图示如下:

例子

● 问题
    • 含 n 个节点的三次树的最小高度是多少 ? 最大高度是多少 ?
● 解

            

最小高度:
    • 含 n 个节点的三次树 , 每个分支结点度都是 3 时, 高度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 = ⌈log₃(2n+1)⌉

最大高度:
    • 设最大高度为h ,则 1 ~ h-1 层的节点个数是 1个 ,到 h 层,节点为3个,保证是三次树,
    前 h -1 层的节点总数为 (h-1) 个 , 第 h层节点个数是 3 个, 节点总数是 n 个 ,
    由  (h-1)+3 = n ,得
    最大高度是  n-2