二叉排序树

对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。如果有相同的值，可以将该节点放在左子节点或右子节点。

二叉排序树的创建和遍历

思路：比较节点的值，小于就放在左子节点，大于就放在右子节点，如果子节点不为空，就递归添加。

	//添加节点
    public void add(Node node){
         if(node==null){
             return;
         }
         if(node.value<this.value){
             if(this.left==null){
                 this.left=node;
             }else{
                 this.left.add(node);
             }
         }else {
             if(this.right==null){
                 this.right=node;
             }else {
                 this.right.add(node);
             }
         }
    }
    //中序遍历
    public void midOrder(){
         if(this.left!=null){
             this.left.midOrder();
         }
        System.out.println(this);
         if(this.right!=null){
             this.right.midOrder();
         }
    }

二叉排序树删除节点

思路：首先要保证能根据值找到那个要删除的节点和它的父节点。
分为5种情况：

1. 要删除的值不存在，也就是目标节点为null，直接返回。
2. 只有一个根节点的情况，直接root=null。
3. 要删除的是叶子节点。需判断目标节点是父节点的左子节点还是右子节点，通过parent.left=null或parent.right=null删除。
4. 删除有一颗子树的节点。首先判断父节点是否为空，如果为空，情况就是删除有一棵子树的根节点，直接让root=target.left或.right。如果父节点不为空，就要判断目标节点是父节点的左右子节点和目标节点的子树是左右子树，一共对应4种可能性。
5. 删除有两棵子树的节点。寻找右子树的最小值或左子树的最大值，将该值赋给目标节点，并将那个最小值或最大值节点删除。

package binarySortTree;

/**
 * 二叉排序树
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] num={7, 3};
        BinarySortTree binarySortTree = new BinarySortTree();
        for(int i:num){
            binarySortTree.add(new Node(i));
        }
        binarySortTree.midOrder();
        System.out.println("-----------");
        binarySortTree.delNode(3);
        binarySortTree.midOrder();

    }
}
//二叉排序树
class BinarySortTree{
    Node root;
    //添加节点
    public void add(Node node){
        if(root==null){
            root=node;
        }else {
            root.add(node);
        }
    }
    //中序遍历
    public void midOrder(){
        if(root==null){
            System.out.println("空树");
        }else {
            root.midOrder();
        }
    }
    //寻找节点
    public Node search(int value){
        if(root==null){
            System.out.println("空树");
            return null;
        }else {
            return root.search(value);
        }
    }
    //寻找父节点
    public Node searchFather(int value){
        if(root==null){
            System.out.println("空树");
            return null;
        }else {
            return root.searchFather(value);
        }
    }
    //寻找某棵子树的最小值，返回并删除它
    public int searchMin(Node node){
        Node temp=node;
        while (temp.left!=null){
            temp=temp.left;
        }
        delNode(temp.value);
        return temp.value;
    }
    //删除节点
    public void delNode(int value){
        //空树
        if(root==null){
            return;
        }
        Node target=root.search(value);
        //说明没找到
        if(target==null){
            return;
        }
        //如果只有一个根节点
        if(root.left==null && root.right==null){
            root=null;
            return;
        }
        //要删除的是叶子节点
        Node parent=root.searchFather(value);
        if(target.left==null && target.right==null){
            //是左子节点
            if(parent.left!=null && target.value==parent.left.value){
                parent.left=null;
            }else if(parent.right!=null && target.value==parent.right.value) {
                //是右子节点
                parent.right=null;
            }
        }else if(target.left!=null && target.right!=null){
            //要删除的节点有两棵子树
            target.value=searchMin(target.right);
        }else {
            //要删除的节点有一棵子树
            //根节点有一棵子树
            if(parent==null){
                if(target.left!=null && target.value==root.value){
                    root=target.left;
                }else if(target.right!=null && target.value==root.value){
                    root=target.right;
                }
            }else {
                //非根节点有一棵子树
                //是父的左子树
                if(parent.left!=null && parent.left.value==target.value){
                    //目标有左子树
                    if(target.left!=null){
                        parent.left.value=target.left.value;
                        target.left=null;
                    }else {
                        //目标有右子树
                        parent.left.value=target.right.value;
                        target.right=null;
                    }
                }else {
                    //是父的右子树
                    //目标有左子树
                    if(target.left!=null){
                        parent.right.value=target.left.value;
                        target.left=null;
                    }else {
                        //目标有右子树
                        parent.right.value=target.right.value;
                        target.right=null;
                    }
                }
            }
        }

    }
}

//树节点
class Node{
     int value;
     Node left;
     Node right;

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    public Node(int value){
         this.value=value;
     }
     //查找节点
    public Node search(int value){
        if(this.value==value){
            return this;
        }else {
            if(value<this.value){
                if(this.left!=null){
                    return this.left.search(value);
                }else {
                    return null;
                }
            }else {
                if(this.right!=null){
                    return this.right.search(value);
                }else {
                    return null;
                }
            }
        }
    }
    //查找节点的父节点
    public Node searchFather(int value){
        if(this.left!=null && this.left.value==value ||this.right!=null && this.right.value==value){
            return this;
        }
        if(this.left!=null && value<this.value){
            return this.left.searchFather(value);
        }else if(this.right!=null && value>=this.value){
            return this.right.searchFather(value);
        }else {
            return null;
        }
    }
     //添加节点
    public void add(Node node){
         if(node==null){
             return;
         }
         if(node.value<this.value){
             if(this.left==null){
                 this.left=node;
             }else{
                 this.left.add(node);
             }
         }else {
             if(this.right==null){
                 this.right=node;
             }else {
                 this.right.add(node);
             }
         }
    }
    //中序遍历
    public void midOrder(){
         if(this.left!=null){
             this.left.midOrder();
         }
        System.out.println(this);
         if(this.right!=null){
             this.right.midOrder();
         }
    }
}