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

看板C_and_CPP作者 (隨便就好)時間8年前 (2017/12/14 18:32), 8年前編輯推噓4(4推 0噓 20→)
留言24則, 5人參與, 8年前最新討論串1/1
開發平台(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://www.ptt.cc/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
→
12/14 19:20, 8年前 , 1F
先看抽象概念 刪除 node 後要找一個 node 來頂位置
12/14 19:20, 1F
→
12/14 19:20, 8年前 , 2F
這個 node key 要比左邊全部大 比右邊全部小，自然
12/14 19:20, 2F
→
12/14 19:20, 8年前 , 3F
是挑右子樹的最小值來用囉
12/14 19:20, 3F
※ 編輯: sdfg014025xx (180.217.169.134), 12/14/2017 19:26:31
→
12/14 19:28, 8年前 , 4F
概念上大概了解...可是程式的實作有點看不懂
12/14 19:28, 4F
→
12/14 20:24, 8年前 , 5F
因為程式碼錯了..
12/14 20:24, 5F
→
12/14 20:39, 8年前 , 6F
真的嗎？這是老師出作業挖空給我們寫的
12/14 20:39, 6F
→
12/14 21:53, 8年前 , 7F
因為課本寫錯了 老師傻傻相信 慘
12/14 21:53, 7F
→
12/14 22:08, 8年前 , 8F
可是照這樣的程式碼跑一些測資還是對的，可以請教一
12/14 22:08, 8F
→
12/14 22:08, 8年前 , 9F
下他錯在哪嗎QQ 這邊卡住很久
12/14 22:08, 9F
→
12/14 22:14, 8年前 , 10F
12/14 22:14, 10F
→
12/14 22:15, 8年前 , 11F
第三．Deleting a node with two children...
12/14 22:15, 11F
→
12/14 22:15, 8年前 , 12F
D就是你要刪的點 E是找到in-order順序大一位要來替代的點
12/14 22:15, 12F
→
12/14 22:16, 8年前 , 13F
E可能有right sub-tree F
12/14 22:16, 13F
→
12/14 22:17, 8年前 , 14F
用E的值覆蓋D E沒有右子就刪除node 但E可能有右子F
12/14 22:17, 14F
→
12/14 22:18, 8年前 , 15F
這時候應該是要F去替換E 而不是把F變成D的右子
12/14 22:18, 15F
→
12/14 22:18, 8年前 , 16F
那D原本的右子去哪了?
12/14 22:18, 16F
→
12/14 22:28, 8年前 , 17F
附個圖給你 紅色是錯的 https://i.imgur.com/BA6JDUd.png
12/14 22:28, 17F
推
12/14 22:44, 8年前 , 18F
其實不複雜，換完值後，要刪除的點就是葉子或是一個子
12/14 22:44, 18F
→
12/14 22:46, 8年前 , 19F
node的點，利用recursive的概念，把那個點再餵回去就可
12/14 22:46, 19F
→
12/14 22:46, 8年前 , 20F
以處理掉
12/14 22:46, 20F
推
12/15 09:15, 8年前 , 21F
老師居然沒自己打過 ...
12/15 09:15, 21F
→
12/15 13:11, 8年前 , 22F
感謝各位！
12/15 13:11, 22F
推
12/15 21:25, 8年前 , 23F
我也忘了補位要遞迴 感謝p大
12/15 21:25, 23F
推
12/16 16:20, 8年前 , 24F
^^"
12/16 16:20, 24F
‣ 更多 sdfg014025xx 的文章
文章代碼(AID): #1QCbCkUp (C_and_CPP)