二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），也称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
    （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
    （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
    （3）左、右子树也分别为二叉排序树；

    二叉排序树 - 图1

    1. /**
    2.  * 《二叉排序树》
    3.  *                61
    4.  *               /  \
    5.  *              55  87
    6.  *             /  \
    7.  *            42  58
    8.  */
    9. public class BinarySortTree {
    11.     /**
    12.      * 根结点
    13.      */
    14.     private TreeNode rootNode;
    16.     /**
    17.      * 树结点
    18.      */
    19.     class TreeNode {
    20.         /**
    21.          * 结点值
    22.          */
    23.         private int value;
    24.         /**
    25.          * 左子结点
    26.          */
    27.         private TreeNode left;
    28.         /**
    29.          * 左子结点
    30.          */
    31.         private TreeNode right;
    33.         public TreeNode(int value) {
    34.             this.value = value;
    35.         }
    37.         /**
    38.          * 中序遍历
    39.          */
    40.         public void middleOrder() {
    41.             // 1、中序遍历左子树
    42.             if (this.left != null) {
    43.                 this.left.middleOrder();
    44.             }
    45.             // 2、输出结点
    46.             System.out.printf("%s ", this.value);
    47.             // 3、中序遍历右子树
    48.             if (this.right != null) {
    49.                 this.right.middleOrder();
    50.             }
    51.         }
    53.         /**
    54.          * 插入结点
    55.          */
    56.         public void addNode(TreeNode node) {
    57.             // 插入结点小于当前结点，则往当前结点左子结点进行插入
    58.             if (node.value < this.value) {
    59.                 if (this.left == null) {
    60.                     // 左子结点为空时，则直接插入
    61.                     this.left = node;
    62.                 } else {
    63.                     // 左子结点不为空时，则往左子结点插入
    64.                     this.left.addNode(node);
    65.                 }
    66.             // 否则往当前结点右子结点进行插入
    67.             } else {
    68.                 if (this.right == null) {
    69.                     // 右子结点为空时，则直接插入
    70.                     this.right = node;
    71.                 } else {
    72.                     // 右子结点不为空时，则往右子结点插入
    73.                     this.right.addNode(node);
    74.                 }
    75.             }
    76.         }
    78.         /**
    79.          * 查找结点
    80.          */
    81.         public TreeNode searchNode(TreeNode node) {
    82.             // 查找结点的值等于当前结点
    83.             if (node.value == this.value) {
    84.                 return this;
    85.             } else if (node.value < this.value ) {
    86.                 //查找结点的值小于当前结点，继续从当前结点的左子结点查找
    87.                 if (this.left != null) {
    88.                     return this.left.searchNode(node);
    89.                 }
    90.             } else {
    91.                 //查找结点的值小于当前结点，继续从当前结点的左子结点查找
    92.                 if (this.right != null) {
    93.                     return this.right.searchNode(node);
    94.                 }
    95.             }
    96.             return null;
    97.         }
    99.         /**
    100.          * 查找父结点
    101.          */
    102.         public TreeNode searchParentNode(TreeNode node) {
    103.             // 如果当前结点就是要查找结点的父结点，直接返回
    104.             if ((this.left != null && this.left.value == node.value)
    105.                     || (this.right != null && this.right.value == node.value)) {
    106.                 return this;
    107.             // 如果查找结点小于当前结点的左结点，则往左子结点递归查找
    108.             } else if (this.left != null && node.value < this.left.value) {
    109.                 return this.left.searchParentNode(node);
    110.             // 如果查找结点大于当前结点的右结点，则往右子结点递归查找
    111.             } else if (this.right != null && node.value > this.right.value){
    112.                 return this.right.searchParentNode(node);
    113.             }
    114.             return null;
    115.         }
    116.     }
    118.     /**
    119.      * 中序遍历
    120.      */
    121.     public void middleOrderPrint() {
    122.         if (rootNode == null) {
    123.             return;
    124.         }
    125.         rootNode.middleOrder();
    126.     }
    128.     /**
    129.      * 插入结点
    130.      */
    131.     public void add(int value) {
    132.         TreeNode node = new TreeNode(value);
    133.         // 根结点为空时，则插入结点直接当作根结点
    134.         if (rootNode == null) {
    135.             rootNode = node;
    136.         } else {
    137.             rootNode.addNode(node);
    138.         }
    139.     }
    141.     /**
    142.      * 查找结点
    143.      */
    144.     public boolean search(int value) {
    145.         TreeNode treeNode = searchNode(value);
    146.         return treeNode != null ? true : false;
    147.     }
    149.     /**
    150.      * 查找结点
    151.      */
    152.     private TreeNode searchNode(int value) {
    153.         TreeNode node = new TreeNode(value);
    154.         // 根结点为空时，直接返回
    155.         if (rootNode == null) {
    156.             return null;
    157.         }
    158.         return rootNode.searchNode(node);
    159.     }
    161.     /**
    162.      * 查找父结点
    163.      */
    164.     private TreeNode searchParentNode(int value) {
    165.         TreeNode node = new TreeNode(value);
    166.         // 根结点为空或者要查找的结点就是根结点时，直接返回
    167.         if (rootNode == null || rootNode.value == value) {
    168.             return null;
    169.         }
    170.         return rootNode.searchParentNode(node);
    171.     }
    173.     /**
    174.      * 删除指定结点下最小结点的值
    175.      *     1. 返回的是以node为根节点的二叉排序树的最小节点的值
    176.      *     2. 删除以node为根节点的二叉排序树的最小节点
    177.      */
    178.     private int delTreeMin(TreeNode node) {
    179.         TreeNode target = node;
    180.         // 循环的查找左节点，就会找到最小值
    181.         while (target.left != null) {
    182.             target = target.left;
    183.         }
    184.         // 这时target就指向了最小节点
    185.         // 删除最小节点
    186.         delete(target.value);
    187.         return target.value;
    188.     }
    190.     /**
    191.      * 删除结点
    192.      */
    193.     public void delete(int value) {
    194.         // 根结点为空时，直接返回
    195.         if (rootNode == null) {
    196.             return;
    197.         }
    198.         // 1、需要先去找到要删除的节点targetNode，没有找到直接返回
    199.         TreeNode targetNode = searchNode(value);
    200.         if (targetNode == null) {
    201.             return;
    202.         }
    203.         // 2、如果我们发现当前这颗二叉排序树删除的点就是根结点，且只有一个节点
    204.         if (rootNode.left == null && rootNode.right == null) {
    205.             rootNode = null;
    206.             return;
    207.         }
    208.         // 3、去找到targetNode的父节点
    209.         TreeNode parentNode = searchParentNode(value);
    210.         // (1) 如果要删除的节点是叶子节点
    211.         if (targetNode.left == null && targetNode.right == null) {
    212.             // 判断targetNode是父节点的左子节点还是右子节点
    213.             if (parentNode != null && parentNode.left != null && parentNode.left.value == value) {
    214.                 parentNode.left = null;
    215.             } else if (parentNode != null && parentNode.right != null && parentNode.right.value == value) {
    216.                 parentNode.right = null;
    217.             }
    218.         // (2) 删除有两棵子树的节点
    219.         } else if (targetNode.left != null && targetNode.right != null) {
    220.             // 从targetNode的右子树中，找到最小的节点，先删除这个最小结点，然后把最小结点的值保存到targetNode中
    221.             int minVal = delTreeMin(targetNode.right);
    222.             targetNode.value = minVal;
    223.         // (3) 删除只有一棵子树的节点
    224.         } else {
    225.             // 如果要删除的节点有左子节点
    226.             if (targetNode.left != null) {
    227.                 if (parentNode != null) {
    228.                     // 判断targetNode是父节点的左子节点还是右子节点
    229.                     if (parentNode.left.value == value) {
    230.                         parentNode.left = targetNode.left;
    231.                     } else {
    232.                         parentNode.right = targetNode.left;
    233.                     }
    234.                 } else {
    235.                     // 表示删除的是根结点
    236.                     rootNode = targetNode.left;
    237.                 }
    238.             // 如果要删除的节点有右子节点
    239.             } else {
    240.                 if (parentNode != null) {
    241.                     // 判断targetNode是父节点的左子节点还是右子节点
    242.                     if (parentNode.left.value == value) {
    243.                         parentNode.left = targetNode.right;
    244.                     } else {
    245.                         parentNode.right = targetNode.right;
    246.                     }
    247.                 } else {
    248.                     // 表示删除的是根结点
    249.                     rootNode = targetNode.right;
    250.                 }
    251.             }
    252.         }
    253.     }
    255.     public static void main(String[] args) {
    256.         // 61 87 55 42 58
    257.         BinarySortTree binarySortTree = new BinarySortTree();
    258.         Scanner scanner = new Scanner(System.in);
    259.         boolean loop = true;
    260.         while (loop) {
    261.             System.out.print("【二叉排序树】插入(1)、查找(2)、删除(3)、遍历(4)、退出(0)：");
    262.             Integer key = scanner.nextInt();
    263.             switch (key) {
    264.                 case 1:
    265.                     System.out.print("请输入插入值：");
    266.                     int value = scanner.nextInt();
    267.                     binarySortTree.add(value);
    268.                     break;
    269.                 case 2:
    270.                     System.out.print("请输入查找值：");
    271.                     int value2 = scanner.nextInt();
    272.                     System.out.println("查找结果：" + binarySortTree.search(value2));
    273.                     break;
    274.                 case 3:
    275.                     System.out.print("请输入删除值：");
    276.                     int value3 = scanner.nextInt();
    277.                     binarySortTree.delete(value3);
    278.                     break;
    279.                 case 4:
    280.                     binarySortTree.middleOrderPrint();
    281.                     System.out.println();
    282.                     break;
    283.                 case 0:
    284.                     scanner.close();
    285.                     loop = false;
    286.                     break;
    287.                 default: break;
    288.             }
    289.         }
    290.         System.out.println("程序退出。。。");
    291.     }
    293. }