简介
二叉搜索树 (bst) 是一种二叉树,其中每个节点最多有两个子节点,称为左子节点和右子节点。对于每个节点,左子树仅包含值小于该节点值的节点,右子树仅包含值大于该节点值的节点。 bst 用于高效的搜索、插入和删除操作。
为什么使用二叉搜索树?
bst 有几个优点:
高效搜索:搜索、插入、删除平均时间复杂度为o(log n)。
动态项目集:支持动态操作,与静态数组不同。
有序元素:bst 的中序遍历会产生按排序顺序排列的元素。
构建 bst 的分步指南
步骤一:定义节点结构
第一步是定义树中节点的结构。每个节点将具有三个属性:一个值、对左子节点的引用和对右子节点的引用。
public class treenode {
int value;
treenode left;
treenode right;
treenode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
登录后复制
第2步:使用构造函数创建bst类
接下来,我们创建 bst 类,其中包含对树根的引用以及插入元素的方法。
public class binarysearchtree {
treenode root;
public binarysearchtree() {
this.root = null;
}
}
登录后复制
第三步:实现插入方法
要将元素插入 bst,我们需要找到新节点的正确位置。插入方法通常实现为递归函数。
public void insert(int value) {
root = insertrec(root, value);
}
private treenode insertrec(treenode root, int value) {
// base case: if the tree is empty, return a new node
if (root == null) {
root = new treenode(value);
return root;
}
// otherwise, recur down the tree
if (value root.value) {
root.right = insertrec(root.right, value);
}
// return the (unchanged) node pointer
return root;
}
登录后复制
可视化
为了更好地理解插入是如何工作的,让我们考虑一个例子。假设我们要在 bst 中插入以下数字序列:50, 30, 70, 20, 40, 60, 80。
50
登录后复制
50
/
30
登录后复制
50
/ \
30 70
登录后复制
50
/ \
30 70
/
登录后复制
插入40:
50
/ \
30 70
/ \
登录后复制
插入60
50
/ \
30 70
/ \ /
登录后复制
插入80:
50
/ \
30 70
/ \ / \
登录后复制
完整代码
这是创建 bst 和插入元素的完整代码:
public class BinarySearchTree {
TreeNode root;
public BinarySearchTree() {
this.root = null;
}
public void insert(int value) {
root = insertRec(root, value);
}
private TreeNode insertRec(TreeNode root, int value) {
if (root == null) {
root = new TreeNode(value);
return root;
}
if (value root.value) {
root.right = insertRec(root.right, value);
}
return root;
}
// Additional methods for traversal, search, and delete can be added here
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
int[] values = {50, 30, 70, 20, 40, 60, 80};
for (int value : values) {
bst.insert(value);
}
// Add code to print or traverse the tree
}
}
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
登录后复制
以上就是Java 中从头开始的二叉搜索树的详细内容,更多请关注php中文网其它相关文章!
91资源网站长-冰晨2024-08-27 17:15
发表在:【账号直充】爱奇艺黄金VIP会员『1个月』官方直充丨立即到账丨24小时全天秒单!不错不错,价格比官方便宜
91资源网站长-冰晨2024-08-27 16:15
发表在:2022零基础Java入门视频课程不错,学习一下