前置知识：

[1] 树结构基础概念

什么是二叉搜索树？

是二叉树的一种，任意一个结点的值都大于左子树的所有值，任意一个结点的值都小于右子树所有的值。

二叉搜索树存储的元素类型，必须是可以比较的，并且不能为 null 。

二叉搜索树的接口

既然是用于搜索功能，应该有增删查功能。 另外还可以提供一些便捷的接口。当前树的大小，是否为空等。

  1. //添加一个元素
  2. public void add(E element) ;
  4. //删除一个指定的元素
  5. public void remove(E element);
  7. //查找一个元素
  8. public boolean constains(E element);
  11. //获取当前二叉搜索树大小
  12. public int size();
  14. //清空
  15. public void clear();
  17. //当前二叉树是否为空
  18. public boolean isEmpty();

二叉搜索树接口的实现

类设计

在实现接口之前，首先分析一下二叉搜索树应该有哪些结构、元素。

树是由结点组成的，所以须要有结点这个类。结点里面肯定有一个元素(或者叫做值)来存储内容。结点存储的元素的类型是未知的，所以使用泛型。由于是二叉搜索树，所以结点需要有左右子节点，并且除了根结点以外的结点都有父节点。

创建结点的时候，必须要传结点的内容和父节点才可以创建成功。所以构造函数要求传这两个参数。除了根结点不需传父节点以外。

综合来看，结点类如下：

  1. public class Node<E> {
  3.     /**
  4.      * 元素
  5.      */
  6.     E element;
  8.     /**
  9.      * 左子节点
  10.      */
  11.     Node<E> left;
  13.     /**
  14.      * 右子节点
  15.      */
  16.     Node<E> right;
  18.     /**
  19.      * 父节点
  20.      */
  21.     Node<E> parent;
  23.       /**
  24.      * 创建结点除了根结点没有父节点外，其他结点都有父节点和结点元素对象。左右子节点创建的时候不一定有。
  25.      */ 
  26.       public Node(E element, Node<E> parent) {
  27.          this.element = element;
  28.          this.parent = parent;
  29.     }
  31. }

二叉搜索树类，首先必须有一个大小的属性来记录当前树内有多少个元素。然后必须有一个根结点，不然对这棵树无从下手。结点类是为了二叉搜索树而存在的，其它类不需要用到它，所以可以作为二叉搜索树的内部类。
再加上之前分析的需要的一些方法。综合上述，二叉搜索树类如下：

  1. /**
  2.  * 二叉搜索树
  3.  */
  4. public class BinarySearchTree<E> {
  6.     private int size;
  8.     private E element;
  10.     /**
  11.      * 返回当前大小
  12.      * @return size
  13.      */
  14.     public int size() {
  15.         return size;
  16.     }
  18.     /**
  19.      * 返回当前是否为空
  20.      * @return 是否为空
  21.      */
  22.     public boolean isEmpty() {
  23.         return size == 0 ;
  24.     }
  26.     /**
  27.      * 清空所有元素
  28.      */
  29.     public void clear() {
  30.         root = null;
  31.         size = 0;
  32.     }
  34.     /**
  35.      * 添加一个元素
  36.      * @param element 元素
  37.      */
  38.     public void add(E element) {
  40.     }
  42.     /**
  43.      * 删除一个特定元素
  44.      * @param element 需要删除的元素
  45.      */
  46.     public void remove(E element) {
  48.     }
  50.     /**
  51.      * 判断元素是否存在
  52.      * @param element 需要判断的元素
  53.      * @return 判断结果
  54.      */
  55.     public boolean contains(E element) {
  56.         return false;
  57.     }
  60.     private static class Node<E>{
  62.         E element;
  63.         Node<E> left;
  64.         Node<E> right;
  65.         Node<E> parent;
  67.         public Node(E element, Node<E> parent) {
  68.             this.element = element;
  69.             this.parent = parent;
  70.         }
  72.     }
  74. }

方法实现

