一、概述

二叉搜索数又叫二叉排序树相比于普通的二叉树，其左节点都小于父节点，右节点都大于父节点。具有快速插入删除查找的特点。类似如下

二叉树.jpg

二、添加操作

二叉树的添加节点的操作思想为根据根节点向下查找，递归的遍历下去，直到找到要插入节点合适的位置。

    /**
     * 添加操作
     *
     * @param node
     * @param date
     */
    public void add(Node<T> node, T date) {
        if (node == null) {
            System.out.println("需要初始化头节点");
            return;
        }
        //根节点值和当前元素比较，如果小于date,则将date放入右边元素
        if (node.date.compareTo(date) < 0) {
            if (node.right != null) {
                add(node.right, date);
            } else {
                node.right = new Node<>(date);
            }
        } else {
            if (node.left != null) {
                add(node.left, date);
            } else {
                node.left = new Node<>(date);
            }
        }
    }

三、查找操作

查找操作类似插入，通过递归进行查找

    /**
     * BST查找操作
     * @param root
     * @param date
     * @return
     */
    public Node find(Node root, T date) {
        Node node = root;
        if (root == null) {
            System.out.println("需要初始化");
        }
        while (node != null) {
            if (node.date.compareTo(date) != 0) {
                if (node.date.compareTo(date) > 0) {
                    node = node.left;
                } else {
                    node = node.right;
                }
            } else {
                return node;
            }
        }
        return null;
    }

四、删除操作

删除操作麻烦点，分别分为三种情况：
要删除的节点有左右孩子，这时候需要找到右子树的最小值与删除的值进行替换，然后删除就变成了删除右子树的最小值的操作，转化为情况2、3.
要删除的节点只有一个孩子，找到要删除节点的父节点，将要删除节点的父节点指向删除节点的孩子节点.
要删除的节点是叶子节点，直接将要删除节点的父节点指向null.

    /**
     * 三种情况
     * 1、要删除的节点有左右子节点 找到右子树的最小值交换，这时候删除转换为删除右子树最小值节点
     * 2、要删除的节点是叶子节点、直接删除将父节点指向null
     * 3、要删除的节点有左孩子或者右孩子  需要更新父节点，指向删除节点的子节点
     *
     * @param node
     * @param date
     */
    public void delete(Node<T> node, T date) {
        //要删除节点的父节点
        Node deleteNodeParent = null;
        Node deleteNode = node;
        while (deleteNode != null && deleteNode.date.compareTo(date) != 0) {
            deleteNodeParent = deleteNode;
            if (deleteNode.date.compareTo(date) > 0) {
                deleteNode = deleteNode.left;
            } else {
                deleteNode = deleteNode.right;
            }
        }

        if (deleteNode == null) {
            return;
        }

        //开始删除节点，判断节点是否有左右孩子
        if (deleteNode.left != null && deleteNode.right != null) {
            //记录右子树的最小节点
            Node leftMinNode = deleteNode.right;
            //记录需要移动节点的父节点
            Node leftMinNodeParent = deleteNode;

            while (leftMinNode.left != null) {
                leftMinNodeParent = leftMinNode;
                leftMinNode = leftMinNode.left;
            }
            //交换数据
            deleteNode.date = leftMinNode.date;
            //交换后要删除的节点就变成了leftMinNode
            deleteNode = leftMinNode;
            deleteNodeParent = leftMinNodeParent;
        }

        //这时候删除的节点是叶子节点或者只有一个子节点,转换为情况2、3
        //找到孩子节点
        Node child = null;
        if (deleteNode.left != null) {
            child = deleteNode.left;
        } else if (deleteNode.right != null) {
            child = deleteNode.right;
        } else {
            child = null;
        }

        //删除根节点
        if (deleteNodeParent == null) {
            node = child;
        } else if (deleteNodeParent.left == deleteNode) {
            //删除的是左节点
            deleteNodeParent.left = child;
        } else {
            deleteNodeParent.right = child;
        }
    }

五、二叉树的三种遍历方式

_.没啥好说的三种遍历方式

    /**
     * 前序遍历
     * 根左右
     *
     * @param root
     */
    public void preOrderRecursion(Node root) {
        if (root != null) {
            System.out.println(root.date);
            preOrderRecursion(root.left);
            preOrderRecursion(root.right);
        }
    }

    /**
     * 中序遍历
     * 左跟右
     *
     * @param root
     */
    public void inOrderRecursion(Node root) {
        if (root != null) {
            inOrderRecursion(root.left);
            System.out.println(root.date);
            inOrderRecursion(root.right);
        }
    }

    /**
     * 后续遍历
     * 左右跟
     *
     * @param root
     */
    public void afterOrderRecursion(Node root) {
        if (root!=null){
            afterOrderRecursion(root.left);
            afterOrderRecursion(root.right);
            System.out.println(root.date);
        }
    }