一、先看一个需求

给你一个数列 (7, 3, 10, 12, 5, 1, 9)，要求能够高效的完成对数据的查询和添加

二、解决方案分析

  1. 使用数组
    数组未排序， 优点：直接在数组尾添加，速度快。 缺点：查找速度慢
    数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位 置后，后面的数据需整体移动，速度慢。
  2. 使用链式存储-链表
    不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。
  3. 使用二叉排序树

三、二叉排序树介绍

二叉排序树： BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当 前节点的值小，右子节点的值比当前节点的值大。

特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点

比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9)

对应的二叉排序树为：

树结构实际应用-二叉排序树 - 图1

四、二叉排序树创建和遍历

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9)

创建成对应的二叉排序树为：

树结构实际应用-二叉排序树 - 图2

五、二叉排序树的删除

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑

  1. 删除叶子节点 (比如：2, 5, 9, 12)
  2. 删除只有一颗子树的节点 (比如：1)
  3. 删除有两颗子树的节点. (比如：7, 3，10 )

思路分析：

  1. //对删除结点的各种情况的思路分析:
  2. 第一种情况:删除叶子节点 (比如：2, 5, 9, 12)
  3.     思路
  4.     (1) 需求先去找到要删除的结点 targetNode
  5.     (2) 找到 targetNode 的 父结点 parent
  6.     (3) 确定 targetNode 是 parent 的左子结点 还是右子结点
  7.     (4) 根据前面的情况来对应删除
  8.     左子结点 parent.left = null
  9.     右子结点 parent.right = null;
  11. 第二种情况: 删除只有一颗子树的节点 比如 1
  12.     思路
  13.     (1) 需求先去找到要删除的结点 targetNode
  14.     (2) 找到 targetNode 的 父结点 parent
  15.     (3) 确定 targetNode 的子结点是左子结点还是右子结点
  16.     (4) targetNode 是 parent 的左子结点还是右子结点
  17.     (5) 如果 targetNode 有左子结点
  18.         5. 1 如果 targetNode 是 parent 的左子结
  19.             parent.left = targetNode.left;
  20.         5.2 如果 targetNode 是 parent 的右子结点
  21.             parent.right = targetNode.left;
  22.     (6) 如果 targetNode 有右子结点
  23.         6.1 如果 targetNode 是 parent 的左子结点
  24.             parent.left = targetNode.right;
  25.         6.2 如果 targetNode 是 parent 的右子结点
  26.             parent.right = targetNode.right
  28. 情况三 ： 删除有两颗子树的节点. (比如：7, 3，10 )
  29.     思路
  30.     (1) 需求先去找到要删除的结点 targetNode
  31.     (2) 找到 targetNode 的 父结点 parent
  32.     (3) 从 targetNode 的右子树找到最小的结点
  33.     (4) 用一个临时变量，将 最小结点的值保存 temp = 11
  34.     (5) 删除该最小结点
  35.     (6) targetNode.value = temp