那么，主要实现的方法有3个，添加，删除和查找

添加方法

添加一个结点比较简单，首先看是否添加的是根结点，如果是添加的是根结点，则直设置当前结点为根结点，然后就可以结束方法了。 代码如下：

  1.     /**
  2.      * 添加一个元素
  3.      */
  4.     public void add(E element) {
  6.         //如果根结点为空，则先完成根结点的添加
  7.         if (root == null) {
  8.             root = new Node<>(element,null);
  9.             size++;
  10.             return;
  11.         }
  12.     }

非根节点的添加思路：

  1. 找到新增节点的父节点。
    从根节点开始对比，如果比根节点大，则去右子树找，如果比根节点小，则去左子树找。一直找到空的位置。如果新增的节点和父节点相等，不处理，或者替换，建议进行替换。因为新元素和旧元素是不一样的。如果没有处理，则丢失了新增的节点了。
  2. 确定新增节点的位置。
    确定父节点后，也就确定了新增节点的位置，是父节点的左节点还是右节点，还是和父节点一样。 然后新增加一个节点，添加进树里面。 然后设置新增的节点为父节点的左子树或者右子树，或者替换掉父节点。

代码如下：

  1. /**
  2.  * 添加一个元素
  3.  */
  4. public void add(E element) {
  6.     //确保元素是非空的
  7.     elementNotNullCheck(element);
  9.     //如果根结点为空，则先完成根结点的添加
  10.     if (root == null) {
  12.         root = new Node<>(element,null);
  13.         size++;
  14.         return;
  15.     }
  17.     //当前结点从根结点开始
  18.     Node<E> currentNode = root;
  20.     //保存父节点，创建新节点的时候需要用到
  21.     Node<E> parentNode = currentNode;
  23.     //保存比较结果，用于判断新增的是左子节点还是右子节点
  24.     int compareResult = 0;
  26.     while (currentNode != null) {
  28.         parentNode = currentNode;
  30.         compareResult = ((Comparable)currentNode.element).compareTo(element);
  32.         if (compareResult > 0) {
  33.             currentNode = currentNode.left;
  35.         } else if (compareResult < 0) {
  36.             currentNode = currentNode.right;
  38.         } else {
  39.             //两个元素相等的情况下,用新的元素覆盖掉旧的元素
  40.             currentNode.element = element;
  41.             return;
  42.         }
  43.     }
  45.     //将新节点加入树:新节点和树的结点建立引用关系
  46.     Node<E> newNode = new Node<>(element,parentNode);
  48.     if (compareResult > 0 ) {
  49.         parentNode.left = newNode;
  51.     } else if (compareResult < 0) {
  52.         parentNode.right = newNode;
  53.     }
  54.     size++;
  55. } 
  57.  private void elementNotNullCheck(E element) {
  58.         if (element == null) {
  59.             throw new IllegalArgumentException("元素不能为null");
  60.           }
  61.  }

这个时候，一般的添加算法就可以算作是完成了。但是值得优化的地方是，如果需要对添加进树的元素进行自定义的比较的话，当前是满足不了的。 因为在比较两个元素的时候，只是单纯的将元素转换成 comparable 接口来进行比较 ：

  1. compareResult = ((Comparable)currentNode.element).compareTo(element);

虽然如果元素没有实现 comparable 接口的话就会报错，类型转换异常，相当于强制要求元素实现 comparable 接口，但是这样的实现方式也限制了比较的逻辑。
例如 Car 类，默认实现了 compareble 接口，按照价格比较。

  1.  public class Car implements Comparable {
  3.         private int price ;
  5.         private int size;
  7.         @Override
  8.         public int compareTo(Object o) {
  10.             Car carO = (Car)o;
  12.             return carO.price - this.price;
  13.         }
  14.     }

这时候，将 Car 对象放入搜索树的话，只能按照价格来排序。但是这时候希望，Car 对象可以按照尺寸来进行排序。或者说希望有2棵二叉搜索树，都是装 Car 类型的对象，但是1棵是按照 Car 的价格排序，另外1棵按照 Car 类型的尺寸排序。

