二叉排序树，也叫搜索树，顾名思义 是一种有顺序的二叉树；

数值的插入

保证插入的数值满足：节点的值大于左子树上的所有节点的值，且小于右子树上所有节点的值

数值的遍历

二叉树中序遍历的结果就是排列好的顺序

数值的删除

删除操作比较难理解，分为多种

以下 用存放int数据为例 实现二叉排序树(水平有限，欢迎拍砖)

/**
 * Created by Zhdf on 2018/12/8.
 * 搜索树，也叫二叉排序树
 * 有以下性质：
 * 如果节点存在左子树..
 * 如果节点存在右子树..
 * 没有重复值（这一点在实际开发中可以忽略）
 */
public class SearchBinaryTree {

    class TreeNode {
        int data;
        TreeNode parent;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
            this.data = data;
        }
    }

    TreeNode root;

    public SearchBinaryTree() {
    }

    public TreeNode put(int data) {
        if (root == null) {
            TreeNode node = new TreeNode(data);
            root = node;
            return root;
        }
        //找到要放入的位置
        TreeNode node = root;
        TreeNode parent = null;
        while (node != null) {
            parent = node;
            if (data < node.data) {
                node = node.leftChild;
            } else if (data > node.data) {
                node = node.rightChild;
            } else {
                //data值已经在当前树里面
                return node;
            }
        }
        //插入节点
        TreeNode newNode = new TreeNode(data);
        if (data < parent.data) {
            newNode.parent = parent;
            parent.leftChild = newNode;
        } else {
            newNode.parent = parent;
            parent.rightChild = newNode;
        }
        return newNode;
    }

    //搜索树树遍历;中序遍历输出结果就是增序
    public void midOrderTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        midOrderTraverse(node.leftChild);
        System.out.print(node.data + " ");
        midOrderTraverse(node.rightChild);
    }

    public TreeNode search(int data) {
        TreeNode node = root;
        if (node == null) {
            return null;
        }
        while (node != null) {
            if (data < node.data) {
                node = node.leftChild;
            } else if (data > node.data) {
                node = node.rightChild;
            } else {
                //找到了
                return node;
            }
        }
        //没有找到，不存在这个值的节点
        return null;
    }

    public void delNode(TreeNode node) {
        if (node == null) {
            throw new RuntimeException("删除的节点不能为空");
        }
        try {
            search(node.data);
        } catch (Exception e) {
            e.printStackTrace();
            throw new RuntimeException("删除的节点不存在");
        }
        TreeNode parent = node.parent;
        //1如果是 叶子节点
        if (node.leftChild == null && node.rightChild == null) {
            if (parent == null) {
                root = null;
            } else {
                if (parent.leftChild != null) {
                    if (parent.leftChild.data == node.data) {
                        parent.leftChild = null;
                        node.parent = null;
                    }
                } else if (parent.rightChild != null) {
                    if (parent.rightChild.data == node.data) {
                        parent.rightChild = null;
                        node.parent = null;
                    }
                }
            }
            return;
        }
        //2如果是 支节点(只有左子树)
        if (node.leftChild != null && node.rightChild == null) {
            if (parent == null) {
                root = node.leftChild;
                node.leftChild.parent = null;
            } else {
                if (parent.leftChild.data == node.data) {
                    parent.leftChild = node.leftChild;
                    node.leftChild.parent = parent;
                } else {
                    parent.rightChild = node.leftChild;
                    node.leftChild.parent = null;
                }
            }
            return;
        }
        //3如果是 支节点(只有右子树)
        else if (node.rightChild != null && node.leftChild == null) {
            if (parent == null) {
                root = node.rightChild;
                node.parent = null;
            } else {
                if (parent.leftChild.data == node.data) {
                    parent.leftChild = node.rightChild;
                    node.rightChild.parent = parent;
                } else {
                    parent.rightChild = node.rightChild;
                    node.rightChild.parent = parent;
                }
            }
            return;
        }
        //4如果是 支节点(左子树右子树都有)
        else if (node.leftChild != null && node.rightChild != null) {
            //node右节点的左节点 不存在
            if (node.rightChild.leftChild == null) {
                if (parent == null) {
                    root = node.rightChild;
                    node.rightChild.parent = null;
                    node.rightChild.leftChild = node.leftChild;
                    node.leftChild.parent = node.rightChild;
                } else {
                    if (parent.leftChild.data == node.data) {
                        parent.leftChild = node.rightChild;
                        node.rightChild.parent = parent;
                        node.rightChild.leftChild = node.leftChild;
                        node.leftChild.parent = node.rightChild;
                    } else {
                        parent.rightChild = node.rightChild;
                        node.rightChild.parent = parent;
                        node.rightChild.leftChild = node.leftChild;
                        node.leftChild.parent = node.rightChild;
                    }
                }
                return;
            }
            //node右节点的左节点 存在
            else {
                TreeNode minNode = findMinNode(node.rightChild.leftChild);
                TreeNode minNodeParent = minNode.parent;
                minNodeParent.leftChild = null;
                if (parent == null) {
                    root = minNode;
                    minNode.leftChild = node.leftChild;
                    minNode.rightChild = node.rightChild;
                    minNode.parent = null;
                    //
                    node.leftChild.parent = minNode;
                    node.rightChild.parent = minNode;
                } else {
                    minNode.leftChild = node.leftChild;
                    minNode.rightChild = node.rightChild;
                    minNode.parent = parent;
                    //
                    node.leftChild.parent = minNode;
                    node.rightChild.parent = minNode;
                }
            }
        }
    }

    private TreeNode findMinNode(TreeNode node) {
        if (node == null) {
            return null;
        }
        TreeNode n = node;
        TreeNode parent = null;
        while (n != null) {
            parent = n.parent;
            n = n.leftChild;
        }
        return parent;
    }
}

测试代码

 public void test() {
        SearchBinaryTree tree = new SearchBinaryTree();
        for (int i = 0; i < arr.length; i++) {
            tree.put(arr[i]);
        }
        tree.midOrderTraverse(tree.root);
        System.out.println();
        SearchBinaryTree.TreeNode node1 = tree.search(2);
        SearchBinaryTree.TreeNode node2 = tree.search(3);
        SearchBinaryTree.TreeNode node3 = tree.search(23);
        SearchBinaryTree.TreeNode node4 = tree.search(26);
        System.out.println("");
        System.out.println("删除2");
        tree.delNode(node1);
        tree.midOrderTraverse(tree.root);
        System.out.println("");
        System.out.println("删除3");
        tree.delNode(node2);
        tree.midOrderTraverse(tree.root);
        System.out.println("");
        System.out.println("删除23");
        tree.delNode(node3);
        tree.midOrderTraverse(tree.root);
        System.out.println("");
        System.out.println("删除26");
        tree.delNode(node4);
        tree.midOrderTraverse(tree.root);
    }