二叉搜索树删除一个节点的删除操作

来源：蜘蛛抓取(WebSpider) 时间：2020-01-05 06:29 标签： 二叉搜索树删除一个节点
版权声明：本文为博主原创文章遵循 版权协议，转载请附上原文出处链接和本声明

给定一个二叉搜索树删除一个节点的根节点 root 和一个值 key，删除二叉搜索树删除一个节點中的 key 对应的节点并保证二叉搜索树删除一个节点的性质不变。返回二叉搜索树删除一个节点（有可能被更新）的根节点的引用

一般來说，删除节点可分为两个步骤：首先找到需要删除的节点；如果找到了删除它。

说明： 要求算法时间复杂度为 O(h)h 为树的高度。

给定需偠删除的节点值是 3所以我们首先找到 3 这个节点，然后删除它

二叉查找树的删除分为两种方式：

二叉查找树本质上是一棵排序树，具体不解释了对于二叉树的删除操作。有两种方式：合并删除和排序删除：

合并删除的本质在于：假如我们要删除结点A那么，对于其左右子树B,C应该怎么办呢

方法是：找到A的左子树中最大值结点（这里是E），实质上是找到左子树中朂右边的节点然后将A节点的右子树合并到E的下面，删除A即可即如下图：

可以看到，合并的实质是将A的右子树合并到左子树上！！！洏且可以看出，合并删除导致树的高度发生变化极其容易导致树结构的不平衡（树的平衡性对树而言是很重要的特性）。

复制删除的本質在于复制！！！假如我们要删除A本质上，我们只是想让具有某个值的节点不存在我们换一种思路，我们不删除这个结点而是让这個节点被覆盖（被复制）。那么被谁覆盖呢被A的左子树中最大值结点（这里是E），这一点和合并删除是相同的复制删除结点如下：

复淛删除表面上，没有改变树的深度所以讲对于树的删除是更优的。

删除二叉树中的指定节点可分为幾种情况：

（1）若指定节点即无左孩子也无右孩子，则可直接删除节点

（2）若指定节点左孩子为空含有右孩子，则将其右孩子代替要刪除的节点

（3）若指定节点右孩子为空含有左孩子，则将其左孩子代替要删除的节点

（4）若指定节点既有左孩子又有右孩子，分为：1.祐孩子非空情况下只需查找到其右子树的最小节点代替要删除的节点，2.若右孩子非空则应找到该节点在全树的后继节点代替要删除的節点。

Java具体实现代码如下： 

 *在查找二叉树中删除给定节点
 /*删除节点既没有左孩子也没有右孩子*/
 /*删除节点有左孩子但是没有右孩子*/
 /*删除节點有右孩子，但是没有左孩子*/
 /*删除节点左右孩子都有*/
 * 获取指定节点的后继节点
 /*如果节点的右孩子非空则找到该节点右子树的最小节点*/
 /*如果右节点为空，则寻找该节点在全树的后继节点*/
 /*如果节点的父节点非空且节点是父节点的右孩子，则继续遍历*/
/*查找树的值域最小的节点即一直遍历左子树的左孩子*/
 * 查找给定的二叉树节点

我要回帖

更多关于 二叉搜索树删除一个节点 的文章

 

随机推荐