要实现这样的定制化比较需求的话，可以在二叉搜索树内设计一个比较器对象。然后将比较的逻辑抽取出来形成一个方法。这个比较方法，如果二叉搜索树有比较器的话，就优先使用比较器进行比较，如果没有的话，就使用 comparable 进行比较。

增加构造器和抽取 compareTo 方法:

  1. public class BinarySearchTree<E> {
  3.     //增加比较器属性
  4.     private Comparator<E> comparator;
  6.     //在构造函数里面将构造器传进来
  7.     public BinarySearchTree(Comparator<E> comparator) {
  8.         this.comparator = comparator;
  9.     }
  11.     //提供默认构造函数
  12.     public BinarySearchTree() {
  14.     }
  16.     /**
  17.      * 比较两个元素的大小
  18.      * @param e1 当前元素
  19.      * @param e2 需要比较的元素
  20.      * @return e1 > e2 返回正数， e1=e2 返回0 , e1 < e2 返回负数
  21.      */
  22.     private int compareTo(E e1 , E e2) {
  24.         if (comparator != null) {
  25.             return comparator.compare(e1,e2);
  26.         }
  28.         return ((Comparable)e1).compareTo(e2);
  29.     }
  32. }

完成添加接口后，完整的类如下：

  1. public class BinarySearchTree<E> {
  3.     private Comparator<E> comparator;
  5.     public BinarySearchTree(Comparator<E> comparator) {
  6.         this.comparator = comparator;
  7.     }
  9.     public BinarySearchTree() {
  11.     }
  13.     /**
  14.      * 树的大小
  15.      */
  16.     private int size;
  18.     /**
  19.      * 根结点
  20.      */
  21.     private Node<E> root;
  23.     /**
  24.      * 添加一个元素
  25.      */
  26.     public void add(E element) {
  28.         elementNotNullCheck(element);
  30.         //如果根结点为空，则先完成根结点的添加
  31.         if (root == null) {
  32.             root = new Node<>(element,null);
  33.             size++;
  34.             return;
  35.         }
  37.         //当前结点从根结点开始
  38.         Node<E> currentNode = root;
  40.         //保存父节点，创建新节点的时候需要用到
  41.         Node<E> parentNode = currentNode;
  43.         //保存比较结果，用于判断新增的是左子节点还是右子节点
  44.         int compareResult = 0;
  46.         while (currentNode != null) {
  48.             parentNode = currentNode;
  50.             compareResult = compareTo(currentNode.element,element);
  52.             if (compareResult > 0) {
  53.                 currentNode = currentNode.left;
  55.             } else if (compareResult < 0) {
  56.                 currentNode = currentNode.right;
  58.             } else {
  59.                 //两个元素相等的情况下,用新的元素覆盖掉旧的元素
  60.                 currentNode.element = element;
  61.                 return;
  62.             }
  63.         }
  65.         //将新节点加入树:新节点和树的结点建立引用关系
  66.         Node<E> newNode = new Node<>(element,parentNode);
  68.         if (compareResult > 0 ) {
  69.             parentNode.left = newNode;
  71.         } else if (compareResult < 0) {
  72.             parentNode.right = newNode;
  73.         }
  75.         size++;
  76.     }
  80.     private void elementNotNullCheck(E element) {
  81.         if (element == null) {
  82.             throw new IllegalArgumentException("元素不能为null");
  83.         }
  84.     }
  87.     /**
  88.      * 比较两个元素的大小
  89.      * @param e1 当前元素
  90.      * @param e2 需要比较的元素
  91.      * @return e1 > e2 返回正数， e1=e2 返回0 , e1 < e2 返回负数
  92.      */
  93.     private int compareTo(E e1 , E e2) {
  95.         if (comparator != null) {
  96.             return comparator.compare(e1,e2);
  97.         }
  99.         return ((Comparable)e1).compareTo(e2);
  100.     }
  102.     /**
  103.      * 删除一个指定的元素
  104.      */
  105.     public void remove(E element){
  107.     }
  109.     /**
  110.      * 查找一个元素
  111.      */
  112.     public boolean contains(E element){
  113.         return false;
  114.     }
  117.     /**
  118.      *获取当前二叉搜索树大小
  119.      */
  120.     public int size(){
  121.         return this.size;
  122.     }
  124.     /**
  125.      * 清空
  126.      */
  127.     public void clear(){
  128.         root = null;
  129.         size = 0;
  130.     }
  132.     /**
  133.      * 当前二叉树是否为空
  134.      */
  135.     public boolean isEmpty(){
  136.         return sizs == 0;
  137.     }
  141.     private static class Node<E>{
  143.         E element;
  144.         Node<E> left;
  145.         Node<E> right;
  146.         Node<E> parent;
  148.         public Node(E element, Node<E> parent) {
  149.             this.element = element;
  150.             this.parent = parent;
  151.         }
  152.     }
  153. }

