[问题]二元树删除左右皆有子树的节点

楼主: 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