java 实现一个BinarySearchTree delete 方法
时间: 2024-05-07 20:15:20 浏览: 12
以下是Java实现BinarySearchTree的delete方法的示例代码:
```
public class BinarySearchTree {
private Node root;
private class Node {
private int key;
private Node left, right;
public Node(int key) {
this.key = key;
}
}
public void delete(int key) {
root = delete(root, key);
}
private Node delete(Node x, int key) {
if (x == null) return null;
if (key < x.key) {
x.left = delete(x.left, key);
} else if (key > x.key) {
x.right = delete(x.right, key);
} else {
if (x.left == null) return x.right;
if (x.right == null) return x.left;
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
return x;
}
private Node min(Node x) {
if (x.left == null) return x;
return min(x.left);
}
private Node deleteMin(Node x) {
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
return x;
}
}
```
在该实现中,delete方法首先调用delete(Node x, int key)方法,传入根节点和待删除的键。 delete(Node x, int key)方法递归遍历二叉搜索树,查找要删除的键所对应的节点。如果找到了该节点,就执行删除操作。如果节点有左右子树,就用它的右子树中的最小值节点来替代这个节点,然后删除右子树中的最小值节点。
delete(Node x, int key)方法还调用了min(Node x)和deleteMin(Node x)方法。min(Node x)方法返回以节点x为根的子树中的最小节点,deleteMin(Node x)方法删除以节点x为根的子树中的最小节点,并返回删除后的子树。
注意:以上代码仅供参考,未经完整测试,可能存在错误,请谨慎使用。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)