二分搜索树

什么是树结构
二分搜索树 - 图1
当你把上面的图倒过来看，就像是一棵树，所以我们把这种结构称为是树结构。那为什么要使用树结构，因为树结构在生活中很常见，如文件夹的组织方式，又或者如公司职能的组织方式，这些都是树结构的例子。为什么会使用树结构呢? 原因就是因为高效。

概念

同链表一样，它也是一种动态的数据结构，链表中的节点是指向一个节点，而二叉树是指向两个节点，我们把这两个节点称为左子树和右子树，又或者称为左孩子和右孩子。如下图表示的就是二叉树
二分搜索树 - 图2

  1. class Node {
  2.     E e;
  3.     Node left;
  4.     Node right;
  5. }
  • 根节点
    • 最顶部的那个节点，如上图中28就是根节点
    • 二叉树具有唯一的一个根节点
  • 叶子节点
    • 没有孩子的节点，如上图的最后一行都是叶子节点
  • 二叉树的每个节点最多有两个孩子，最多有一个父亲

那是什么是二分搜索树，首先二分搜索树是二叉树，它满足这样的特点，对于每个节点

  • 大于左子树所有节点的值
  • 小于右子树所有节点的值

二分搜索树 - 图3
可以验算，上面的这棵树满足二分搜索树的性质，所以这棵树是二分搜索树。下面我们来实现二分搜索树中节点有关代码

  1. public class BST<E extends Comparable<E>> {
  2.     private class Node {
  3.         public E e;
  4.         public Node left;
  5.         public Node right;
  7.         public Node(E e) {
  8.             this.e = e;
  9.             left = null;
  10.             right = null;
  11.         }
  13.         @Override
  14.         public String toString() {
  15.             return e.toString();
  16.         }
  17.     }
  19.     //根节点
  20.     private Node root;
  21.     //树中元素的个数
  22.     private int size;
  24.     public BST() {
  25.         root = null;
  26.         size = 0;
  27.     }
  29.     public int size() {
  30.         return size;
  31.     }
  32.     public boolean isEmpty() {
  33.         return size == 0;
  34.     }
  35. }

实现

添加元素

二分搜索树 - 图4
上图想必已经将添加元素的规则说的很详细了，所以这里直接上代码

  1. public void add(E e) {
  2.     if (root == null) {
  3.         root = new Node(e);
  4.         size++;
  5.     } else {
  6.         add(root, e);
  7.     }
  8. }
  9. private void add(Node node, E e) {
  10.     //递归终止条件
  11.     if (e.equals(node.e)) {
  12.         return;
  13.     } else if (e.compareTo(node.e) < 0 && node.left == null) {
  14.         node.left = new Node(e);
  15.         size++;
  16.         return;
  17.     } else if (e.compareTo(node.e) > 0 && node.right == null) {
  18.         node.right = new Node(e);
  19.         size++;
  20.         return;
  21.     }
  22.     if (e.compareTo(node.e) < 0) {
  23.         add(node.left, e);
  24.     }
  25.     if (e.compareTo(node.e) > 0) {
  26.         add(node.right, e);
  27.     }
  28. }

其实上面的代码还可以改进，因为我们在add(E e)中对root为根节点进行了单独的考虑，其实可以不再这里考虑，因为通过上面的规则知道，当一个节点为null时，不管它是根节点还是左右孩子，新加入的节点都将取代这个null节点
二分搜索树 - 图5
所以我们优化上面的代码如下

  1. public void add(E e) {
  2.     root = add(root, e);
  3. }
  4. private Node add(Node node, E e) {
  5.     //这里返回的Node所指的语义是node所代表的根节点
  6.     if (node == null) {
  7.         size++;
  8.         return new Node(e);
  9.     }
  10.     if (e.compareTo(node.e) < 0) {
  11.         //如果比根节点小，对左子树进行更新
  12.         node.left = add(node.left, e);
  13.     } else if (e.compareTo(node.e) > 0) {
  14.         //如果比根节点大，对右子树进行更新
  15.         node.right = add(node.right,e);
  16.     }
  17.     //等于的话什么都不做
  18.     return node;
  19. }

