close
標題:

二元樹的一個選擇題...

 

此文章來自奇摩知識+如有不便請留言告知

發問:

若一個完全二元樹（complete binary tree）的高度為8，則其最多可能節點數目為： a)255 b)256 c)511 d)512 這題是不是怪怪的呢？答案是給 c complete binary tree 不是最底層沒有滿嗎？

最佳解答:

高度 0： 1個節點（根節點） 高度 1： 3個節點 (2^2-1) 高度 2： 7個節點 (2^3-1) 高度 3： 15個節點 (2^4-1) 高度 4： 31個節點 (2^5-1) 高度 5： 63個節點 (2^6-1) 高度 6：127個節點 (2^7-1) 高度 7：255個節點 (2^8-1) 高度 8：511個節點 (2^9-1) 2009-12-01 02:04:27 補充： 請翻閱資料結構書籍對這些的定義再說吧！

其他解答:

這題答案會有爭議，也有不少人把根節點歸為第一層，這種用法反而占大多數，所以這題答案會有很大的問題.... 事實上，這題答案A也可以，高度8：(2^8-1)=255個節點 ，基本上選A的人是占大多數的，選C的人應該是小部分，這題可以去考選部抗議，出題者太粗心了，應該要定義根節點為第0層或第1層才可以。|||||並沒有怪怪的啊.沒錯,complete binary tree的定義是最底層不需要全滿.若滿的話那也是個complete binary tree啊.這題目是說"則其最多可能節點數目".所以就像東邪無弓所講的.一個高度為8的binary tree在全滿的情況之下是511的node.6FE1C1721610E824
arrow
arrow
    文章標籤
    第一 也是 保系入 答案 高度
    全站熱搜

    gpjqem1 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