遍历方法

进行查找编写查找方法之前，首先进行遍历方法的编写。因为查找的时候会用到。对二叉搜索树的遍历，一般有4种方式，前序遍历，中序遍历，后序遍历，层级遍历。

前序遍历：先访问根结点，再访问子结点。 根结点 -> 左子结点 -> 右子结点 或者 根结点 -> 右子节点 -> 左子节点 都可以，一般默认先左再右。根结点在最先访问。

中序遍历：先访问左子结点，再访问根结点，再访问右子节点。 左子结点 -> 根结点 -> 右子结点 或者 右子结点 -> 根节点 -> 左子节点 都可以，一般默认先左再右。 根结点放在中间访问。

后序遍历：先访问左子结点，再访问右子结点，再访问根节点。 左子结点 -> 右子结点 -> 根结点 或者 右子结点 -> 左子节点 -> 根节点 都可以，一般默认先左再右。 根结点放在最后访问。

层序遍历：按照二叉树，一层一层的遍历。

image.png
例如上面的二叉树，
前序遍历结果是：7 4 2 1 3 5 9 8 11 10 12
中序遍历结果是：1 5 3 4 5 7 8 9 10 11 12
后续遍历结果是：1 3 2 5 4 8 10 12 11 9 7
层序遍历的结果是：7 4 9 2 5 8 11 1 3 10 12

使用递归的方式进行遍历的话，遍历的实现比较简单，调用的时候使用传入根结点即可：

  1. /**
  2.  * 递归的方式进行前序遍历
  3.  */
  4. public void preOrderByRecursive(Node node) {
  6.     if (node == null) {
  7.         return;
  8.     }
  10.     System.out.print(node.element + " ");
  11.     preOrderByRecursive(node.left);
  12.     preOrderByRecursive(node.right);
  13. }
  15. /**
  16.  * 递归的方式进行中序遍历
  17.  */
  18. public void inOrderByRecursive(Node node) {
  19.     if (node == null) {
  20.         return;
  21.     }
  23.     inOrderByRecursive(node.left);
  24.     System.out.print(node.element + " ");
  25.     inOrderByRecursive(node.right);
  26. }
  28. /**
  29.  * 递归的方式进行后序遍历
  30.  */
  31. public void afterOrderByRecursive(Node node) {
  32.     if (node == null) {
  33.         return;
  34.     }
  36.     afterOrderByRecursive(node.left);
  37.     afterOrderByRecursive(node.right);
  38.     System.out.print(node.element + " ");
  39. }

