[理工] 完整二元樹問題

看板Grad-ProbAsk作者 (effeminacy)時間9年前 (2016/11/24 10:45), 編輯推噓5(5推 0噓 15→)
留言20則, 4人參與, 最新討論串1/1
假設有一棵完整二元樹，其高度h=4時， 請問此棵二元樹的節點數n 最少與最多各多少？ 解答給n的範圍是：7 < n < 15 我的疑問： 是不是 7 < n <= 15才對? 因為完滿二元樹必定是完整二元樹 而完滿二元樹的節點數是(2^h) - 1 = 15 所以15是不是也要包含才對 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.55.230 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479955532.A.0A9.html
推
11/24 10:55, , 1F
我認為要包含
11/24 10:55, 1F
推
11/24 11:01, , 2F
我也認為要包含，不過完滿是指full，完整是指complete嗎
11/24 11:01, 2F
→
11/24 11:05, , 3F
是的,然後root為1
11/24 11:05, 3F
→
11/24 11:06, , 4F
完整二元樹,還有一個特性,不能跳節點,編號要依序存放
11/24 11:06, 4F
推
11/24 11:09, , 5F
話說，full不一定是complete吧？full要求是每個internal
11/24 11:09, 5F
→
11/24 11:09, , 6F
node都要有兩個子點，complete是要求每個leaf都要在同一
11/24 11:09, 6F
→
11/24 11:09, , 7F
層
11/24 11:09, 7F
推
11/24 11:12, , 8F
我們學校老師教的full一定是complete，樓上說的那
11/24 11:12, 8F
→
11/24 11:12, , 9F
個叫proper binary tree，但是我好像也有看過不一
11/24 11:12, 9F
→
11/24 11:12, , 10F
樣的定義@@
11/24 11:12, 10F
推
11/24 11:49, , 11F
我也覺得很妙，我以前學的full是全滿的，可是上網查的
11/24 11:49, 11F
→
11/24 11:49, , 12F
又會看到只要每個internal node包含兩個子點也被稱做是
11/24 11:49, 12F
→
11/24 11:49, , 13F
full, 可能真的是定義不同吧
11/24 11:49, 13F
→
11/24 11:52, , 14F
網路的確有看到不同定義,如果考解釋定義,full我的寫法
11/24 11:52, 14F
→
11/24 11:53, , 15F
應該還是偏向節點數全滿那個定義，看了幾本書都是這寫法
11/24 11:53, 15F
→
11/24 11:53, , 16F
至於其他定義寫法，也有送分可能
11/24 11:53, 16F
→
11/24 12:31, , 17F
資結跟離散的complete full 意思完全不同喔
11/24 12:31, 17F
→
11/24 12:32, , 18F
離散complete=資結的full
11/24 12:32, 18F
→
11/24 12:34, , 19F
離散full BT = 每個internal node有兩個子點
11/24 12:34, 19F
→
11/24 12:41, , 20F
因為我沒學過離散,感謝A大的釐清
11/24 12:41, 20F
‣ 更多 wtmo5566 的文章
文章代碼(AID): #1ODbHC2f (Grad-ProbAsk)