Java删除二叉搜索树的任意元素的方法详解

Java删除二叉搜索树的任意元素的方法详解

本文实例讲述了java删除二叉搜索树的任意元素的方法。分享给大家供大家参考，具体如下：

一.删除思路分析

在删除二叉搜索树的任意元素时，会有三种情况：

1.1 删除只有左孩子的节点

节点删除之后，将左孩子所在的二叉树取代其位置；连在原来节点父亲元素右节点的位置，比如在图中需要删除58这个节点。

删除58这个节点后，如下图所示：

1.2 删除只有右孩子的节点：

节点删除之后，将右孩子所在的二叉树取代其位置；连在原来节点的位置，比如在下图中需要删除58这个节点。

删除58这个节点后，如下图所示：

这里需要说明说一下，以上两种情况其实包含了叶子节点情况的，我们可以把叶子节点理解成只有左孩子的节点，也可以把它理解为只有右孩子的节点，只不过左孩子、右孩子为null。

1.3 删除包含左右孩子的节点

如下图，二叉搜索树包含有左右孩子，假设现需要删除58这个节点。

针对该种情况，分析如下：

我们把58这个节点记为d节点（包含有左子树与右子树）,如下图所示：

针对这种节点删除情况需要把左子树与右子树融合起来，融合方法：

从d这节点的左孩子与右孩子中找一个比d节点还要大的节点取代d节点，根据二叉搜索树的性质可知（左边节点<当前节点<右边节点），这个需要被找的节点存在于d节点的右孩子节点中。

寻找规则：

寻找需要被删除节点58(d)的后继的所有元素中，离 58 最近的且比 58 大的节点，在本例中为59这个节点【即右子树中的最小值】，记为s，如下图所示：

删除步骤：

（1）从d的右子树中删除最小值，将删除最小值s后的d的右子树, 变为d后继节点s的右孩子，如下图所示：

（2）将d节点（58节点）的左子树，变为后继节点s(59节点http://)的左子树，如下图所示：

(3)将后继节点s（59节点）连接到d节点（58节点）父亲节点的右边，删除d节点（58节点）后,后继s节点（59节点）成为新的根，如下图所示：

二、编码实现二叉搜索树的任意元素

根据上述的分析，在此基础上进行编码，删除代码如下：

//从二叉搜索树中删除元素为e的节点

public void remove(E e) {

root = remove(root, e);

}

//删除以node为根的二叉搜索树中值为e的节点，递归算法

//返回删除节点后更新的二叉搜索树的根

private Node remove(Node node, E e) {

if (node == null)

return null;

if (e.compareTo(node.e) < 0) {//e

node.left = remove(node.left, e);

return node;

}

if (e.compareTo(node.e) > 0) {//e>node.e (被删除元素e大于当前节点值e)

node.right = remove(node.right, e);

return node;

} else {//e==node.e (被删除元素e等于当前节点值e)

//待删除节点左子树为空情况

if (node.left == null) {

Node rightNode = node.right;

node.right = null;

size--;

return rightNode;

}

//待删除节点右子树为空情况

if (node.right == null) {

Node leftNode = node.left;

node.left = null;

size--;

return leftNode;

}

//左右子树均不为空

//方法：找到比待删除节点大的最小节点，即待删除节点右子树的最小节点

//用这个节点顶替待删除节点的位置

Node successor = minimum(node.right);

successor.right = removeMin(node.right);

successor.left = node.left;

node.left = node.right = null;

return successor;

}

}

对于上述代码中的minimum函数，在5.3节中已经实现，此处同样也把代码列出来：

// 寻找二分搜索树的最小元素

public E minimum() {

if (size == 0) {

throw new IllegalArgumentException("BST is empty");

}

Node ninNode = minimum(root);

return ninNode.e;

}

// 返回以node为根的二分搜索树的最小值所在的节点

private Node minimum(Node node) {

if (node.left == null) {

return node;

}

//返回相应的节点的左子树的最小值

return minimum(node.left);

}

源码地址 https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

node.left = remove(node.left, e);

return node;

}

if (e.compareTo(node.e) > 0) {//e>node.e (被删除元素e大于当前节点值e)

node.right = remove(node.right, e);

return node;

} else {//e==node.e (被删除元素e等于当前节点值e)

//待删除节点左子树为空情况

if (node.left == null) {

Node rightNode = node.right;

node.right = null;

size--;

return rightNode;

}

//待删除节点右子树为空情况

if (node.right == null) {

Node leftNode = node.left;

node.left = null;

size--;

return leftNode;

}

//左右子树均不为空

//方法：找到比待删除节点大的最小节点，即待删除节点右子树的最小节点

//用这个节点顶替待删除节点的位置

Node successor = minimum(node.right);

successor.right = removeMin(node.right);

successor.left = node.left;

node.left = node.right = null;

return successor;

}

}

对于上述代码中的minimum函数，在5.3节中已经实现，此处同样也把代码列出来：

// 寻找二分搜索树的最小元素

public E minimum() {

if (size == 0) {

throw new IllegalArgumentException("BST is empty");

}

Node ninNode = minimum(root);

return ninNode.e;

}

// 返回以node为根的二分搜索树的最小值所在的节点

private Node minimum(Node node) {

if (node.left == null) {

return node;

}

//返回相应的节点的左子树的最小值

return minimum(node.left);

}

源码地址 https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。