层序遍历稍微复杂一些，需要和队列配合使用。首先将根结点放入队列，然后循环遍历出列，在出列的同时，进行结点的访问，并且将结点的左右子节点放入队列。一直循环将所有元素都出列，这样就完成了层序遍历。

  1. /**
  2.  * 循环的方式进行层序遍历
  3.  */
  4. public void levelOrderByLoop(Node node) {
  6.     if (node == null) {
  7.         return;
  8.     }
  10.     //根结点入列
  11.     Queue<Node> queue = new LinkedList();
  12.     queue.offer(node);
  14.     //循环出列，然后访问元素并且将子结点入列
  15.     while (!queue.isEmpty()) {
  17.         Node n = queue.poll();
  18.         System.out.print(n.element + " ");
  20.         if (n.left != null) {
  21.             queue.offer(n.left);
  22.         }
  24.         if (n.right != null) {
  25.             queue.offer(n.right);
  26.         }
  27.     }
  28. }

这样的写法，还是有一个缺点，就是在遍历的时候，对结点的操作是固定的，只能是进行输出元素。如果希望将元素+1 ，或者 -1 这样的操作，就满足不了。所以，可以像增加比较器那样，增加一个访问器，遍历的时候，根据访问器的逻辑，对结点进行访问。由于访问器是在二叉搜索树内部使用的，所以定义一个内部类即可。

  1. public static interface Visitor<E> {
  3.     /**
  4.      * 访问方法
  5.      */
  6.     void visit(E element);
  7. }

然后将遍历的方法稍加修改，加入访问器, 修改后的遍历方法如下：

  2.     /**
  3.      * 使用递归的方式进行前序遍历
  4.      * @param node 前序遍历的结点
  5.      */
  6.     public void preOrderByRecursive(Node<E> node ,Visitor<E> visitor) {
  8.         if (node == null) {
  9.             return;
  10.         }
  12.         if (visitor != null) {
  13.             visitor.visit(node.element);
  14.         }
  16.         preOrderByRecursive(node.left,visitor);
  18.         preOrderByRecursive(node.right,visitor);
  19.     }
  21.     /**
  22.      * 递归的方式进行中序遍历
  23.      */
  24.     public void inOrderByRecursive(Node<E> node,Visitor<E> visitor) {
  25.         if (node == null) {
  26.             return;
  27.         }
  29.         inOrderByRecursive(node.left,visitor);
  30.         if (visitor != null) {
  31.             visitor.visit(node.element);
  32.         }
  33.         inOrderByRecursive(node.right,visitor);
  34.     }
  36.     /**
  37.      * 递归的方式进行后序遍历
  38.      */
  39.     public void afterOrderByRecursive(Node<E> node,Visitor<E> visitor) {
  40.         if (node == null) {
  41.             return;
  42.         }
  44.         afterOrderByRecursive(node.left,visitor);
  45.         afterOrderByRecursive(node.right,visitor);
  46.         if (visitor != null) {
  47.             visitor.visit(node.element);
  48.         }
  49.     }
  52.     /**
  53.      * 循环的方式进行层序遍历
  54.      */
  55.     public void levelOrderByLoop(Node<E> node,Visitor<E> visitor) {
  57.         if (node == null) {
  58.             return;
  59.         }
  61.         //根结点入列
  62.         Queue<Node> queue = new LinkedList();
  63.         queue.offer(node);
  65.         //循环出列，然后访问元素并且将子结点入列
  66.         while (!queue.isEmpty()) {
  68.             Node<E> n = queue.poll();
  70.             if (visitor != null) {
  71.                 visitor.visit(n.element);
  72.             }
  73.             if (n.left != null) {
  74.                 queue.offer(n.left);
  75.             }
  76.             if (n.right != null) {
  77.                 queue.offer(n.right);
  78.             }
  79.         }
  80.     }

高度计算

接下来再来看看二叉树的高度的计算。二叉树的高度=根结点的高度。

根结点的高度=高度更高的子节点的高度+1。只需要递归的不断找到更高的子结点的高度，然后+1，就可以得到根结点的高度了。 使用递归的方式求树的高度实现如下：

  1.     /**
  2.      * 使用递归的方式返回结点的高度
  3.      * @return 结点的高度
  4.      */
  5.     public int heightByRecursive(Node node) {
  6.         if (node == null) {
  7.             return 0;
  8.         }
  9.         return Math.max(heightByRecursive(node.left),heightByRecursive(node.right)) + 1;
  10.     }

