[問題]二元樹刪除左右皆有子樹的節點

作者: sdfg014025xx (隨便就好)   2017-12-14 18:32:11
開發平台(Platform): (Ex: Win10, Linux, ...)
Win 10
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
VC2017
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
問題(Question):
BST中刪除的部分
在remove部分中的removeNode函式不太懂
291行上面是處理當刪除的是葉節點和目標若
是其中一個無子樹的情況
我搞不懂是291行要處理刪除目標皆有子樹的
情況,tempPtr的指標是由呼叫
removeLeftmostNode得來,我看得懂他是要
找大於刪除目標但是是最小的節點,可是他之
後回傳是return removeNode(nodePtr),這樣
子temp的指標是怎麼得到呢?因為如果跳到
removeNode的話不就變的要刪掉葉節點,後
來回傳就是空指標了temp接下來的程式碼不就錯了嗎?
餵入的資料(Input):
預期的正確結果(Expected Output):
錯誤結果(Wrong Output):
程式碼(Code):(請善用置底文網頁, 記得排版)
http://codepad.org/paIfmLtw
補充說明(Supplement):
因為只有這邊搞不懂所以主程式和其他的標頭
檔就沒有附了,我查了刪除是把取代的節點資
料替換,然後刪掉最後的葉節點,可是這支程
式碼替換的地方看的不是很懂...卡了很久,拜
託各位救我,感謝!
作者: longlongint (華哥爾)   2017-12-14 19:20:00
先看抽象概念 刪除 node 後要找一個 node 來頂位置這個 node key 要比左邊全部大 比右邊全部小,自然是挑右子樹的最小值來用囉
作者: sdfg014025xx (隨便就好)   2017-12-14 19:28:00
概念上大概了解...可是程式的實作有點看不懂
作者: galic (嘎利)   2017-12-14 20:24:00
因為程式碼錯了..
作者: sdfg014025xx (隨便就好)   2017-12-14 20:39:00
真的嗎?這是老師出作業挖空給我們寫的
作者: galic (嘎利)   2017-12-14 21:53:00
因為課本寫錯了 老師傻傻相信 慘
作者: sdfg014025xx (隨便就好)   2017-12-14 22:08:00
可是照這樣的程式碼跑一些測資還是對的,可以請教一下他錯在哪嗎QQ 這邊卡住很久
作者: galic (嘎利)   2017-12-14 22:14:00
https://wikipedia.org/wiki/Binary_search_tree#Deletion第三.Deleting a node with two children...D就是你要刪的點 E是找到in-order順序大一位要來替代的點E可能有right sub-tree F用E的值覆蓋D E沒有右子就刪除node 但E可能有右子F這時候應該是要F去替換E 而不是把F變成D的右子那D原本的右子去哪了?附個圖給你 紅色是錯的 https://i.imgur.com/BA6JDUd.png
作者: peterwu4 (notd)   2017-12-14 22:44:00
其實不複雜,換完值後,要刪除的點就是葉子或是一個子node的點,利用recursive的概念,把那個點再餵回去就可以處理掉
作者: nova06091   2017-12-15 09:15:00
老師居然沒自己打過 ...
作者: sdfg014025xx (隨便就好)   2017-12-15 13:11:00
感謝各位!
作者: longlongint (華哥爾)   2017-12-15 21:25:00
我也忘了補位要遞迴 感謝p大
作者: peterwu4 (notd)   2017-12-16 16:20:00
^^"

Links booklink

Contact Us: admin [ a t ] ucptt.com