gpjqem1的部落格

標題:

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

• 2012靜宜大學企管系學費-))
• 怎麼去君悅大飯店-
• Flavour of life 的音樂語法（急需）@1@
• HONDA 雅哥K9價格@1@
• ausu記憶體
• 世界最小的硬幣是甚麼幣
• 98年各四技二專幼保系入取分數
• 98年指定考科法政群錄取分數@1@
• (急!!!)從台北開車到三峽大板根--
• 我想念休閒系...有哪裡可以讀呢-@1@

 

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

發問:

若一個完全二元樹（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