[理工] [DS]小問題

看板Grad-ProbAsk作者 (ZZZZ)時間13年前 (2011/02/13 21:19), 編輯推噓5(5推 0噓 11→)
留言16則, 8人參與, 最新討論串1/1
For complete binary tree, array representation wastes no space 這敘述答案是寫false 我想問是因為他的陣列都是以2的冪次方做為他的大小嗎 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.250.218.142
→
02/13 21:20, , 1F
complete binary tree的定義下，n個node就用n個space存就好
02/13 21:20, 1F
→
02/13 21:21, , 2F
因為看同一層node中，由左至右一定填滿
02/13 21:21, 2F
→
02/13 21:23, , 3F
可是題目不是說沒有浪費空間 那為什麼錯
02/13 21:23, 3F
→
02/13 21:24, , 4F
對阿...為什麼F
02/13 21:24, 4F
推
02/13 21:25, , 5F
Full complete binary tree && complete binary tree ??
02/13 21:25, 5F
推
02/13 21:26, , 6F
array representation是2的次方
02/13 21:26, 6F
→
02/13 21:26, , 7F
Full才會不浪費
02/13 21:26, 7F
→
02/13 21:31, , 8F
我剛沒看到你給的答案= =資結的complete不是我剛講的那樣嗎?
02/13 21:31, 8F
→
02/13 21:32, , 9F
樓上講的應該是full, complete是node編號序跟full一樣
02/13 21:32, 9F
推
02/13 21:33, , 10F
complete並不是指滿的 是指n個node的tree依序放入跟
02/13 21:33, 10F
推
02/13 21:33, , 11F
complete非樹葉層全滿 樹葉層由左至右填 不一定填滿
02/13 21:33, 11F
推
02/13 21:34, , 12F
full tree一樣的位置上, 就像是Ben大說的這樣!
02/13 21:34, 12F
→
02/13 21:35, , 13F
我剛看了一下書，他array是由高度來分配的，高度為k就分
02/13 21:35, 13F
→
02/13 21:35, , 14F
2^k-1個，所以complete不一定會填滿array，而full才會
02/13 21:35, 14F
→
02/13 21:37, , 15F
所以果然問題在array大小的定義 感謝
02/13 21:37, 15F
→
09/11 14:15, , 16F
Full才會不浪費 https://daxiv.com
09/11 14:15, 16F
‣ 更多 death888 的文章
文章代碼(AID): #1DLzfd7U (Grad-ProbAsk)