查询操作

  1. public boolean contains(E e) {
  2.     return contains(root, e);
  3. }
  4. private boolean contains(Node node, E e) {
  5.     if (node == null) {
  6.         return false;
  7.     }
  9.     if (e.equals(node.e)) {
  10.         return true;
  11.     } else if (e.compareTo(node.e) < 0) {
  12.         return contains(node.left, e);
  13.     } else {
  14.         return contains(node.right,e);
  15.     }
  16. }

二叉树的遍历

对于某个数据结构的遍历就是将该数据结构中所有的元素都访问一遍，分为三类

  • 前序遍历
    • 父节点在访问左子树之前访问
  • 中序遍历
    • 父节点在访问左子树之后，在访问右子树之前访问
  • 后序遍历
    • 父节点在访问右子树之后访问

二分搜索树 - 图6

前序遍历
  1. public void preOrder() {
  2.     preOrder(root);
  3. }
  4. private void preOrder(Node node) {
  5.     if (node == null) {
  6.         return;
  7.     }
  8.     //先访问父节点
  9.     System.out.println(node);
  10.     preOrder(node.left);
  11.     preOrder(node.right);
  12. }

中序遍历
  1. public void inOrder() {
  2.     inOrder(root);
  3. }
  4. private void inOrder(Node node) {
  5.     if (node == null) {
  6.         return;
  7.     }
  9.     inOrder(node.left);
  10.     System.out.println(node);
  11.     inOrder(node.right);
  12. }

中序遍历的结果是元素从小到大排序。

后序遍历
  1. public void postOrder() {
  2.     postOrder(root);
  3. }
  4. private void postOrder(Node node) {
  5.     if (node == null) {
  6.         return;
  7.     }
  9.     postOrder(node.left);
  10.     postOrder(node.right);
  11.     System.out.println(node);
  12. }

后序遍历的一个应用是内存释放，我们必须先把左右孩子的内存释放完才能释放该节点的内存。

前序遍历的非递归实现

二分搜索树 - 图7
代码实现

  1. public void preOrderNR() {
  2.     //非递归写法
  3.     if (root == null) {
  4.         return;
  5.     }
  6.     //这里的Stack是上面自己写的Stack
  7.     Stack<Node> stack = new ArrayStack<>();
  8.     stack.push(root);
  10.     while (!stack.isEmpty()) {
  11.         Node top = stack.pop();
  12.         System.out.println(top);
  13.         if (top.right != null) {
  14.             stack.push(top.right);
  15.         }
  16.         if (top.left != null) {
  17.             stack.push(top.left);
  18.         }
  19.     }
  20. }

层序遍历

二分搜索树 - 图8
代码实现

  1. public void levelOrder() {
  2.     if (root == null) {
  3.         return;
  4.     }
  5.     Queue<Node> queue = new LoopQueue<>();
  6.     queue.enqueue(root);
  7.     while (!queue.isEmpty()) {
  8.         Node front = queue.dequeue();
  9.         System.out.println(front);
  10.         if (front.left != null) {
  11.             queue.enqueue(front.left);
  12.         }
  13.         if (front.right != null) {
  14.             queue.enqueue(front.right);
  15.         }
  16.     }
  17. }

删除元素

在二分搜索树中删除一个节点是比较复杂的，我们首先从最简单的情况开始，删除二分搜索树中的最小值和最大值，首先是如何找到最大值和最小值
二分搜索树 - 图9

  1. public E minimum() {
  2.     if (size == 0) {
  3.         throw new IllegalArgumentException("树为空");
  4.     }
  5.     return minimum(root).e;
  6. }
  7. private Node minimum(Node node) {
  8.     if (node.left == null) {
  9.         return node;
  10.     }
  11.     return minimum(node.left);
  12. }
  13. public E maximum() {
  14.     if (size == 0) {
  15.         throw new IllegalArgumentException("树为空");
  16.     }
  17.     return maximum(root).e;
  18. }
  19. private Node maximum(Node node) {
  20.     if (node.right == null) {
  21.         return node;
  22.     }
  23.     return maximum(node.right);
  24. }

