对于排序二叉树删除节点的一些理解

1、删除叶子节点,这个没有什么特别的地方,找到目标节点然后通过父节点进行删除就可以了
2、删除有一颗子树的节点,先找到目标节点target,然后找到目标节点的父节点parent,分为几种情况
1)target是parent的左子树,target有左子树
对于排序二叉树删除节点的一些理解
比如说这个,我们要删除8的话,直接让parent.left = target.left就可以了,其他三种情况,也是一样的
2)target是parent的左子树,target有右子树
对于排序二叉树删除节点的一些理解
我们删除6,就是parent.left = target.right
3)target是parent的右子树,target有左子树
对于排序二叉树删除节点的一些理解
我们删除14的话就是,parent.right = target.left
4)target是parent的右子树,target有右子树
对于排序二叉树删除节点的一些理解
我们要删除14的话就是parent.right = target.right
5)但是当我们的target没有父节点时,也就是target是根节点,此时我们直接让根节点是变成target的子树就好了,比如:root = target.left 。
3、当要删除节点有两个子树的时候
我们采用使用左子树的最右侧节点来(也就是左子树的最大节点)代替目标节点
对于排序二叉树删除节点的一些理解
比如说这个,我们要删除10节点,他有两个子树,我们使用左子树中最大的一个来代替它,也就是8,我们先找到目标节点10target,再找到8temp,然后让target.val = temp.val;也就是进行了替换,但是此时我们还需要将8删除掉,此时又分8有左子树(不可能有右子树,他已经是最右的了)和8是叶子节点,按照上面的删除方法进行删除即可
以上就是对于排序二叉树删除节点的一些理解,希望大家指正

上一篇:2016年中国软件业务收入前百家企业名单发布


下一篇:std::make_shared的误用造成的内存泄露