※ 引述《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)