[理工] [資結]-tree depth

看板Grad-ProbAsk作者 (123)時間14年前 (2010/02/20 19:39), 編輯推噓3(3推 0噓 8→)
留言11則, 6人參與, 最新討論串1/1
For a general tree of degree 3 , if the node number is 300, what's its minimum depth? 我是這樣做，degree皆為3的話，用full tree會讓depth最小 0 1 2 k 3 + 3 + 3 +.....+3 =300 k+1 1(3 - 1 ) --------------- =300 求得k = 5，解答說是6 請問我錯在哪阿？ 3-1 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.124.202.119
→
02/20 19:46, , 1F
level=k那層只有3^(k-1)個node
02/20 19:46, 1F
推
02/20 19:49, , 2F
看你root的level定為0還是1
02/20 19:49, 2F
→
02/20 20:01, , 3F
我第一項為3^0，所以level從0開始那我算出來5是對的？
02/20 20:01, 3F
→
02/20 20:02, , 4F
資結level從1開始，離散從0
02/20 20:02, 4F
→
02/20 20:04, , 5F
如果你的level從0開始,那你最後一層的level是h-1
02/20 20:04, 5F
→
02/20 20:06, , 6F
假如你設k為高度,最後一項是3^(k-1)
02/20 20:06, 6F
→
02/20 20:06, , 7F
假如你設k為高度減一,最後給答案要把那1加回來
02/20 20:06, 7F
推
02/20 20:11, , 8F
root定為0的話原po算的沒錯
02/20 20:11, 8F
推
02/20 21:59, , 9F
請問解其他類似題時 要假設root為0還是1會比較好？ 謝謝
02/20 21:59, 9F
→
02/20 22:03, , 10F
你可以寫假設，一般資結1 離散0
02/20 22:03, 10F
→
02/20 22:27, , 11F
喔@@ 原來是假設高度也從0開始 對不起我鬼打牆了
02/20 22:27, 11F
‣ 更多 gn00618777 的文章
文章代碼(AID): #1BVydm7a (Grad-ProbAsk)