找到了之后如何删除呢
二分搜索树 - 图10

  1. public E removeMin() {
  2.     E ret = minimum();
  3.     root = removeMin(root);
  4.     return ret;
  5. }
  6. private Node removeMin(Node node) {
  7.     if (node.left == null) {
  8.         Node rightNode = node.right;
  9.         node.right = null;
  10.         size--;
  11.         return rightNode;
  12.     }
  13.     node.left = removeMin(node.left);
  14.     return node;
  15. }
  1. public E removeMax() {
  2.     E ret = maximum();
  3.     root = removeMax(root);
  4.     return ret;
  5. }
  6. private Node removeMax(Node node) {
  7.     if (node.right == null) {
  8.         Node leftNode = node.left;
  9.         node.left = null;
  10.         size--;
  11.         return leftNode;
  12.     }
  14.     node.right = removeMax(node.right);
  15.     return node;
  16. }

现在讲解如何删除二分搜搜数中的任意一个节点
二分搜索树 - 图11

  1. public void remove(E e) {
  2.     root = remove(root, e);
  3. }
  4. private Node remove(Node node, E e) {
  5.     if (node == null) {
  6.         return null;
  7.     }
  8.     if (e.equals(node.e)) {
  9.         if (node.right == null) {
  10.             Node leftNode = node.left;
  11.             node.left = null;
  12.             size--;
  13.             return leftNode;
  14.         } else if (node.left == null) {
  15.             Node rightNode = node.right;
  16.             node.right = null;
  17.             size--;
  18.             return rightNode;
  19.         } else {
  20.             Node successor = minimum(node.right);
  21.             successor.right = removeMin(node.right);//为什么这条语句必须在前面???
  22.             successor.left = node.left;
  23.             node.left = node.right = null;
  24.             //size--; 在removeMin中已经维护size了
  25.             return successor;
  26.         }
  27.     } else if (e.compareTo(node.e) < 0) {
  28.         node.left = remove(node.left, e);
  29.     } else {
  30.         node.right = remove(node.right, e);
  31.     }
  32.     return node;
  33. }

上面说的是取右子树中的最小值，你也可以考虑取左子树中的最大值，道理都是一样的。

