通过输入实现一个二叉排序树的插入、删除、查找的实例,并且建立起一个二叉排序树完成测试
时间: 2024-12-25 22:32:31 浏览: 6
在Java中,我们可以使用递归的方式来实现二叉搜索树(Binary Search Tree, BST)的插入、删除和查找操作。首先,我们需要定义一个`TreeNode`类表示二叉树节点:
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
```
接下来,我们创建一个`BST`类,包含这些基本操作的方法:
```java
import java.util.Scanner;
public class BST {
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);
} else if (val < node.val) {
node.left = insertRec(node.left, val);
} else {
node.right = insertRec(node.right, val);
}
return node;
}
// 删除方法,这里简化为删除值等于给定值的节点,不考虑其他复杂情况
public void delete(int val) {
root = deleteRec(root, val);
}
private TreeNode deleteRec(TreeNode node, int val) {
if (node == null) {
return null;
} else if (val < node.val) {
node.left = deleteRec(node.left, val);
} else if (val > node.val) {
node.right = deleteRec(node.right, val);
} else {
// 如果只有一个子节点或没有子节点的情况
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
// 找到右子树中的最小元素替换当前节点
TreeNode temp = findMin(node.right);
node.val = temp.val;
node.right = deleteRec(node.right, temp.val); // 递归删除
}
}
return node;
}
// 查找方法
public boolean search(int val) {
return searchRec(root, val);
}
private boolean searchRec(TreeNode node, int val) {
if (node == null) {
return false;
} else if (node.val == val) {
return true;
} else if (val < node.val) {
return searchRec(node.left, val);
} else {
return searchRec(node.right, val);
}
}
// 辅助方法找到右子树中的最小元素
private TreeNode findMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
// 主函数,用于测试
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BST tree = new BST();
System.out.println("Enter numbers to build the tree or -1 to stop:");
while (true) {
int val = scanner.nextInt();
if (val == -1) {
break;
}
tree.insert(val);
}
scanner.close();
System.out.println("Enter a value to search for:");
int searchVal = scanner.nextInt();
boolean found = tree.search(searchVal);
System.out.printf("Value %d is found in the tree? %b%n", searchVal, found);
System.out.println("Enter a value to delete:");
int deleteVal = scanner.nextInt();
tree.delete(deleteVal);
// 你可以选择再次查找删除后的结果,看是否正确
// ...
}
}
```
这个例子中,我们在主函数中构建了一个简单的二叉搜索树并进行了插入、搜索和删除的操作。用户可以通过输入来交互。注意,这个实现没有处理所有可能的删除场景,例如删除具有两个子节点的节点时,它简单地选择了右子树中的最小元素进行替换。
阅读全文