Java中Binary Search树介绍
导读：Binary Search Tree（二叉搜索树）是一种常见的数据结构，它是一种二叉树，其中每个节点最多只有两个子节点，并且满足以下性质： 左子树中的所有节点的值都小于当前节点的值。 右子树中的所有节点的值都大于当前节点的值。 左右子树也...
Binary Search Tree（二叉搜索树）是一种常见的数据结构，它是一种二叉树，其中每个节点最多只有两个子节点，并且满足以下性质：
- 左子树中的所有节点的值都小于当前节点的值。
- 右子树中的所有节点的值都大于当前节点的值。
- 左右子树也都是二叉搜索树。
由于满足上述性质，二叉搜索树可以支持高效的搜索、插入和删除操作。搜索操作的时间复杂度为O(log n)，其中n为树中节点的数量。
Java中可以通过自定义节点类和二叉搜索树类来实现Binary Search Tree。下面是一个简单的实现示例：
class Node {
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class BST {
private Node root;
public BST() {
this.root = null;
}
public void insert(int val) {
this.root = insertNode(root, val);
}
private Node insertNode(Node root, int val) {
if (root == null) {
return new Node(val);
}
if (val <
root.val) {
root.left = insertNode(root.left, val);
}
else {
root.right = insertNode(root.right, val);
}
return root;
}
public boolean search(int val) {
return searchNode(root, val);
}
private boolean searchNode(Node root, int val) {
if (root == null) {
return false;
}
if (val == root.val) {
return true;
}
else if (val <
root.val) {
return searchNode(root.left, val);
}
else {
return searchNode(root.right, val);
}
}
public void delete(int val) {
this.root = deleteNode(root, val);
}
private Node deleteNode(Node root, int val) {
if (root == null) {
return null;
}
if (val <
root.val) {
root.left = deleteNode(root.left, val);
}
else if (val >
root.val) {
root.right = deleteNode(root.right, val);
}
else {
if (root.left == null) {
return root.right;
}
else if (root.right == null) {
return root.left;
}
root.val = findMin(root.right);
root.right = deleteNode(root.right, root.val);
}
return root;
}
private int findMin(Node root) {
int min = root.val;
while (root.left != null) {
min = root.left.val;
root = root.left;
}
return min;
}
}
在上面的代码中，我们定义了Node类表示二叉搜索树的节点，以及BST类表示二叉搜索树。我们实现了插入、搜索和删除操作，可以通过这些操作来操作二叉搜索树。
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： Java中Binary Search树介绍
本文地址： https://pptw.com/jishu/687326.html