完整代码

  1. public class BST<E extends Comparable<E>> {
  2.     private class Node {
  3.         public E e;
  4.         public Node left;
  5.         public Node right;
  7.         public Node(E e) {
  8.             this.e = e;
  9.             left = null;
  10.             right = null;
  11.         }
  13.         @Override
  14.         public String toString() {
  15.             return e.toString();
  16.         }
  17.     }
  19.     //根节点
  20.     private Node root;
  21.     //树中元素的个数
  22.     private int size;
  24.     public BST() {
  25.         root = null;
  26.         size = 0;
  27.     }
  29.     public int size() {
  30.         return size;
  31.     }
  32.     public boolean isEmpty() {
  33.         return size == 0;
  34.     }
  36.     public void add(E e) {
  37.         root = add(root, e);
  38.     }
  41.     private Node add(Node node, E e) {
  42.         //这里返回语义指的的是node所代表的根节点
  43.         if (node == null) {
  44.             size++;
  45.             return new Node(e);
  46.         }
  48.         if (e.compareTo(node.e) < 0) {
  49.             //如果比根节点小，对左子树进行更新
  50.             node.left = add(node.left, e);
  51.         } else if (e.compareTo(node.e) > 0) {
  52.             //如果比根节点大，对右子树进行更新
  53.             node.right = add(node.right,e);
  54.         }
  55.         //等于的话什么都不做
  56.         return node;
  57.     }
  59.     public boolean contains(E e) {
  60.         return contains(root, e);
  61.     }
  63.     private boolean contains(Node node, E e) {
  64.         if (node == null) {
  65.             return false;
  66.         }
  68.         if (e.equals(node.e)) {
  69.             return true;
  70.         } else if (e.compareTo(node.e) < 0) {
  71.             return contains(node.left, e);
  72.         } else {
  73.             return contains(node.right,e);
  74.         }
  75.     }
  77.     //前序遍历
  78.     public void preOrder() {
  79.         preOrder(root);
  80.     }
  81.     private void preOrder(Node node) {
  82.         if (node == null) {
  83.             return;
  84.         }
  86.         System.out.println(node);
  87.         preOrder(node.left);
  88.         preOrder(node.right);
  89.     }
  91.     public void preOrderNR() {
  92.         //非递归写法
  93.         if (root == null) {
  94.             return;
  95.         }
  96.         Stack<Node> stack = new ArrayStack<>();
  97.         stack.push(root);
  99.         while (!stack.isEmpty()) {
  100.             Node top = stack.pop();
  101.             System.out.println(top);
  102.             if (top.right != null) {
  103.                 stack.push(top.right);
  104.             }
  105.             if (top.left != null) {
  106.                 stack.push(top.left);
  107.             }
  108.         }
  109.     }
  111.     //中序遍历
  112.     public void inOrder() {
  113.         inOrder(root);
  114.     }
  115.     private void inOrder(Node node) {
  116.         if (node == null) {
  117.             return;
  118.         }
  120.         inOrder(node.left);
  121.         System.out.println(node);
  122.         inOrder(node.right);
  123.     }
  125.     //后序遍历
  126.     public void postOrder() {
  127.         postOrder(root);
  128.     }
  129.     private void postOrder(Node node) {
  130.         if (node == null) {
  131.             return;
  132.         }
  134.         postOrder(node.left);
  135.         postOrder(node.right);
  136.         System.out.println(node);
  137.     }
  139.     public void levelOrder() {
  140.         if (root == null) {
  141.             return;
  142.         }
  143.         Queue<Node> queue = new LoopQueue<>();
  144.         queue.enqueue(root);
  146.         while (!queue.isEmpty()) {
  147.             Node front = queue.dequeue();
  148.             System.out.println(front);
  149.             if (front.left != null) {
  150.                 queue.enqueue(front.left);
  151.             }
  152.             if (front.right != null) {
  153.                 queue.enqueue(front.right);
  154.             }
  155.         }
  156.     }
  158.     public E minimum() {
  159.         if (size == 0) {
  160.             throw new IllegalArgumentException("树为空");
  161.         }
  162.         return minimum(root).e;
  163.     }
  165.     private Node minimum(Node node) {
  166.         if (node.left == null) {
  167.             return node;
  168.         }
  169.         return minimum(node.left);
  170.     }
  172.     public E maximum() {
  173.         if (size == 0) {
  174.             throw new IllegalArgumentException("树为空");
  175.         }
  176.         return maximum(root).e;
  177.     }
  179.     private Node maximum(Node node) {
  180.         if (node.right == null) {
  181.             return node;
  182.         }
  183.         return maximum(node.right);
  184.     }
  186.     public E removeMin() {
  187.         E ret = minimum();
  188.         root = removeMin(root);
  189.         return ret;
  190.     }
  192.     private Node removeMin(Node node) {
  193.         if (node.left == null) {
  194.             Node rightNode = node.right;
  195.             node.right = null;
  196.             size--;
  197.             return rightNode;
  198.         }
  200.         node.left = removeMin(node.left);
  201.         return node;
  202.     }
  204.     public E removeMax() {
  205.         E ret = maximum();
  206.         root = removeMax(root);
  207.         return ret;
  208.     }
  209.     private Node removeMax(Node node) {
  210.         if (node.right == null) {
  211.             Node leftNode = node.left;
  212.             node.left = null;
  213.             size--;
  214.             return leftNode;
  215.         }
  217.         node.right = removeMax(node.right);
  218.         return node;
  219.     }
  221.     public void remove(E e) {
  222.         root = remove(root, e);
  223.     }
  224.     private Node remove(Node node, E e) {
  225.         if (node == null) {
  226.             return null;
  227.         }
  228.         if (e.equals(node.e)) {
  229.             if (node.right == null) {
  230.                 Node leftNode = node.left;
  231.                 node.left = null;
  232.                 size--;
  233.                 return leftNode;
  234.             } else if (node.left == null) {
  235.                 Node rightNode = node.right;
  236.                 node.right = null;
  237.                 size--;
  238.                 return rightNode;
  239.             } else {
  240.                 Node successor = minimum(node.right);
  241.                 successor.right = removeMin(node.right);//为什么这条语句必须在前面???
  242.                 successor.left = node.left;
  243.                 node.left = node.right = null;
  244.                 //size--; 在removeMin中已经维护size了
  245.                 return successor;
  246.             }
  247.         } else if (e.compareTo(node.e) < 0) {
  248.             node.left = remove(node.left, e);
  249.         } else {
  250.             node.right = remove(node.right, e);
  251.         }
  252.         return node;
  253.     }
  254. }