二叉排序树

1. 每个节点都保证大于其做节点，小于其右节点
2. 插入:比较然后递归就可实现
3. 遍历：中序遍历是有序的
4. 搜索：同理比较然后递归
5. 删除：
   1. 删除叶子节点
      直接删除
   2. 只有一个节点
      将当前节点的子节点上移即可
   3. 双节点
      找到删除节点的右子树的最小值，也就是右子树一直找左节点即可，然后将这个值赋值个删除节点，删除这个最小值节点即可；

public class OrderTree {

    public static void main(String[] args) {
        OrderTree ot = new OrderTree();
        ot.add(12);
        ot.add(8);
        ot.add(6);
        ot.add(10);
        ot.add(5);
        ot.add(7);
        ot.add(9);
        ot.add(11);
        ot.infixOrder();
        System.out.println("======================");
        ot.del(8);
        ot.infixOrder();
    }

    public Node root;

    public void add(int value) {
        Node curNode = new Node(value);
        if (root == null) {
            root = curNode;
            return;
        }
        root.add(curNode);
    }

    public void preOrder() {
        root.preOrder();
    }

    public void infixOrder() {
        root.infixOrder();
    }

    public Node serach(int value) {
        return root.serach(value);
    }

    public Node serachParent(int value) {
        if (value == root.value) {
            return null;
        }
        return root.seraceParent(value);
    }

    public void del(int value) {
        if (value == root.value) {
            root = null;
            return;
        }
        root.del(value);
    }
}

class Node {

    public int value;
    public Node left;
    public Node right;

    public Node(int value) {
        this.value = value;
    }

    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 preOrder() {
        System.out.println(this.value);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.print(this.value + " ");
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public Node serach(int value) {
        if (this.value == value) {
            return this;
        }
        if (value < this.value) {
            return this.left.serach(value);
        } else {
            return this.right.serach(value);
        }
    }

    public Node seraceParent(int value) {
        if ((this.left != null && this.left.value == value)
                || (this.right != null && this.right.value == value)) {
            return this;
        }
        if (this.left != null && this.left.value > value) {
            return this.left.seraceParent(value);
        } else if (this.right != null && this.right.value > value) {
            return this.right.seraceParent(value);
        } else {
            return null;
        }
    }

    public void del(int value) {

        Node parent = this.seraceParent(value);
        if (parent == null) {
            return;
        }
        Node delNode;
        if (value < parent.value) {
            delNode = parent.left;
            if (delNode.left == null && delNode.right == null) {
                //删除的是叶子节点
                parent.left = null;
            } else if (delNode.left == null || delNode.right == null) {
                //有一个节点
                parent.left = delNode.left == null ? delNode.right : delNode.right;
            } else {
                //俩个节点（规定所有的右节点上移）
                Node minNodeParent = parent.left;
                Node minNode = parent.left.right;
                while (minNode.left != null) {
                    minNodeParent = minNode;
                    minNode = minNode.left;
                }

                if (parent.left.right.left == null) {
                    minNodeParent.right = null;
                } else {
                    minNodeParent.left = null;
                }
                delNode.value = minNode.value;
            }
        } else {
            delNode = parent.right;
            //删除的是叶子节点
            if (delNode.left == null && delNode.right == null) {
                parent.right = null;
            } else if (delNode.left == null || delNode.right == null) {
                parent.right = delNode.left == null ? delNode.right : delNode.right;
            } else {
                //俩个节点（规定所有的右节点上移）
                Node minNodeParent = parent.right;
                Node minNode = parent.right.right;
                while (minNode.left != null) {
                    minNodeParent = minNode;
                    minNode = minNode.left;
                }
                if (parent.left.right.left == null) {
                    minNodeParent.right = null;
                } else {
                    minNodeParent.left = null;
                }
                delNode.value = minNode.value;
            }
        }
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("Node{");
        sb.append("value=").append(value);
        sb.append('}');
        return sb.toString();
    }
}