一些概念的定義
- 擴充二叉樹:在二叉樹出現空子樹的位置增加空樹葉所形成的二叉樹
- 外部結點:空樹葉結點
- 內部結點:非空結點
- 外路徑長度:擴充二叉樹中所有外部結點到根結點的路徑長度之和
- 內路徑長度:擴充二叉樹中所有內部結點到根節點的路徑長度之和
重要結論
外路徑長度 E
內路徑長度 I
內結點個數 n
E = I + 2n
數學歸納法證明 E = I + 2n
- 當n為1時,I = 0; E = 2; 滿足 E = I + 2n
- 當有n個內結點時設公式成立,則當有 n + 1個內結點時(相對于n個內結點時增加一個外界點) ,令增加了一個內結點后二叉樹的高為 h(不包含外結點)、內路徑長度 I(n+1) = I(n) + h , 外路徑長度E(n+1) = E(n) - h + 2(h+1),又有E(n) = I(n) + 2n, 整理得 E(n+1) - h - 2 = I(n+1) - h + 2n 即有E(n+1) = I(n+1) + 2(n+1)
證畢
轉載請註明出處,本文鏈接:https://www.uj5u.com/qianduan/198105.html
標籤:其他
