7.3.1.4 二叉排序树的删除
原书定位
印刷页P285起,对应PDF第297页。下文为目视整理的知识提要;完整内容见原书对照。
分三种情况:叶结点直接摘除;仅一个孩子则由孩子接替;两个孩子则用中序前驱或后继的关键字替换,再删除对应前驱或后继结点。
前驱是左子树最大者,后继是右子树最小者;替代后仍要接好它原有的唯一可能孩子。删除不是把整个子树一起移除。先删后插同一关键字,树形不保证恢复。

二叉排序树删除的三种情况,原书P286。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P285起,对应PDF第297页。下文为目视整理的知识提要;完整内容见原书对照。
分三种情况:叶结点直接摘除;仅一个孩子则由孩子接替;两个孩子则用中序前驱或后继的关键字替换,再删除对应前驱或后继结点。
前驱是左子树最大者,后继是右子树最小者;替代后仍要接好它原有的唯一可能孩子。删除不是把整个子树一起移除。先删后插同一关键字,树形不保证恢复。

二叉排序树删除的三种情况,原书P286。