六、代码实现:

  1. public class BinarySortTreeDemo {
  3.     public static void main(String[] args) {
  5.         int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
  6.         BinarySortTree binarySortTree = new BinarySortTree();
  8.         //循环的添加结点到二叉排序树
  9.         for(int i = 0; i< arr.length; i++) {
  10.             binarySortTree.add(new Node(arr[i]));
  11.         }
  13.         //中序遍历二叉排序树
  14.         System.out.println("中序遍历二叉排序树~");
  15.         binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
  17.         //测试一下删除叶子结点
  18.         //binarySortTree.delNode(12);
  19.         //binarySortTree.delNode(5);
  20.         //binarySortTree.delNode(10);
  21.         //binarySortTree.delNode(2);
  22.         //binarySortTree.delNode(3);
  23.         //binarySortTree.delNode(9);
  24.         //binarySortTree.delNode(1);
  25.         binarySortTree.delNode(7);
  27.         System.out.println("root=" + binarySortTree.getRoot());
  28.         System.out.println("删除结点后");
  29.         binarySortTree.infixOrder();
  30.     }
  31. }
  33. //创建二叉排序树
  34. class BinarySortTree {
  35.     private Node root;
  36.     public Node getRoot() {
  37.         return root;
  38.     }
  40.     //查找要删除的结点
  41.     public Node search(int value){
  42.         if(root == null) {
  43.             return null;
  44.         } else {
  45.             return root.search(value);
  46.         }
  47.     }
  49.     //查找父结点
  50.     public Node searchParent(int value) {
  51.         if(root == null) {
  52.             return null;
  53.         } else {
  54.             return root.searchParent(value);
  55.         }
  56.     }
  58.     //编写方法:
  59.     //1. 返回的 以 node 为根结点的二叉排序树的最小结点的值
  60.     //2. 删除 node 为根结点的二叉排序树的最小结点
  61.     /**
  62.     *
  63.     * @param node 传入的结点(当做二叉排序树的根结点)
  64.     * @return 返回的 以 node 为根结点的二叉排序树的最小结点的值
  65.     */
  66.     public int delRightTreeMin(Node node) {
  67.         Node target=node;
  68.         //循环的查找左子节点，就会找到最小值
  69.         while(target.left != null) {
  70.             target = target.left;
  71.         }
  72.         //这时 target 就指向了最小结点
  73.         //删除最小结点
  74.         delNode(target.value);
  75.         return target.value;
  76.     }
  78.     //删除结点
  79.     public void delNode(int value) {
  80.         if(root == null) {
  81.             return;
  82.         }else {
  83.             //1.需求先去找到要删除的结点 targetNode
  84.             Node targetNode = search(value);
  85.             //如果没有找到要删除的结点
  86.             if(targetNode == null) {
  87.                 return;
  88.             }
  89.             //如果我们发现当前这颗二叉排序树只有一个结点
  90.             if(root.left == null && root.right == null) {
  91.                 root = null;
  92.                 return;
  93.             }
  94.             //去找到 targetNode 的父结点
  95.             Node parent = searchParent(value);
  96.             //如果要删除的结点是叶子结点
  97.             if(targetNode.left == null && targetNode.right == null) {
  98.                 //判断 targetNode 是父结点的左子结点，还是右子结点
  99.                 if(parent.left != null && parent.left.value == value) { //是左子结点
  100.                     parent.left = null;
  101.                 } else if (parent.right != null && parent.right.value == value) {//是由子结点
  102.                     parent.right = null;
  103.                 }
  104.             } else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点
  105.                 int minVal = delRightTreeMin(targetNode.right);
  106.                 targetNode.value = minVal;
  107.             } else { // 删除只有一颗子树的结点
  108.                 //如果要删除的结点有左子结点
  109.                 if(targetNode.left != null) {
  110.                     if(parent != null) {
  111.                         //如果 targetNode 是 parent 的左子结点
  112.                         if(parent.left.value == value) {
  113.                             parent.left = targetNode.left;
  114.                         } else { // targetNode 是 parent 的右子结点
  115.                             parent.right = targetNode.left;
  116.                         }
  117.                     } else {
  118.                         root = targetNode.left;
  119.                     }
  120.                 } else { //如果要删除的结点有右子结点
  121.                     if(parent != null) {
  122.                         //如果 targetNode 是 parent 的左子结点
  123.                         if(parent.left.value == value) {
  124.                             parent.left = targetNode.right;
  125.                         } else { //如果 targetNode 是 parent 的右子结点
  126.                             parent.right = targetNode.right;
  127.                         }
  128.                     } else {
  129.                         root = targetNode.right;
  130.                     }
  131.                 }
  132.             }
  133.         }
  134.     }
  136.     //添加结点的方法
  137.     public void add(Node node) {
  138.         if(root == null) {
  139.             root = node;//如果 root 为空则直接让 root 指向 node
  140.         } else {
  141.             root.add(node);
  142.         }
  143.     }
  145.     //中序遍历
  146.     public void infixOrder() {
  147.         if(root != null) {
  148.             root.infixOrder();
  149.         } else {
  150.             System.out.println("二叉排序树为空，不能遍历");
  151.         }
  152.     }
  153. }
  155. //创建 Node 结点
  156. class Node {
  157.     int value;
  158.     Node left;
  159.     Node right;
  160.     public Node(int value) {
  161.         this.value = value;
  162.     }
  164.     //查找要删除的结点
  165.     /**
  166.     *
  167.     * @param value 希望删除的结点的值
  168.     * @return 如果找到返回该结点，否则返回 null
  169.     */
  170.     public Node search(int value) {
  171.         if(value == this.value) { //找到就是该结点
  172.             return this;
  173.         } else if(value < this.value) {//如果查找的值小于当前结点，向左子树递归查找
  174.             //如果左子结点为空
  175.             if(this.left == null) {
  176.                 return null;
  177.             }
  178.             return this.left.search(value);
  179.         } else { //如果查找的值不小于当前结点，向右子树递归查找
  180.             if(this.right == null) {
  181.                 return null;
  182.             }
  183.             return this.right.search(value);
  184.         }
  185.     }
  187.     //查找要删除结点的父结点
  188.     /**
  189.     *
  190.     * @param value 要找到的结点的值
  191.     * @return 返回的是要删除的结点的父结点，如果没有就返回 null
  192.     */
  193.     public Node searchParent(int value) {
  194.         //如果当前结点就是要删除的结点的父结点，就返回
  195.         if((this.left != null && this.left.value == value) ||
  196.            (this.right != null && this.right.value == value)) {
  197.             return this;
  198.         } else {
  199.             //如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
  200.             if(value < this.value && this.left != null) {
  201.                 return this.left.searchParent(value); //向左子树递归查找
  202.             } else if (value >= this.value && this.right != null) {
  203.                 return this.right.searchParent(value); //向右子树递归查找
  204.             } else {
  205.                 return null; // 没有找到父结点
  206.             }
  207.         }
  208.     }
  210.     @Override
  211.     public String toString() {
  212.         return "Node [value=" + value + "]";
  213.     }
  215.     //添加结点的方法
  216.     //递归的形式添加结点，注意需要满足二叉排序树的要求
  217.     public void add(Node node) {
  218.         if(node == null) {
  219.             return;
  220.         }
  221.         //判断传入的结点的值，和当前子树的根结点的值关系
  222.         if(node.value < this.value) {
  223.             //如果当前结点左子结点为 null
  224.             if(this.left == null) {
  225.                 this.left = node;
  226.             } else {
  227.                 //递归的向左子树添加
  228.                 this.left.add(node);
  229.             }
  230.         } else { //添加的结点的值大于 当前结点的值
  231.             if(this.right == null) {
  232.                 this.right = node;
  233.             } else {
  234.                 //递归的向右子树添加
  235.                 this.right.add(node);
  236.             }
  237.         }
  238.     }
  240.     //中序遍历
  241.     public void infixOrder() {
  242.         if(this.left != null) {
  243.             this.left.infixOrder();
  244.         }
  245.         System.out.println(this);
  246.         if(this.right != null) {
  247.             this.right.infixOrder();
  248.         }
  249.     }
  250. }

七：提升

如果我们从左子树找到最大的结点，然后前面的思路完成

  1.     /**
  2.      * 以传进来的左节点为根节点，向右边节点遍历找到最大值
  3.      *
  4.      * @param leftNode
  5.      * @return
  6.      */
  7.     public int deleteLeftTreeNode(Node leftNode) {
  9.         // 向右遍历找到最大值
  10.         Node targe = leftNode;
  11.         if (targe.getRight() != null) {
  12.             targe = targe.getRight();
  13.         }
  15.         // 删除最大值的节点
  16.         delete(targe.getValue());
  17.         return targe.getValue();
  18.     }