使用循环的方式来计算树的高度也比较简单，树的高度其实也就是等于树的层数。那么只需要计算出树有多少层即可。

计算层数，使用层序遍历，是比较简单的方式。只需要在遍历的时候，遍历完一层的时候，高度+1，一直遍历完所有的层，那么树的层数也就知道了。

经过观察发现，每遍历完一层的时候，队列中剩下的元素的数量就等于下一层元素的数量。例如在上图的二叉树中，结点7出列后，队列中就只剩下结点4,9。结点9出列后，队列中只剩剩下结点2,5,8,11。

那么，就可以加一个变量，用来记录当前层还没有遍历的元素：levelSize 。在遍历的过程中 levelSize = 0，那么就代表，这一层已经遍历完了，就可以进行高度的累加了。累加完的同时，也是可以知道下一层的元素的数量的，那么重新将 levelSize 的大小设置为下一层的元素的数量，然后开始遍历下一层。这样遍历完成后，就可以得到树的层数，也就是高度了。 代码实现如下：

  1. /**
  2.  * 使用递归的方式返回树的层数也就是高度
  3.  * @return 树的高度
  4.  */
  5. public int heightByLoop(Node node) {
  6.     if (node == null) {
  7.         return 0;
  8.     }
  10.     //根结点入列
  11.     Queue<Node> queue = new LinkedList();
  12.     queue.offer(node);
  14.     //当前层，还没有遍历的元素个数
  15.     //还没有开始遍历，所以，还没有遍历的层是第1层，还没有遍历的元素是1个。
  16.     int levelSize = 1;
  18.     //初始高度为0；
  19.     int height = 0;
  21.     //循环出列，然后访问元素并且将子结点入列
  22.     while (!queue.isEmpty()) {
  24.         Node n = queue.poll();
  25.         levelSize --;
  27.         if (n.left != null) {
  28.             queue.offer(n.left);
  29.         }
  31.         if (n.right != null) {
  32.             queue.offer(n.right);
  33.         }
  35.         //levelSize == 0 说明已经遍历完这一层的元素
  36.         if (levelSize == 0) {
  37.             //累加高度
  38.             height ++;
  40.             //赋值下一层的未遍历的元素个数
  41.             levelSize = queue.size();
  42.         }
  43.     }
  45.     return height;
  46. }

前驱和后继结点

中序遍历时的前一个结点称为前驱结点，中序遍历时的后一个结点称为后继结点。
image.png
例如上面的二叉树，结点8的前驱是7，后继是9。结点2的前驱是1，后继是3。结点7的前驱是6，后继是8。结点1没有前驱，后继是2。结点10的前驱是9，后继是11。结点12的前驱是11，没有后继

根据观察总结可以分析得出，求一个结点的前驱的时候，可以分为以下2种情况：

  1. 结点有左子树。那么，前驱一定是该结点的左子节点或者是该结点的左子树的最深的右子树。例如结点8有左子树，它的前驱就是左子节点4的右子结点6的右子节点7。结点4的前驱是左子结点2的右子结点3。结点2的前驱是左子节点1。
  2. 结点没有左子树，那么它的前驱一定是比它小的第1个父节点或者祖父结点。如果找不到比它小的父节点或者祖父结点，那么，它就没有前驱。例如：结点3没有左子树，就找它的父结点2，2比3小，所以2就是3的前驱节点。结点11，第1个比它小的祖父结点是10，所以10是前驱。结点1，没有左子树，而且父节点和祖父结点里面没有找到比1小的，找到8以后，就没有父节点了。所以，1没有前驱。

