→ lairrol:補充一下方法1重組過程要不斷的檢驗整顆新的樹.... 12/18 02:56
→ lairrol:不建議使用就是了.... 12/18 02:56
※ 引述《cg1132001 (瑕疵品大王)》之銘言：
: 小弟我想請問一下
: 作業有一題是要用link的方式建置出一棵max heap tree
: 目前有將tree建出來，值也放入了
: 但是要如何去將普通的complete binary tree 轉成max heap tree?
: 例如：
: 1 5
: / \ / \
: 2 3 → 4 3
: / \ / \
: 4 5 1 2
: 課本上的範例都是用array來建置
: 雖然知道原理，但是因為各節點沒有index
: 要如何去實作想了好久還是沒有頭緒，課本也找不到
: 想請問一下各位大大，要怎麼做才可以達到目的？
: 感謝! m(_ _)m
Sorry~我內文沒看清楚!!我還以為原波是要來問"Heap tree"
或"Linked list"的~所以我回文謝罪了.....
===================負責任的分隔線===================
自己在學D.S.的時候老師也出過類似的問題
我想過的方法是如果有一棵什麼也不是的tree
要轉變成 Max-heap 有以下兩種
Method:
1.砍掉重練法
2.重組法
方法內容請往下看囉~
==========================================================
1.砍掉重練法就是把原本的tree從尾巴一個一個重新拼出Max-heap
ex:
Step 1.
1 3
/ \ 把 3 拿出來 →
2 3
這時候原本的tree變下面這樣↓
1
/ \
2
Step 2.
1
/ \ 把 2 拿出來跟 3 比 比3小所以插在3下面
2
變成這樣
3
/
2
一直循環上面的步驟到原本的tree都被砍光為止
這樣新的tree就是你要的Max-heap
===========================================================
2.重組法
Max-heap的定義就是老大要比小弟大
老大(父節點) 小弟(子節點)
一個老大帶兩個小弟這樣是很合理的!!(誤)
ex:
3 3
/ \ 跟 / \
1 2 2 1
是一樣的
所以看你原本沒排過的tree有多大叢就從下面開始比較然後往上比較
我的順序是由右到左 由下到上 記得要檢驗一下是否有沒換到的
細節我有點忘記了....
大概是這樣.....
ex:
1
/ \
4 6
/ \ / \
5 3 2 7
先比較 再比較 最後再比
6 4 1
/ \ / \ / \
2 7 5 3 ? ?
^^^ ^^^
為什麼是問號?
因為要等你比較完下面兩組之後那兩個數字才會確定
大概是這樣囉~!!
給你參考....
p.s:想當初小大二的我是用方法1 去硬幹..... 用Linked list玩到差點瘋掉就是了
--
▃▃ ╔ ═ ╗
▍ ▍ ▃▃▃ ╴╴╴
◣ ◢ ◥◣ ╚ ═ ╝ ╲ ╔═══╗
▌▄ ◢◤ ◥◣ ║ ╱ ╲ ║ Blue ║
▌ ▌ ◢◤ ◥◣ ║ ╠ ═ ╱ ╲ ╚═══╝
▄▄▄ ◢◤ ◥◣ ═╩ ╩ ══ ╱ ╲http://i.imgur.com/RRU3c.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.114.98.99
※ 編輯: lairrol 來自: 58.114.98.99 (12/18 02:53)