通过输入实现一个二叉排序树的插入、删除、查找,并且建立起一个二叉排序树
时间: 2024-12-25 20:32:28 浏览: 15
在Java中,我们可以使用递归的方式来实现二叉排序树(Binary Search Tree, BST)的插入、删除和查找操作。首先,我们需要定义一个节点类`TreeNode`,然后创建BST相关的类。
```java
// 定义一个二叉树节点
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
// 创建一个二叉搜索树类
public class BinarySearchTree {
private TreeNode root;
// 插入操作
public void insert(int val) {
root = insertRec(root, val);
}
private TreeNode insertRec(TreeNode node, int val) {
if (node == null) {
return new TreeNode(val);
}
if (val < node.val) {
node.left = insertRec(node.left, val);
} else {
node.right = insertRec(node.right, val);
}
return node;
}
// 删除操作
public void remove(int val) {
root = removeRec(root, val);
}
private TreeNode removeRec(TreeNode node, int val) {
if (node == null) {
return null;
}
if (val < node.val) {
node.left = removeRec(node.left, val);
} else if (val > node.val) {
node.right = removeRec(node.right, val);
} else { // 找到要删除的节点
if (node.left == null && node.right == null) { // 没有子节点,直接删除
node = null;
} else if (node.left == null) { // 只有一个左子节点
node = node.right;
} else if (node.right == null) { // 只有一个右子节点
node = node.left;
} else { // 有两个子节点,找到右子树中的最小值替换当前节点
TreeNode minNode = findMin(node.right);
node.val = minNode.val;
node.right = removeRec(node.right, minNode.val);
}
}
return node;
}
// 查找操作
public boolean search(int val) {
return searchRec(root, val);
}
private boolean searchRec(TreeNode node, int val) {
if (node == null || node.val == val) {
return node != null;
}
return val < node.val ? searchRec(node.left, val) : searchRec(node.right, val);
}
// 辅助方法:查找右子树中的最小值
private TreeNode findMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
// 其他辅助方法(如遍历等)省略...
}
```
阅读全文