二叉搜索树

定义

所谓二叉搜索树 又叫二叉排序树 二叉排序树的充分条件为

• 如果他的左子树不为空 则其左子树的所有节点的 VALUE 都小于 Root 的 VALUE
• 如果他的右子树不为空 则其右子树的所有节点的 VALUE 都大于 Root 的 VALUE
• 他的左右子树也都为二叉排序树

定义一个节点

 public class Node {
     int key;           // 节点的key
	 int value;        //节点的卫星数据
	 Node left;        //此节点的左子节点，数据类型为Node
	 Node right;       //此节点的右子节点，数据类型为Node
	
    //构造方法 
	public Node(int key) {
        this.key = key;
		this.value=null;
		this.left=null;
		this.right=null;
	}
}

二叉排序树的搜索

查找非常方便

public Node find(int key，Node root)
{ 
    // 从树中按照key查找元素
    Node current = root;
    while (current.key!= key)
    {
        if (key > current.key)
            current = current.right;
        else
            current = current.left;
            //如果子节点为空 说明该元素不存在
        if (current == null) return null;
    }
    return current;
}

二叉排序树的插入

public boolean insertOneNode(int key,Node root) {
       Node node = new Node(key);
       if(root == null) {
           root = node;
           return true;
       }
       Node parent = null;
       Node cur = root;
       while (cur != null) {
           if(cur.key == key) {
               //不允许插入相同key的node
               return false;
           }else if(cur.key > key) {
               parent = cur;
               cur = cur.left;
           }else{
               parent = cur;
               cur = cur.right;
           }
       }
       if (parent.key > key) {
           parent.left = node;
       }else{
           parent.right = node;
       }
       return true;
   }

二叉排序树的删除

只有左子树为空的情况

• 当前节点根节点，删除后根节点为当前节点的右孩子节点
• 当前节点不是根节点，且当前节点是父亲节点的左孩子节点，则删除后父亲节点的左孩子节点为，当前节点的右孩子节点
• 当前节点不是根节点，且当前节点是父亲节点的右孩子节点，则删除后父亲节点的右孩子节点为，当前节点的右孩子节点

只有右子树为空的情况

• 当前节点根节点，删除后根节点为当前节点的左孩子节点
• 当前节点不是根节点，且当前节点是父亲节点的左孩子节点，则删除后父亲节点的左孩子节点为，当前节点的左孩子节点
• 当前节点不是根节点，且当前节点是父亲节点的右孩子节点，则删除后父亲节点的右孩子节点为，当前节点的左孩子节点

左右子树都不为空的情况

• 找到要删除节点，右树最左边的节点或者找到左树最右边的节点，随便一个都可以，设该节点为target节点
  那么将当前节点删除本质上为将target节点的key 和 卫星数据 给 当前节点 然后将 target节点删除 。
• 如果找到的是右树最左边的节点为target 则(伪代码) target的左子树为空 target.parent.left = target.right
• 如果找到的是左树的最右边的节点为 target 则(伪代码) target的右子树为空 target.parent.right = target.left

public boolean removeKeyNode(int key,Node root) {
       if(root == null) {
           return false;
       }
       Node parent = null;
       Node cur = root;
       while (cur != null) {
           if(cur.key == key) {
               removeNode(parent,cur,root);
               return true;
           }else if(cur.key < key) {
               parent = cur;
               cur = cur.right;
           }else{
               parent = cur;
               cur = cur.left;
           }
       }
       //没有找到需要删除的节点
       return false;
   }
   public void removeNode(Node parent,Node cur,Node root) {
       // 左子树为空的情况 
       if(cur.left == null) {
           if(cur == root) {
               root = root.right;
           }else if(cur == parent.left) {
               parent.left = cur.right;
           }else{
               parent.right = cur.right;
           }
           // 右子树为空的情况
       }else if(cur.right == null) {
           if(root == cur) {
               root = root.left;
           }else if(cur == parent.left) {
               parent.left = cur.left;
           }else{
               parent.right = cur.left;
           }
       }else{
           // 左右都不为空的情况 这里选择为找右子树的最左边的节点 也就是右子树的最小值
           Node targetParent = cur;
           Node target = cur.right;
           while (target.left != null) {
               targetParent = target;
               target = target.left;
           }
           //将target的key和数据给当前需要删除的节点
           cur.key = target.key;
           // cur.value  = target.value 卫星数据更换
          targetParent.left = target.right;
       }
   }