Re: [問題] 計概某二元樹題

看板TransCSI作者XrGodz (紐愛銅管分部首席)時間17年前 (2007/06/10 14:46)推噓2(2推 0噓 3→)

留言5則, 2人參與討論串2/2 (看更多)

※ 引述《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

推

freexq

06/10 17:46, , 1^F

06/10 17:46, 1^F

→

freexq

06/10 17:47, , 2^F

06/10 17:47, 2^F

→

freexq

06/10 17:49, , 3^F

06/10 17:49, 3^F