作者sdfg014025xx (隨便就好)
看板C_and_CPP
標題[問題]
時間Thu Dec 14 18:32:11 2017
開發平台(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)：
因為只有這邊搞不懂所以主程式和其他的標頭
檔就沒有附了，我查了刪除是把取代的節點資
料替換，然後刪掉最後的葉節點，可是這支程
式碼替換的地方看的不是很懂...卡了很久，拜
託各位救我，感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.169.134
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1513247534.A.7B3.html
※ 編輯: sdfg014025xx (180.217.169.134), 12/14/2017 18:32:39
※ 編輯: sdfg014025xx (180.217.169.134), 12/14/2017 18:33:50
1F：→ longlongint: 先看抽象概念 刪除 node 後要找一個 node 來頂位置12/14 19:20
2F：→ longlongint: 這個 node key 要比左邊全部大 比右邊全部小，自然12/14 19:20
3F：→ longlongint: 是挑右子樹的最小值來用囉12/14 19:20
※ 編輯: sdfg014025xx (180.217.169.134), 12/14/2017 19:26:31
4F：→ sdfg014025xx: 概念上大概了解...可是程式的實作有點看不懂 12/14 19:28
5F：→ galic: 因為程式碼錯了.. 12/14 20:24
6F：→ sdfg014025xx: 真的嗎？這是老師出作業挖空給我們寫的 12/14 20:39
7F：→ galic: 因為課本寫錯了 老師傻傻相信 慘 12/14 21:53
8F：→ sdfg014025xx: 可是照這樣的程式碼跑一些測資還是對的，可以請教一 12/14 22:08
9F：→ sdfg014025xx: 下他錯在哪嗎QQ 這邊卡住很久 12/14 22:08
11F：→ galic: 第三．Deleting a node with two children... 12/14 22:15
12F：→ galic: D就是你要刪的點 E是找到in-order順序大一位要來替代的點 12/14 22:15
13F：→ galic: E可能有right sub-tree F 12/14 22:16
14F：→ galic: 用E的值覆蓋D E沒有右子就刪除node 但E可能有右子F 12/14 22:17
15F：→ galic: 這時候應該是要F去替換E 而不是把F變成D的右子 12/14 22:18
16F：→ galic: 那D原本的右子去哪了? 12/14 22:18
18F：推 peterwu4: 其實不複雜，換完值後，要刪除的點就是葉子或是一個子 12/14 22:44
19F：→ peterwu4: node的點，利用recursive的概念，把那個點再餵回去就可 12/14 22:46
20F：→ peterwu4: 以處理掉 12/14 22:46
21F：推 nova06091: 老師居然沒自己打過 ... 12/15 09:15
22F：→ sdfg014025xx: 感謝各位！ 12/15 13:11
23F：推 longlongint: 我也忘了補位要遞迴 感謝p大 12/15 21:25
24F：推 peterwu4: ^^" 12/16 16:20