后继结点的情况刚好和前驱相反。
根据观察总结可以分析得出，求一个结点的后继的时候，可以分为以下2种情况：

  1. 结点有右子树。那么，后继一定是它的右子节点或者是它的右子树的最深的左子树。例如结点8有右子树，它的后继就是右子节点13的右子结点10的右子节点9。结点4的后继是右子结点6的左子结点5。结点6的后继是右子节点7。
  2. 结点没有右子树，那么它的后继一定是比它大的第1个父节点或者祖父结点。如果找不到比它大的父节点或者祖父结点，那么，它就没有后继。例如：结点3没有右子树，就找它的父结点2，2比3小，继续找祖父结点4，比3大，所以4就是3的后继点。结点12，第1个比它大的祖父结点是13，所以13是后继。结点13，没有右子树，而且父节点和祖父结点里面没有找到比13大的，找到8以后，就没有父节点了。所以，13没有后继。

根据以上思路，代码实现如下：

  1. /**
  2.  * 求前驱结点
  3.  */
  4. public Node<E> predecessor(Node<E> node) {
  6.     if (node == null) {
  7.         return null;
  8.     }
  10.     //存在左子树的情况
  11.     Node<E> p = node.left;
  12.     if (p != null) {
  13.         while (p.right != null) {
  14.             p = p.right;
  15.         }
  16.         return p;
  17.     }
  19.     //不存在左子树的情况，在父节点或者祖父结点找
  20.     while (node.parent != null && node == node.parent.left) {
  21.         node = node.parent;
  22.     }
  24.     return node.parent;
  26. }
  29. /**
  30.  * 求后继结点
  31.  */
  32. public Node<E> successor(Node<E> node) {
  33.     if (node == null) {
  34.         return null;
  35.     }
  37.     //存在右子树的情况
  38.     Node<E> p = node.right;
  39.     if (p != null) {
  40.         while (p.left != null) {
  41.             p = p.left;
  42.         }
  43.         return p;
  44.     }
  46.     //不存在右子树的情况. 在父节点或者祖父结点找
  47.     while (node.parent != null && node == node.parent.right) {
  48.         node = node.parent;
  49.     }
  51.     return node.parent;
  53. }

删除

因为二叉树只有3种结点，叶子结点，度为1的结点，度为2的结点。所以删除按照这3种结点进行分类删除：

  1. 删除叶子结点。删除叶子结点比较简单，例如上面的二叉树。删除结点1，和7和11，就是删除叶子结点。删除1的时候，只需要 1.parent = null 和 1.parent.left = null 就可以了。删除7就是 7.parent = null 和7.parent.right = null。 删除11 , 11.parent = null 和 11.parent.left = null。 如果只有1个根结点，那么根结点就是叶子结点，那么直接 root = null 就可以了。

  2. 删除父节点为空的结点。只有1种情况，就是该结点是根结点。 只需要 root = null。 就可以了。

  3. 删除度=1 的结点。例如13和12 ，只需要将父结点的子，指向它的子。它的子的父节点指向，指向它的父即可。删除13，13.parent.right = 13.left 和 13.left.parent = 13.parent。 删除12 ： 12.parent.right = 12.left 和12.left.parent = 12.parent.

  4. 删除度=2 的结点。可以选择，使用它的前驱或者后继结点来替代。这样可以保持二叉树的整体结构不变。过程是，使用前驱或者后继结点的元素覆盖要删除的结点的元素。 然后删除前驱或者后继结点即可。前驱结点或后继结点一定是度为0或1的结点。

例如结点4,8,10。删除j结点4，结点4.element = 结点4.predecessor.element 和 删除结点4.predecessor。删
除结点8，结点8.element = 结点8.predecessor.element 和 删除结点8.predecessor。 删除结点10，结点
10.element = 结点10.predecessor.element 和 删除结点10.predecessor。这3个例子用的是前驱结点替代删
除的结点，使用后继结点来替代删除的结点也可以。

