Re: [理工] [資結] Complete Tree
※ 引述《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
推
11/09 13:47, , 1F
11/09 13:47, 1F
→
11/09 13:48, , 2F
11/09 13:48, 2F
推
11/09 14:18, , 3F
11/09 14:18, 3F
→
11/09 14:19, , 4F
11/09 14:19, 4F
→
11/09 14:19, , 5F
11/09 14:19, 5F
→
11/09 14:19, , 6F
11/09 14:19, 6F
推
11/09 14:23, , 7F
11/09 14:23, 7F
→
11/09 14:24, , 8F
11/09 14:24, 8F
→
11/09 14:25, , 9F
11/09 14:25, 9F
真的欸@@;
我記成這個定義
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)
推
11/09 15:25, , 10F
11/09 15:25, 10F
推
11/10 00:05, , 11F
11/10 00:05, 11F
→
08/09 10:52, , 12F
08/09 10:52, 12F
→
09/11 14:02, , 13F
09/11 14:02, 13F
→
12/15 00:27,
7年前
, 14F
12/15 00:27, 14F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：