介绍
二叉搜索树 (bst) 是一种二叉树，其中每个节点最多有2个子节点，称为左子节点和右子节点。针对每个节点，左子树仅包含值小于该节点值的节点，右子树仅包含值大于该节点值的节点。 bst 用以高效的检索、插进和删除操作。为什么使用二叉搜索树？
bst 几个优势：高效搜索：检索、插进、删掉均值时间复杂度为o(log n)。
动态项目集：适用动态操作，与静态数组不同。
有序原素：bst 的中序遍历会产生按排列次序排列元素。
搭建 bst 的逐层手册
步骤一：界定节点构造
第一步是界定树中节点构造。每个节点将具有三个特性：一个值、对左子节点的引入与对右子节点的引入。
11
publicclasstreenode{
intvalue;
treenodeleft;
treenoderight;
treenode(intvalue){
this.value=value;
this.left=null;
this.right=null;
}
}
第2步：应用构造函数建立bst类
下面，大家建立 bst 类，其中包括对树杆的引入及其插进元素方式。
publicclassbinarysearchtree{
treenoderoot;
publicbinarysearchtree(){
this.root=null;
}
}
第三步：完成插入方法
要把原素插进 bst，大家需要找到新节点的正确位置。插入方法一般完成为递归函数。
publicvoidinsert(intvalue){
root=insertrec(root,value);
}
privatetreenodeinsertrec(treenoderoot,intvalue){
//basecase:ifthetreeisempty,returnanewnode
if(root==null){
root=newtreenode(value);
returnroot;
}
//otherwise,recurdownthetree
if(valueroot.value){
root.right=insertrec(root.right,value);
}
//returnthe(unchanged)nodepointer
returnroot;
}
可视化
为了更好地了解插进是如何工作的，使我们考虑一个例子。假定我们要在 bst 中插进下列数字序列：50, 30, 70, 20, 40, 60, 80。
50
/
30
50
/
3070
50
/
3070
/
插进40：
50
/
3070
/
插进60
50
/
3070
//
插进80：
50
/
3070
//
详细编码
这是建立 bst 和插进元素详细编码：
publicclassBinarySearchTree{
TreeNoderoot;
publicBinarySearchTree(){
this.root=null;
}
publicvoidinsert(intvalue){
root=insertRec(root,value);
}
privateTreeNodeinsertRec(TreeNoderoot,intvalue){
if(root==null){
root=newTreeNode(value);
returnroot;
}
if(valueroot.value){
root.right=insertRec(root.right,value);
}
returnroot;
}
//Additionalmethodsfortraversal,search,anddeletecanbeaddedhere
publicstaticvoidmain(String[]args){
BinarySearchTree bst =newBinarySearchTree();
int[]values={50, 30, 70, 20, 40, 60, 80};
for(intvalue:values){
bst.insert(value);
}
//Addcodetoprintortraversethetree
}
}
classTreeNode{
intvalue;
TreeNodeleft;
TreeNoderight;
TreeNode(intvalue){
this.value=value;
this.left=null;
this.right=null;
}
}
以上就是Java 中重新开始的二叉搜索树的详细内容，大量请关注其他类似文章！