因为提供对外的删除接口是的参数是元素，不是结点，但是进行删除的时候真正删除的是结点。所以需要写2个方法中转一下，根据元素找到节点和删除结点。

  1. /**
  2.  * 根据元素返回对应的结点
  3.  * @param element 元素
  4.  * @return 元素所在的结点
  5.  */
  6. public Node<E> node(E element) {
  8.     Node<E> node = root;
  10.     while (node != null) {
  11.         int cmp = compareTo(element, node.element);
  13.         if (cmp == 0) {
  14.             return node;
  15.         }
  16.         if (cmp > 0) {
  17.             node = node.right;
  18.         }else {
  19.             node = node.left;
  20.         }
  21.     }
  23.     return null;
  24. }
  27. /**
  28.  * 删除一个指定的元素
  29.  */
  30. public void remove(E element){
  31.     remove(node(element));
  32. }
  35. /**
  36.  * 删除一个指定的结点
  37.  */
  38. private void remove(Node<E> node) {
  39.     //删除结点的实现
  40. }

根据上面的删除的思路，删除结点的方法实现如下：

  1. /**
  2.  * 删除一个指定的结点
  3.  */
  4. private void remove(Node<E> node) {
  6.     if (node == null) {
  7.         return;
  8.     }
  10.     size --;
  12.     //结点度=2的情况 ， 使用前驱来替代的方案
  13.     if (node.hasTowChildren()) {
  14.         //找到前驱
  15.         Node<E> predecessor = predecessor(node);
  17.         node.element = predecessor.element;
  19.         //删除前驱.  if语句块的外面，就是删除度=0或1的情况。所以直接赋值，在外面就可以删除了。
  20.         node = predecessor;
  21.     }
  24.     //先假设是度=1的情况
  25.     Node<E> child = node.left == null ? node.right : node.left;
  27.     if (child != null) {
  28.         //绝对是度=1 的情况，因为有子结点
  30.         if (node.parent == null) {
  31.             //根结点的情况
  32.             root = child;
  34.         } else {
  36.             child.parent = node.parent;
  38.             if (node == node.parent.left) {
  39.                 //删除的结点是左结点的情况
  40.                 node.parent.left = child;
  41.             } else {
  42.                 node.parent.right = child;
  43.                 //删除的结点是右结点的情况
  44.             }
  46.         }
  48.     } else {
  49.         //没有子节点，证明度=0，是叶子结点
  51.         if (node.parent == null) {
  52.             //根结点
  53.             root = null;
  54.         } else {
  55.             if (node == node.parent.left) {
  56.                 node.parent.left = null;
  58.             } else {
  59.                 node.parent.right = null;
  61.             }
  62.         }
  64.     }
  65. }

最后补充一下contains接口：

  2. /**
  3.  * 查找一个元素
  4.  * @param element 需要查找的元素
  5.  * @return 存在返回 true ，否则false
  6.  */
  7. public boolean contains(E element){
  8.     return node(element) != null;
  9. }

导致为止，二叉搜索树就完全实现了。

二叉搜索树的退化

在理想状态下，二叉树的添加、删除、查找结点的算法复杂度都是 O(logn)。
image.png
例如上面的二叉树：搜索结点2,9,11，由于是有序的，所以就是搜索的时候相当于二分搜索，所以，算法复杂度是O(logn)。 添加和删除结点也是相同的情况。

但是，如果是从小到大添加结点的话，二叉树可能就会变成如下的情况：

image.png
这时候二叉树就变成了链表的形状，搜索、添加、和删除结点，时间复杂度都变成了O(n)。 还有一种情况是，本身二叉树是相对正常的二叉树，但是由于删除结点，将二叉树变成单链的结构。
image.png image.png

这些二叉树变成链表的情况，称为二叉树的退化。由树结构退化成了链表结构。

要避免这种情况的话，就要在添加，删除结点的时候，保持二叉搜索树的平衡，左右子树的高度差不能相差太远。保持平衡的二叉树搜索树，就称为平衡二叉搜索树。经典的平衡二叉搜索树有：AVL树，红黑树。

完整的源码：
https://github.com/franck418/DataStrcture.git