简介：
二叉搜索树的就是一棵二叉树，他满足节点的左孩子值不大于节点的值，右孩子的值不小于节点的值。一般来说有插入，和删除，以及遍历操作。 其中插入与删除的时间复杂度为一般情况下O（log（n）），最坏退化为链表O（n） ，遍历：时间复杂度O（n）。
详细参考。
代码实现：
import java.util.Deque;
import java.util.LinkedList;
public class BST {//二叉搜索树
public static class TreeNode{
int val;
TreeNode left,right;
public TreeNode(int val)
{
this.val=val;
this.left=null;
this.right=null;
}
}
public static TreeNode makeEmpty(TreeNode node)//清空
{
if(node==null) return null;
makeEmpty(node.left);
makeEmpty(node.right);
node=null;
return null;
}
//插入子树
public static TreeNode insert(TreeNode node,int val)//时间复杂度O(log n)
{
if(node==null)
node=new TreeNode(val);
else if(node.val>val)//值小于节点的值，插入左子树。
node.left=insert(node.left,val);
else
node.right=insert(node.right,val);
return node;
}
public TreeNode find(TreeNode root,int val)//寻找对应值的节点 找不到返回为空
{
if(root==null) return null;
if(root.val>val) return find(root.left,val);
else if(root.val<val) return find(root.right,val);
else return root;
}
public static TreeNode findMin(TreeNode root)
{
if(root==null||root.left==null) return root;
return findMin(root.left);
}
public static TreeNode findMax(TreeNode root)
{
if(root==null||root.right==null) return root;
return findMax(root.right);
}
public static TreeNode remove(TreeNode node,int val)
{
if(node==null) return null;
if(node.val>val) node.left=remove(node.left,val);//向左子树移动
else if(node.val<val) node.right=remove(node.right,val);
else if(node.left!=null&&node.right!=null)
{
TreeNode temp=findMin(node.right);//找到比他大的最小值
node.val=temp.val;//找到最小值的点，将那个点的值移动到当前点
node.right=remove(node.right,node.val);//将最小值点删除
}
else
{
if(node.left==null) node=node.right;
else if(node.right==null) node=node.left;
}
return node;
}
public static void hOrder(TreeNode root)//层次遍历
{
Deque<TreeNode> que=new LinkedList<>();
if(root==null) return;
que.add(root);
while(!que.isEmpty())
{
int len=que.size();
for(int i=0;i<len;i++)
{
TreeNode temp=que.peek();
que.pop();
System.out.print(temp.val+" ");
if(temp.left!=null) que.add(temp.left);
if(temp.right!=null) que.add(temp.right);
}
System.out.println();
}
return;
}
public static void main(String[] args) {
TreeNode root=null;
for(int i=1;i<10;i+=2)//插入
{
root=insert(root,i);
root=insert(root,i-5);
}
hOrder(root);
root=remove(root,2);
System.out.println();
hOrder(root);
System.out.println();
System.out.println("最大值："+findMax(root).val);
System.out.println("最小值："+findMin(root).val);
}
}
结果：
1
-4 3
-2 2 5
0 4 7
9
1
-4 3
-2 5
0 4 7
9
最大值：9
最小值：-4
| 
转播
