作者jameschou (DOG)
看板Grad-ProbAsk
標題Re: [理工] [資結] Complete Tree
時間Tue Nov 9 01:17:47 2010
※ 引述《koehie (開喜烏龍茶)》之銘言：
: 請問下列三題該如何解答 ?
: 1. 一顆深度為 H 的 Complete Binary Tree 最少有幾個節點 ?
: 2. 一顆深度為 H 的 Complete Binary Tree 最多有幾個節點 ?
: 3. 假如一顆 Complete Binary Tree 總共有 n 個節點且 n 為奇數, 請問
: 此樹中 Leaf 節點有多少個 ?
照這題題意看起來
Complete Binary Tree應該是"除了leaf以外的節點都有左右子樹"這定義
(因為complete binary tree這個好像在不同書有不同定義的樣子)
如果是這個定義,那麼
1.
樹應該是長類似這樣(此圖是深度H=4):
o
/ \
o o
/ \
o o
/ \
o o
如此可以知道
最少有2*H-1 = 2H-1個節點
2.
樹應該是全滿的 類似這樣(此圖是深度H=4):
o
/ \
o o
/ \ / \
o o o o
/ \ / \ / \ / \
o o o o o o o o
可知道最多有2^H-1個節點
3.
n為奇數這條件其實不是很重要 因為n好像一定會是奇數@@
設此樹內節點有i個,leaf有f個
n = i + f
又 i = f - 1
=> n = 2*f - 1
=> f = (n+1)/2 ...所以答案是(n+1)/2個
至於為什麼i = f - 1
我們可以從最小的樹開始考慮 (三個點):
o
/ \
o o
此時的 f=2 , i=1 ,所以 i = f-1沒錯
再來只要更大的樹 都可以從這個樹慢慢生成
(把一個leaf拿掉 換成一個內節點 但內節點一定要有左右子樹 所以又有兩個leaf)
=>每將一個leaf拿掉改成內節點 就會再多出兩個leaf
也就是說leaf的數量 少了一 又多了二 => 每操作一次leaf數多一點
而每操作一次 內節點的數量也是多一點
簡單來說 內節點跟leaf的"差"不會變 也就是1 , 所以 i = f-1
統整一下這三題的答案:
1. 2H-1
2. 2^H -1
3. (n+1)/2
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.83
推 Martin23:你第一題好像不對吧... 11/09 13:47
→ Martin23:不過應該是tree定義不一樣 11/09 13:48
推 hanbz:A complete binary tree is a binary tree in which every 11/09 14:18
→ hanbz:level, except possibly the last, is completely filled, 11/09 14:19
→ hanbz:and all nodes are as far left as possible.[4] 11/09 14:19
→ hanbz:wiki上的定義 11/09 14:19
推 hanbz:版本差異在於是除最後一層外都要填滿只有最後一層先填左邊 11/09 14:23
→ hanbz:還是只要滿足是先填左邊,右邊都可以當作最後一層~~ 11/09 14:24
→ hanbz:反正以聖經版的解釋為主吧~鑽研版本問題沒太大意義XD 11/09 14:25
真的欸@@;
我記成這個定義
A binary tree in which each node has exactly zero or two children.
這好像有些書上是叫作full binary tree ... 的樣子
主要好像就是complete跟full這兩種在各版本有一些出入
所以聖經版的解釋是哪一個..?
如果是照三樓的定義的話
這題的答案應該是 2^(H-1) ..嗎? (前幾層全填滿 最下最左留一個leaf)
※ 編輯: jameschou 來自: 140.113.139.83 (11/09 14:33)
推 compulsory:strictly BT? 11/09 15:25
推 KenJcFar:full BT ,complete BT的定義在離散和資結上似乎就有不同 11/10 00:05