[問題] 將ARRAY的值放入二元樹

看板C_and_CPP作者 (亂入)時間12年前 (2011/12/16 17:05), 編輯推噓1(1推 0噓 18→)
留言19則, 5人參與, 最新討論串1/1
簡單來說 如果今天有個ARRAY是這樣 i 0 1 2 3 4 5 6 7 8 9 10 A[i] 0 5 3 7 4 8 0 9 7 0 8 畫成二元樹是這樣 5 3 7 4 8 9 7 8 簡單來說就是把ARRAY的資料轉成二元TREE 請問該如何實作 想了很久想不出概念 因為他有LEFT跟RIGHT LINK 中間又有空值 最後這程式還要traversal 所以parent到child的link一定要有 還有不知道要不要先把中間兩個0的NODE補起來 因為建立起之後還要判斷是否為LEFTIST TREE 以上新手發問 感謝:) -- 孤單很好， ﹡． 你好厲害唷 ‥ ﹡ … 怎麼變的啊? 因為事實上也沒有人那麼在乎你。 ╰ ‥ 鏘啷! ﹡ ╯ 是什麼啊? ○ ○ ﹡﹨○∕ ‥ ○＞ ● ╰ △ △﹨ □ ＊ □ φkcetair ︿■ ∥ ╯︳ ∥ ∥ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 112.104.192.196 ※ 編輯: ernieyang09 來自: 112.104.192.196 (12/16 17:06)
→
12/16 17:08, , 1F
搜尋binary search tree一定有一堆可以參考的~還會有code~
12/16 17:08, 1F
→
12/16 17:08, , 2F
binary search tree跟這個好像不太像耶 他是根據KEY的
12/16 17:08, 2F
→
12/16 17:09, , 3F
大小去分辨左右的 這是已經設定好要放在哪了
12/16 17:09, 3F
→
12/16 17:09, , 4F
sorry眼殘沒看清楚Orz
12/16 17:09, 4F
→
12/16 17:11, , 5F
is the leaf '8' really the internal '8''s child?
12/16 17:11, 5F
→
12/16 17:11, , 6F
他的0有時會空白有時沒有這點也很奇怪耶
12/16 17:11, 6F
sry更正了 剛剛排版排錯 ※ 編輯: ernieyang09 來自: 112.104.192.196 (12/16 17:12)
→
12/16 17:15, , 7F
應該可以用遞迴做下去,比如說你現在做第1個,就地回呼叫2,3
12/16 17:15, 7F
→
12/16 17:15, , 8F
you can maintain a subtree list, build the target
12/16 17:15, 8F
→
12/16 17:15, , 9F
1*2 , 1*2+1就是他的左右子節點,然後2又呼叫4,5~ 3叫6,7
12/16 17:15, 9F
→
12/16 17:16, , 10F
in bottom up approach, just take values in array
12/16 17:16, 10F
→
12/16 17:16, , 11F
reversely
12/16 17:16, 11F
→
12/16 17:16, , 12F
遞迴終止條件就是子節點的號碼超過陣列大小的時候不要呼叫
12/16 17:16, 12F
→
12/16 17:19, , 13F
版主大大我的方法會對吧???(怕怕的XDD
12/16 17:19, 13F
推
12/16 17:25, , 14F
若熟悉 queue 的話，用 queue 來做應該蠻簡單的
12/16 17:25, 14F
→
12/16 17:28, , 15F
queue is convenient only on building a heap, if
12/16 17:28, 15F
→
12/16 17:30, , 16F
you store just pointers
12/16 17:30, 16F
→
12/16 17:32, , 17F
@flere: it works
12/16 17:32, 17F
→
12/16 17:37, , 18F
謝囉~不過感覺比起queue是難做了一點
12/16 17:37, 18F
→
12/16 17:41, , 19F
原來用array表示轉成用linked表示要這樣轉，感謝f大~
12/16 17:41, 19F
‣ 更多 ernieyang09 的文章
文章代碼(AID): #1EwmdOJM (C_and_CPP)