二叉搜索树

搜索树支持很多动态集合操作，包括寻找，最小项，最大项等等一系列操作。所以可以使用搜索树当作字典或者优先队列。

二叉搜索树是以一棵二叉树来组织的。在二叉搜索树中任意一个节点x来说，其左子树中的关键字最大不大于x.key，其右子树中的关键字最小不小于x.key。大部分搜索树操作的最坏运行时间与树的高度成正比。

中序遍历

public void inorder(TreeNode node){
  while(node!=null){
    inorder(node.left);
    System.out.println(node.key);
    inorder(node.right);
  }
}

得出定理：遍历一棵n个结点子树的根，调用INORDER-TREE-WALK(x)需要O(n)的时间。

找出二叉树中的关键字K

public TreeNode search(TreeNode node, int key){
  while(node!=null&&node.key!=key){
    if(key<node.key)
      node = node.left;
    else
      node = node.right;
  }
  return node;
}

二叉搜索树中的最小元素

public TreeNode getMin(TreeNode node){
  while(node.left!=null){
      node = node.left;
  }
   return node;
 }

二叉搜索树中的最大元素

public TreeNode getMax(TreeNode node){
  while(node.right!=null)
    node = node.right;
  return node;
 }

二叉树的插入元素

public void insert(TreeNode root,int key){
  if(root==null)
    return;
  TreeNode parent;
  while(root!=null){
    parent = root;
    if(key<root.key)
      root = root.left;
    else if(key>root.key)
      root = root.right;
    else
      return;  
  }
  if(key<parent.key)
    parent.left = new TreeNode(key);
  else if(key > parent.key)
    parent.right = new TreeNode(key);
}

二叉树的插入就是遍历二叉树找到合适的点。然后处理该点与二叉树的关系。

二叉搜索树删除元素

二叉搜索树删除元素时需要考虑几种情况：

1. 要删除的节点只有左节点或者只有右节点，直接把节点替换到它的位置
2. 没有子节点，直接删除
3. 有左节点和右节点。这种情况比较复杂，把