推 freexq:哇~~懂了....解得漂亮^^,感謝!! 06/10 17:46
→ freexq:我知道我的算法錯在哪裡了 06/10 17:47
→ freexq:公式求出的X是總節點數目,而不是題目要的"第h層的節點數" 06/10 17:49
→ freexq:所以用這個公式就錯了...畫圖才是正解~~ 06/10 17:53
推 swabasic:有公式 你也可以自己代數字進去 例第三層這樣 06/27 20:14
※ 引述《freexq (快樂蕃茄)》之銘言：
: 高度為 n 的二元樹(Binary tree)，第 h 高度的節點(Nodes)數目
: 最多有多少個(其中n>=h)？
: (A)2^h+1 (B)2^(h+1) (C)2^h-1 (D)2^(h-1)
: 正確解答為：(D)
: ----------------------------------------------------------
: 以下為我自己算的，但是是錯的，請各位先進指點
: log(x+1)=h (設 x 為節點數目)
: -->2^h=x+1
: -->x=2^h-1
第一層 有1個節點 ○ 2^0 第一層的節點數=2^(1-1)
/ \
第二層 有2個節點 ○ ○ 2^1 第二層的節點數=2^(2-1)
/ \/ \
第三層 有4個節點 ○ ○○ ○ 2^2 第三層的節點數=2^(3-1)
/ \/\/\/ \
第四層 有8個節點 ○○○○○○○○ 2^3 第四層的節點數=2^(4-1)
. . . . .
. . . . .
. . . . .
. . . . .
很好奇為什麼會用到log...= =?
有關於樹的題目
基本上只要圖畫一畫
答案就會出來了
不需要記那些冗長的公式...XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.229.20.138