一、二叉查找树（BTS）

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

定义:
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。

查找

步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。

查找复杂

1、定义节点

class Node {
    //节点值
    int val;
    //左子节点引用
    Node leftChild;
    //右子节点引用
    Node  rightChild;
}

2、插入

首先执行查找算法，找出被插结点的父亲结点。
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。

private Node root;

public void insert(int data) {
        Node newNode = new Node();
        newNode.val = data;
        if(root == null) {
            //如果是第一个节点，也就是根节点为null,直接创建一个新的节点即可　
            root = newNode;
        } else {
            Node current = root;
            //current节点的父节点
            Node parent;
            //循环查找插入的位置
            while(true) {
                parent = current;
                //如果插入的值小于当前节点的值，从左子树查找
                if(data < current.val) {
                    current = current.leftChild;
                    //直到当前节点为null
                    if(current == null) {
                        //设置当前节点的父节点的左子节点为新创建的节点
                        parent.leftChild = newNode;
                        return;
                    }
                }
                //如果插入的值大于当前节点的值，从左子树查找
                else if (data > current.val) {
                    current = current.rightChild;
                    //直到当前节点为null
                    if(current == null) {
                        //设置当前节点的父节点的右子节点为新创建的节点
                        parent.rightChild = newNode;
                        return;
                    }
                } else {
                    // 相等
                    return;
                }
            }// end of while(true)
        }
    }

3、查找

public Node find(int value) {
        Node current = root;
        while(current.val != value) {
            if(value < current.val) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
            if(current == null) {
                return null;
            }
        }

        return current;
    }

4、删除

public boolean delete(int value) {

        Node current = root;
        Node parent = root;
        boolean isLeft = false;
        boolean isRight = false;
        //查找所要删除的节点的左子节点还是右子节点
        while(current.val != value) {
            parent = current;
            isLeft = false;
            isRight = false;
            if(value < current.val) {
                current = current.leftChild;
                isLeft = true;
            }
            else {
                current = current.rightChild;
                isRight = true;
            }
        }
        //不存在该值
        if(current == null) {
            return false;
        }
        //是叶子节点，不存在子节点
        if((current.leftChild == null)
                && (current.rightChild == null)) {
            System.out.println("是叶子节点，不存在子节点");
            if(isLeft) {
                //如果是左子节点，设父节点的左子节点为null
                parent.leftChild = null;
            }
            else if(isRight) {
                //如果是右子节点，设父节点的右子节点为null
                parent.rightChild = null;
            }
            return  true;
        }
        //存在左子节点
        else if((current.leftChild != null)
                && (current.rightChild == null)) {
            System.out.println("不是叶子节点，存在左子节点");

            if(isLeft) {
                parent.leftChild = current.leftChild;
            }
            else if(isRight) {
                parent.rightChild = current.leftChild;
            }
            current = null;
            return  true;
        }

        //存在右子节点
        else if((current.leftChild == null)
                && (current.rightChild != null)) {
            System.out.println("不是叶子节点，存在右子节点");
            if(isLeft) {
                parent.leftChild = current.rightChild;

            }
            else if(isRight) {
                parent.rightChild = current.rightChild;
            }
            current = null;
            return  true;
        }
        //左右子节点都存在
        else {
            System.out.println("不是叶子节点，存在左右子节点");

            if(isLeft) {
                parent.leftChild = current.rightChild;

                Node currentLeft = current.rightChild;
                Node parentLeft = currentLeft;
                while(currentLeft != null) {
                    parentLeft = currentLeft;
                    currentLeft = currentLeft.leftChild;
                }
                parentLeft.leftChild = current.leftChild;
                current = null;

            }
            else if(isRight) {
                parent.rightChild = current.rightChild;

                Node currentLeft = current.rightChild;
                Node parentLeft = currentLeft;
                while(currentLeft != null) {
                    parentLeft = currentLeft;
                    currentLeft = currentLeft.leftChild;
                }
                parentLeft.leftChild = current.leftChild;
                current = null;
            }

            return  true;
        }

    }

5、打印

public void printTree(Node head) {
        System.out.println("-----------------\r\nBinary Tree:");
        printInOrder(head, 0, "Root-", 8);
        System.out.println();
    }

    public void printInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.rightChild, height + 1, "R-", len);
        String val = to + head.val;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val;// + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.leftChild, height + 1, "L-", len);
    }

    public String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

存在的问题

二叉搜索树插入时是按照一定规则进行插入的，因此在中序遍历时获得的数据是有序的，比如下面查找35，只需要比较３次就可以获得结果，因此插入或者查找的效率还是比较高的。

但是存在的一个问题是，如果插入的数据是单调变化的，那就变成了线性链表，最后导致查找效率降低。
因此，也就出现了其他更好的二叉树数据结构，比如红黑树，红黑树是一种平衡的二叉树。