BSTjava代码运行
时间: 2023-09-26 14:09:38 浏览: 29
以下是一个简单的二叉搜索树(Binary Search Tree,BST)Java 代码示例:
``` java
public class BinarySearchTree {
private TreeNode root;
// 插入节点
public void insert(int value) {
if (root == null) {
root = new TreeNode(value);
return;
}
TreeNode current = root;
while (true) {
if (value < current.value) {
if (current.left == null) {
current.left = new TreeNode(value);
return;
}
current = current.left;
} else {
if (current.right == null) {
current.right = new TreeNode(value);
return;
}
current = current.right;
}
}
}
// 查找节点
public boolean contains(int value) {
TreeNode current = root;
while (current != null) {
if (value == current.value) {
return true;
} else if (value < current.value) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
// 中序遍历
public void inOrderTraversal() {
inOrderTraversal(root);
}
private void inOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.left);
System.out.print(node.value + " ");
inOrderTraversal(node.right);
}
// 删除节点
public void remove(int value) {
root = remove(root, value);
}
private TreeNode remove(TreeNode node, int value) {
if (node == null) {
return null;
}
if (value < node.value) {
node.left = remove(node.left, value);
} else if (value > node.value) {
node.right = remove(node.right, value);
} else {
// 找到要删除的节点
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
}
// 找到右子树的最小节点
TreeNode minNode = node.right;
while (minNode.left != null) {
minNode = minNode.left;
}
// 替换要删除的节点的值
node.value = minNode.value;
// 删除右子树的最小节点
node.right = remove(node.right, minNode.value);
}
return node;
}
}
class TreeNode {
int value;
TreeNode left;
TreeNode right;
public TreeNode(int value) {
this.value = value;
}
}
```
这个示例实现了一个二叉搜索树,可以插入、查找、中序遍历和删除节点。在程序运行时,你可以创建一个 `BinarySearchTree` 对象,并使用 `insert` 方法插入节点,使用 `contains` 方法查找节点,使用 `inOrderTraversal` 方法中序遍历节点,使用 `remove` 方法删除节点。例如:
``` java
BinarySearchTree bst = new BinarySearchTree();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(1);
bst.insert(9);
System.out.println(bst.contains(3)); // true
bst.inOrderTraversal(); // 输出 1 3 5 7 9
bst.remove(5);
bst.inOrderTraversal(); // 输出 1 3 7 9
```