Re: [理工] [資結] Tree的性質
※ 引述《huangwh (香腸)》之銘言：
科目:資料結構
範圍:二元樹
題目:
就下列4種Binary Tree，分別自(A)～(D)中填入Correct選項
1.任意的Binary Tree
2.Full Binary Tree
3.Complete Binary Tree
4.Strict Binary Tree
A n0=n2+1
B n=2n0-1
C 高度=log(n+1) [礙於輸入關係，此基底為2]
D n0+n2<=n
答案: 1.A
2.A B C D
3.A C D
4.A B D
問題: 我的問題在選項 D
筆記上寫:
n0+n2<=n
n0+n2<=n0+n1+n2<=n0+n2+1
|_______| 問題所在
|_______>這一段是怎樣得出的?
|
n0+n2<=n0+n1+n2 |
0<=n1 |
|
n0+n1+n2<=n0+n2+1 -------
n1<=1
0<=n1<=1
便可得 2 3 4 皆為所求
ref:
如果你是指洪兔的筆記，這段不是嚴謹的推導，只是在解釋選項。
選項D的筆記似乎漏抄了部份文字，
原選項為「n0 + n2 <= n <= n0 + n2 + 1」
則:
令 n : 總node數;
n1: Degree 1 之node數
n2: Degree 2 之node數
n = n0 + n1 + n2
If Binary Tree 非空:
n0 = n2 + 1 (by Thm.)
選項(D)
(i)
n0 + n2 <= n
( n2 + 1 ) + n2 <= n0 + n1 + n2
2n2 + 1 <= 2n2 + n1 + 1
等號成立於 n1 = 0 ;
(Note: 這裡條件不足以推論至n1<=1)
n <= n0 + n2 + 1
( n0 + n1 + n2 ) <= n0 + n2 + 1
n1 <= 1;
(ii)
by Def:
任意 Binary Tree : 0 <= n1 <= n-1
Full Binary Tree : n1 = 0
Complete Binary Tree : 0 <= n1 < 1
Strickly Binary Tree : n1 = 0
by(i),(ii) choose 2,3,4
--
有錯或誤會原意尚祈指正
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.112.174
※ 編輯: witz 來自: 118.160.112.174 (09/22 02:55)
推
09/22 15:05, , 1F
09/22 15:05, 1F
→
09/22 15:52, , 2F
09/22 15:52, 2F
※ 編輯: witz 來自: 118.160.112.174 (09/22 15:52)
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：