算法之二叉排序树的其它知识点讲解-二叉树删除

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

各位小伙伴们大家好呀，本篇文章将会为大家讲解下二叉排序树删除的内容，删除虽然不是常考点，但也需要掌握其原理，下面就开始我们的讲解吧！

一、重要知识点

（1）中序遍历二叉排序树可得到关键字的有序序列；

（2）每次在二叉排序树中插入新结点都将是二叉排序树上新的叶子结点；

（3）二叉排序树的存储结构一般选用二叉链表；

（4）二叉排序树也称为二叉查找树；

二、二叉排序树的删除

假设待删除的结点为cur，其父节点为parent，二叉树的删除遵循删除结点后需要保持二叉排序树的特性。

二叉树删除步骤：

1.若当前结点cur为叶子结点，即左右孩子为空，则直接删除该结点即可，删除该结点并不破坏二叉排序树的结构，需要使父节点parent的指向该结点的指针为空；

2.若当前结点cur的左孩子或右孩子为空，则直接让父结点parent指向cur结点的左孩子或右孩子即可；

3.若当前结点cur的左孩子和右孩子均不为空，有两种处理方式：

• 让cur的左子树成为parent的左子树，cur的右子树为cur直接前驱结点的右子树；

• 让cur的直接前驱（或直接后继）替代cur，然后从二叉排序树中删除cur的直接前驱（或直接后继）；

PS:

直接前驱：小于cur结点data值并且值最大的节点 ，中序遍历cur前面的第一个结点；

直接后继：大于cur结点data值并且值最小的结点，中序遍历cur后面的第一个结点；

举例，假设有如下二叉排序树：

（1）删除叶子结点：如果删除值为43的结点，只需修改值为45结点的左孩子指针，然后释放值为43的结点即可；

（2）删除只有一个左孩子或右孩子的结点：如果删除值为45的结点，只需要将值为40结点的右孩子指针指向43结点即可，然后释放值为45的结点；删除值为200的结点同理；

（3）删除既有左孩子，又有右孩子的结点：如果删除值为50的结点，有两种方法：

• 方法一、让值为30的结点成为值为100结点的左孩子，值为70的结点成为值为45结点的右孩子；

• 方法二、让值为45的结点代替值为50的结点，45结点的左孩子43成为值为40结点的右孩子；

三、总结

二叉排序树经常考的是查找和插入的操作，删除操作也需要理解其原理。二叉排序树的平均查找长度是一个重要且经常考的考点，后面在讲平均查找长度的时候会一并讲解，大家有不理解的可以在评论区留言哦！

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