求排序二叉树删除结点的算法

不奢球 · 发表于 2026-4-7 17:10:45

首先判断有没有父节点【若没有父节点，则需要在修改fp的对应子节点的地方改动一下】
然后删除节点有没有子节点
1.如果都没有直接删了父节点fp的对应子节点改为null释放p就行了
2.如果只有一个子节点也好办，直接将fp的对应子节点改为p的这个子节点再释放p就可以了
3.最麻烦的是有2个子节点这种情况你有2个选择，一个是从p的左子树删，就是在p的左子树找到最大的节点【即从p的左节点开始，一直向右，直到没有右子节点的那个就是】，先删除该最大节点【只可能是1，2的情况】，然后将这个最大节点替换树中p的位置【fp的对应子节点设为它，它的子节点设为p的2个子节点】，然后释放p。从p的右子树删也一样，不过是从右子树寻找最小节点替换。
我手头只有java的就不贴出来了

		自动登录	找回密码
密码			立即注册

求排序二叉树删除结点的算法

相关帖子