1 折半查找法
了解二叉查找树之前，先来看看折半查找法,也叫二分查找法 在一个有序的整数数组中（假如是从小到大排序的），如果查找某个元素，返回元素的索引。
如下：
1int[] arr = new int[]{1,3,4,6,8,9}; 2在 arr 数组中查找6这个元素，查到返回对应的索引，没有找到就返回-1
思想很简单: 1 先找到数组中间元素target与6比较 2 如果target比6大，就在数组的左边查找 3 如果target比6小，就在数组的右边查找
java实现代码如下：
1 private static int binarySearch(int[] data, int target) { 2 int l = 0; 3 int r = data.length - 1; 4 5 while (l <= r) { 6 //int mid = (l + r) / 2; 7 //这句代码理论上是没有问题的，但是是有bug的 8 //如果因为 l + r 会超过整数的最大值，就会溢出 9 //所以换成下面的写法，最小边界，加上差的一半，就是中间索引 10 11 //最小边界，加上差的一半，就是中间值 12 int mid = l + (r - l) / 2; 13 14 15 if (data[mid] > target) { //如果中间的值比target大,r向右移动。 16 r = mid - 1; 17 } else if (data[mid] < target) { //如果中间的值比target小，l向左移动 18 l = mid + 1; 19 } else { 20 return mid; //如果中间的值与target相等，就返回下标 21 } 22 } 23 24 //没有找到就返回-1 25 return -1; 26 }
测试代码如下：
1 public static void main(String[] args) { 2 int[] data = new int[]{1,3,4,6,8,9}; 3 System.out.println(binarySearch(data, 6)); 4 }
输出
3
折半查找的关键是数组必须有序，一次过滤掉一半的数据，时间复杂度为O（logN）。 上面是以2为底的，N为数组的元素个数.
折半查找和下面的要讲的二分搜索树是有一样的思想
2 二分搜索树定义
二分搜索树定义双叫二分查找树，其定义如下 1 若它的左子树不为空，则左子树上所有的节点的值均小于根结点的值 2 若它的右子树不为空，则右子树上所有的节点的值均大于根结点的值 3 它的左右子树也分别为二分搜索树
由二叉搜索树的定义可知，它前提是二叉树，并且采用了递归的定义方式 。再得，它的节点满足一定的关系，左子树的节点一定比父节点的小， 右子树的节点一定比父节点的大。
构造一棵二叉搜索树的目的，其实目的不是为了排序，是为了提高查找，删除，插入关键字的速度。
下面我们用图和代码来解释二叉树的查找，插入，和删除。比如下图就是一个二叉搜索树
2.0 二叉搜索树的定义和节点的定义
二叉搜索树中存放的都是key。先看下二叉树的定义
1 //key必须继承Comparable，可以比较大小的 2 public class QBST<K extends Comparable<K>, V> { 3 ... 4 }
二叉树中节点的定义
1 //QNode是作为QBST的内部类的。后面会有完整的源码 2 class QNode { 3 //key,也相当于上图中的数字，只不过不一定是数字 4 //只要能比较大小就行了。这里的key，是继承Comparable的 5 K key; 6 7 //节点中的value 8 V value; 9 10 //左子树 11 QNode left; 12 13 //右子树 14 QNode right; 15 16 //根据key,value构造一个节点 17 QNode(K key, V value) { 18 this.key = key; 19 this.value = value; 20 this.left = null; 21 this.right = null; 22 } 23 24 //根据一个节点，构造另一个新节点 25 QNode(QNode node){ 26 this.key = node.key; 27 this.value = node.value; 28 this.left = node.left; 29 this.right = node.right; 30 } 31 }
类的定义和类中节点的定义都有了。 二分搜索树的定义如下：
1/** 2 * 二分搜索树，也叫二分查找树 3 */ 4public class QBST<K extends Comparable<K>, V> { 5 class QNode { 6 K key; 7 V value; 8 QNode left; 9 QNode right; 10 11 QNode(K key, V value) { 12 this.key = key; 13 this.value = value; 14 this.left = null; 15 this.right = null; 16 } 17 18 QNode(QNode node){ 19 this.key = node.key; 20 this.value = node.value; 21 this.left = node.left; 22 this.right = node.right; 23 } 24 } 25 26 //树的根 27 private QNode root; 28 //树中节点的个数 29 private int count; 30 31 //构造一棵空的二分搜索树 32 public QBST() { 33 root = null; 34 count = 0; 35 } 36 37 //返回二分搜索树中的个数 38 public int size() { 39 return count; 40 } 41 42 //树是否为空 43 public boolean isEmpty() { 44 return count == 0; 45 } 46 47 }
2.1 二叉搜索树的插入
1 如果这棵树为空，新建一个节点，作为根 2 如果要插入的key比根节点大，就插入到右子树中 3 如果要插入的key比根节点小，就插入到左子树中 4 如果要插入的key和根节点相等，就更新当前节点的value 代码如下：
1 public void insert(K key, V value) { 2 root = insert(root, key, value); 3 } 4 5 // 向以node为根的二叉搜索树中，插入节点(key,value) 6 // 返回插入新节点后的二叉搜索树的根 7 private QNode insert(QNode node, K key, V value) { 8 //查检条件 9 checkNotNull(key,"key is null"); 10 11 //如果node为空,直接new一个节点返回 12 if (node == null) { 13 count++; 14 return new QNode(key, value); 15 } 16 17 //如果key比根节点大，插入到node的右子树中 18 if (key.compareTo(node.key) == 1) { 19 node.right = insert(node.right, key, value); 20 21 //如果key比根节点小，插入到node的左子树中 22 } else if (key.compareTo(node.key) == -1) { 23 node.left = insert(node.left, key, value); 24 25 //如果key和根节点相等，更新根节点的value 26 } else { 27 node.value = value; 28 } 29 30 //返回根 31 return node; 32 }
2.2 二叉搜索树的查找
和上面向一棵二叉搜索树插入一个节点一样。 向一棵二叉搜索树中查找一个节点也是类似 1 如果根节点为空，不用查找了，返回null 2 如果key比根节点的key要大，在右子树中查找 3 如果key比根节点的key要小，在左子树中查找 4 如果key和根节点的key相等，返回根节点
代码实现如下：
1 //搜索key结果的value 2 public V search(K key){ 3 return search(root,key); 4 } 5 6 // 向以node为根的二叉搜索树中，以key为键，返回V 7 private V search(QNode node,K key){ 8 checkNotNull(key,"key is null"); 9 10 //如果当前节点为null,返回null 11 if(node == null){ 12 return null; 13 } 14 15 //如果key比根节点的key大，在右子树中查找 16 if(key.compareTo(node.key) == 1){ 17 return search(node.right,key); 18 19 //如果key比根节点的key小，在左子树中查找 20 }else if(key.compareTo(node.key) == -1){ 21 return search(node.left,key); 22 23 //如果key与根节点的key值相等，就返回节点的value值 24 }else { 25 return node.value; 26 } 27 }
2.3 二叉搜索树的遍历
二叉树的遍历有前序遍历，中序遍历，后序遍历，层序遍历（也叫做广度优先遍历）
如下图的二叉搜索树。
根据根节点的访问顺序，可以把遍历分为前序遍历，中序遍历，后序遍历 前序遍历：先访问根节点，再前序遍历左右子树 中序遍历：先中序遍历左子树，再访问根节点，后中序遍历右子树 后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点
代码实现分别如下：
1 // 前序遍历 O(n) 2 public void preOrder(){ 3 //后序遍历以root为根的二叉搜索树 4 preOrder(root); 5 } 6 7 private void preOrder(QNode node){ 8 if(node != null){ 9 //先遍历根节点 10 System.out.println(node.key);//这里的访问只是打印 11 //前序遍历左子树 12 preOrder(node.left); 13 //后序遍历右子树 14 preOrder(node.right); 15 } 16 } 17 18 // 中序遍历 O(n) 19 public void middleOrder(){ 20 middleOrder(root); 21 } 22 23 private void middleOrder(QNode node){ 24 if(node != null){ 25 middleOrder(node.left); 26 System.out.println(node.key); 27 middleOrder(node.right); 28 } 29 } 30 31 // 后序遍历 O(n) 32 public void postOrder(){ 33 postOrder(root); 34 } 35 36 private void postOrder(QNode node){ 37 if(node != null){ 38 postOrder(node.left); 39 postOrder(node.right); 40 System.out.println(node.key); 41 } 42 } 43
其中层序遍历就是一层一层的从左到右遍历 上图中层序遍历的结果是 13 6 15 3 7 10 18 代码实现需要借助队列，代码实现如下：
1 // 层序遍历，也叫做广度优先遍历 2 public void levelOrder(){ 3 if (root == null){ 4 return; 5 } 6 7 LinkedList<QNode> q = new LinkedList<>(); 8 q.addLast(root); 9 10 while (!q.isEmpty()){ 11 QNode node = q.removeFirst(); 12 System.out.println("节点的值是：" + node.key); 13 14 if(node.left != null){ 15 q.addLast(node.left); 16 } 17 if(node.right != null){ 18 q.addLast(node.right); 19 } 20 21 } 22 } 23
2.4 二叉搜索树的删除
二叉搜索树最麻烦的就是删除节点，删除任意二叉树中的节点之前，我们来先删除特殊的节点。
- 删除二叉搜索树中最小的节点
- 删除二叉搜索树中最大的节点
- 查找二叉搜索树中最小的节点
- 查找二叉搜索树中最大的节点
我们先来实现这些操作。
如下图
根据二叉搜索树的定义，可以得出以下结论
- 在一个二叉搜索树中，最小的节点一定是最左边的节点，也就是图中的节点 3
- 在一个二叉搜索树中，最大的节点一定是最右边的节点，也就是图中的节点 18
总之： 最小节点去左子树中找，直到节点的左孩子为空，则当前节点就是最小节点 最大节点去右子树中找，直到节点的右孩子为空，则当前节点就是最大节点
1 先来实现查找二叉搜索树中最小的节点 如下代码
1 //查找一棵树中最小的节点，返回 K 2 public K minimum(){ 3 checkNotNull(root,"the tree is empty"); 4 5 //在以根为root的二叉搜索树中返回最小节点的键值 6 QNode minNode = minimum(root); 7 8 //返回最小节点的键值 9 return minNode.key; 10 } 11 12 // 在以node为根的二叉搜索树中，返回最小键值的节点 13 private QNode minimum(QNode node){ 14 //如果node.left == null,说明当前node节点就是最小的节点 15 //返回当前节点node 16 if(node.left == null){ 17 return node; 18 } 19 20 //如果当前节点不是最小的节点 21 //继承往左子树中查找 22 return minimum(node.left); 23 }
同理，查找最大节点也是一样 2 实现查找二叉搜索树中最大的节点 代码如下：
1 2 public K maximum(){ 3 checkNotNull(root,"the tree is empty"); 4 QNode maxNode = maximum(root); 5 return maxNode.key; 6 } 7 8 // 在以node为根的二叉搜索树中，返回最大键值的节点 9 private QNode maximum(QNode node){ 10 if(node.right == null){ 11 return node; 12 } 13 14 return maximum(node.right); 15 }
上面实现了查找最小节点和最大节点，下面我们再来实现删除最小节点和删除最大节点
3 实现删除二叉搜索树中最小的节点 一直往左孩子中删除，当某一个节点node没有左孩子时，说明当前节点就是最小节点 这时候分两种情况
- 当前节点有右孩子 如果是这种情况，直接把右孩子返回，作为当前节点
- 当前节点没有右孩子 如果是这种情况，直接返回null。此时返回右孩子也行，因为右孩子也是null
代码实现如下
1 // 删除二叉搜索树中最小的节点 2 public void removeMin(){ 3 if(root != null){ 4 root = removeMin(root); 5 } 6 } 7 8 // 删除掉以node为根的二分搜索树中的最小的节点 9 // 返回删除节点后新的二分搜索树的根 10 private QNode removeMin(QNode node){ 11 //如果当前当前没有左孩子，则当前节点就是最小节点 12 if(node.left == null){ 13 //保存当前节点的右孩子，这句代码把上面两种情况都包含了 14 QNode rightNode = node.right; 15 node = null; //释放当前节点 16 count--; //记得数量要减1 17 return rightNode;//返回右孩子，有可能为空或者不为空 18 } 19 20 //递归调用删除以当前节点的左孩子为根的二叉搜索中最小的节点 21 node.left = removeMin(node.left); 22 23 //别忘了返回当前节点 24 return node; 25 }
同理，删除二叉搜索树中最大的节点的代码如下：
1 // 删除二叉搜索树中最大的节点 2 public void removeMax(){ 3 if(root != null){ 4 root = removeMax(root); 5 } 6 } 7 8 // 删除掉以node为根的二分搜索树中的最大的节点 9 // 返回删除节点后新的二分搜索树的根 10 private QNode removeMax(QNode node){ 11 if(node.right == null){ 12 QNode leftNode = node.left; 13 count--; 14 node = null; 15 16 return leftNode; 17 } 18 19 node.right = removeMax(node.right); 20 return node; 21 }
下面来分析一下删除任意一个节点。 删除任意一个节点node，那么可以分为以下几种情况
- node 没有孩子
- node 只有一个孩子
- node 有两个孩子
如下图一棵二叉搜索树，我们来分析
第一种情况：node没有孩子
这种情况最简单，直接删除就行了，剩下的还是一棵二叉搜索树
比如图中的 节点5，节点13，节点27，节点50，删除任意一个节点之后
剩下的还是满足一棵二叉搜索树
第二种情况：node只有一个孩子 这种情况又分两种
- node节点有一个左孩子
- node节点有一个右孩子
上面两种情况其实不影响，比如图中的节点10，节点45,分别有一个左孩子和一个右孩子。
也好办，节点10删除后，它的左孩子节点5，放在节点10的位置
同理知，节点45删除后，它的右孩子节点50，放在节点45的位置
这样一来，剩下的节点还是一棵二叉搜索树
第三种情况：node有两个孩子
还是上图为准，以节点17为例，节点17有左右两个孩子,分别是10，19
要删除节点17，怎么办呢？
或者说节点17删除 后，哪个节点应该放在节点17的位置上呢？
我们节点17满足两个性质 ：
- 17大于它的左孩子10
- 17小于它的右孩子19
那么我们找到一个这样的节点，只要满足上面这两条性质，不就是可以了吗。 so easey
我们就来先找一个大于10而且小于19的节点
- 大于 10 的节点，只要在 17 的右子树 也就是以 19 为根节点的树中找不就行了吗 因为17的右子树中所有的节点都比 17 大
- 小于 19 的节点，只要在以 19 为根的树中找左孩子不就得了吗
经过上面的分析，这样的节点就是 13 啊，将17删除 ，把13放到17的位置 ，如图
其实，把10放到17的位置也是可以的。如下图
10和13两个节点都满足条件，所以我们可以得出结论
删除一个有两个孩子节点，可以找这个节点左子树中的最大节点，或者右子树中的最小节点来放到当前位置
伪代码：
删除左右都 有孩子的节点 d
找到 s = min(d.right)
s 可以叫作 d 的后继
s.right = deledeMin(d->right)
s.left = d.left;
删除 d, s 是新的子树的根
翻译成代码如下：
1 public void remove(K key) { 2 root = remove(root, key); 3 } 4 5 // 删除掉以node为根的二分搜索树中键值为key的节点 6 // 返回删除节点后新的二分搜索树的根 7 // O(logN) 8 private QNode remove(QNode node, K key) { 9 //如果树为null,返回null 10 if (node == null) { 11 return null; 12 } 13 14 //想要删除某个节点，必须先要找到这个节点 15 //所以下面的代码包含了查找 16 17 if (key.compareTo(node.key) == -1) {//如果key小于根节点的key 18 19 //到node的左子树查找并删除键值为key的节点 20 node.left = remove(node.left, key); 21 22 //返回删除节点后新的二分搜索树的根 23 return node; 24 25 } else if (key.compareTo(node.key) == 1) {//如果key大于根节点的key 26 27 //到node的右子树查找并删除键值为key的节点 28 node.right = remove(node.right, key); 29 30 //返回删除节点后新的二分搜索树的根 31 return node; 32 } else { //key == node.key,也就是找到了这个节点 33 34 //当前节点的左孩子为null 35 if (node.left == null) { 36 //保存右孩子节点 37 QNode rightNode = node.right; 38 //个数减1 39 count--; 40 41 //删除 42 node = null; 43 44 //右节点作为新的根 45 return rightNode; 46 } 47 48 //当前节点的右孩子为null 49 if (node.right == null) { 50 //保存左孩子的节点 51 QNode leftNode = node.left; 52 //个数减1 53 count--; 54 55 //删除 56 node = null; 57 58 //左节点作为新的根 59 return leftNode; 60 } 61 62 //上面的情况也包括了左右两个孩子都是null 63 //这样的情况就走第一种，node.left==null的条件中。也满足 64 65 66 //下面是 node.left != null && node.right != null的情况 67 68 //找到右子树中最小节点 69 QNode min = minimum(node.right); 70 71 //用最小节点新建一个节点,因为等会要删除最小的节点，所以这里我们要新建一个最小节点 72 QNode s = new QNode(min); 73 74 //s的右孩子，就是删除node右子树中最小节点返回的根 75 s.right = removeMin(node.right); 76 77 //s的左孩子，就是删除节点的左孩子 78 s.left = node.left; 79 80 //返回新的根 81 return s; 82 } 83 }
同过上面的分析，我们了解了二叉搜索树的性质，以及插入，查找，查找最大节点，查找最小节点，删除最大节点，删除最小节点，以及最后分析出来删除一个任意节点。
下面我们粘出完整代码 。如下
1 2/** 3 * 二分搜索树，也叫二分查找树 4 */ 5public class QBST<K extends Comparable<K>, V> { 6 class QNode { 7 K key; 8 V value; 9 QNode left; 10 QNode right; 11 12 QNode(K key, V value) { 13 this.key = key; 14 this.value = value; 15 this.left = null; 16 this.right = null; 17 } 18 19 QNode(QNode node) { 20 this.key = node.key; 21 this.value = node.value; 22 this.left = node.left; 23 this.right = node.right; 24 } 25 } 26 27 private QNode root; 28 private int count; 29 30 31 public QBST() { 32 root = null; 33 count = 0; 34 } 35 36 public int size() { 37 return count; 38 } 39 40 public boolean isEmpty() { 41 return count == 0; 42 } 43 44 public void insert(K key, V value) { 45 root = insert(root, key, value); 46 } 47 48 // 向以node为根的二叉搜索树中，插入节点(key,value) 49 // 返回插入新节点后的二叉搜索树的根 50 private QNode insert(QNode node, K key, V value) { 51 checkNotNull(key, "key is null"); 52 53 if (node == null) { 54 count++; 55 return new QNode(key, value); 56 } 57 58 if (key.compareTo(node.key) == 1) { 59 node.right = insert(node.right, key, value); 60 } else if (key.compareTo(node.key) == -1) { 61 node.left = insert(node.left, key, value); 62 } else { 63 node.value = value; 64 } 65 66 return node; 67 } 68 69 public boolean contain(K key) { 70 return contain(root, key); 71 } 72 73 // 向以node为根的二叉搜索树中，查找是否包含key的节点 74 private boolean contain(QNode node, K key) { 75 checkNotNull(key, "key is null"); 76 77 if (node == null) { 78 return false; 79 } 80 81 if (key.compareTo(node.key) == 1) { 82 return contain(node.right, key); 83 } else if (key.compareTo(node.key) == -1) { 84 return contain(node.left.key); 85 } else { 86 return true; 87 } 88 } 89 90 public V search(K key) { 91 return search(root, key); 92 } 93 94 // 向以node为根的二叉搜索树中， 95 private V search(QNode node, K key) { 96 checkNotNull(key, "key is null"); 97 98 if (node == null) { 99 return null; 100 } 101 102 if (key.compareTo(node.key) == 1) { 103 return search(node.right, key); 104 } else if (key.compareTo(node.key) == -1) { 105 return search(node.left, key); 106 } else { 107 return node.value; 108 } 109 } 110 111 // 前序遍历 O(n) 112 public void preOrder() { 113 preOrder(root); 114 } 115 116 private void preOrder(QNode node) { 117 if (node != null) { 118 System.out.println(node.key); 119 preOrder(node.left); 120 preOrder(node.right); 121 } 122 } 123 124 // 中序遍历 O(n) 125 public void middleOrder() { 126 middleOrder(root); 127 } 128 129 private void middleOrder(QNode node) { 130 if (node != null) { 131 middleOrder(node.left); 132 System.out.println(node.key); 133 middleOrder(node.right); 134 } 135 } 136 137 // 后序遍历 O(n) 138 public void postOrder() { 139 postOrder(root); 140 } 141 142 private void postOrder(QNode node) { 143 if (node != null) { 144 postOrder(node.left); 145 postOrder(node.right); 146 System.out.println(node.key); 147 } 148 } 149 150 // 层序遍历，也叫做广度优先遍历 151 public void levelOrder() { 152 if (root == null) { 153 return; 154 } 155 156 LinkedList<QNode> queue = new LinkedList<>(); 157 queue.addLast(root); 158 159 while (!queue.isEmpty()) { 160 QNode node = queue.removeLast(); 161 System.out.println(node.key); 162 queue.addLast(node.left); 163 queue.addLast(node.right); 164 } 165 } 166 167 public void destroy() { 168 destroy(root); 169 } 170 171 // 销毁操作就是后序遍历的一次应用 172 private void destroy(QNode node) { 173 if (node != null) { 174 destroy(node.left); 175 destroy(node.right); 176 177 node = null; 178 count--; 179 } 180 } 181 182 public K minimum() { 183 checkNotNull(root, "the tree is empty"); 184 QNode minNode = minimum(root); 185 return minNode.key; 186 } 187 188 // 在以node为根的二叉搜索树中，返回最小键值的节点 189 private QNode minimum(QNode node) { 190 if (node.left == null) { 191 return node; 192 } 193 194 return minimum(node.left); 195 } 196 197 public K maximum() { 198 checkNotNull(root, "the tree is empty"); 199 QNode maxNode = maximum(root); 200 return maxNode.key; 201 } 202 203 // 在以node为根的二叉搜索树中，返回最大键值的节点 204 private QNode maximum(QNode node) { 205 if (node.right == null) { 206 return node; 207 } 208 209 return maximum(node.right); 210 } 211 212 // 删除二叉搜索树中最小的节点 213 public void removeMin() { 214 if (root != null) { 215 root = removeMin(root); 216 } 217 } 218 219 // 删除掉以node为根的二分搜索树中的最小的节点 220 // 返回删除节点后新的二分搜索树的根 221 private QNode removeMin(QNode node) { 222 if (node.left == null) { 223 QNode rightNode = node.right; 224 node = null; 225 count--; 226 return rightNode; 227 } 228 229 node.left = removeMin(node.left); 230 return node; 231 } 232 233 // 删除二叉搜索树中最大的节点 234 public void removeMax() { 235 if (root != null) { 236 root = removeMax(root); 237 } 238 } 239 240 // 删除掉以node为根的二分搜索树中的最大的节点 241 // 返回删除节点后新的二分搜索树的根 242 private QNode removeMax(QNode node) { 243 if (node.right == null) { 244 QNode leftNode = node.left; 245 count--; 246 node = null; 247 248 return leftNode; 249 } 250 251 node.right = removeMax(node.right); 252 return node; 253 } 254 255 public void remove(K key) { 256 root = remove(root, key); 257 } 258 259 // 删除掉以node为根的二分搜索树中键值为key的节点 260 // 返回删除节点后新的二分搜索树的根 261 // O(logN) 262 private QNode remove(QNode node, K key) { 263 //如果树为null,返回null 264 if (node == null) { 265 return null; 266 } 267 268 //想要删除某个节点，必须先要找到这个节点 269 //所以下面的代码包含了查找 270 271 if (key.compareTo(node.key) == -1) {//如果key小于根节点的key 272 273 //到node的左子树查找并删除键值为key的节点 274 node.left = remove(node.left, key); 275 276 //返回删除节点后新的二分搜索树的根 277 return node; 278 279 } else if (key.compareTo(node.key) == 1) {//如果key大于根节点的key 280 281 //到node的右子树查找并删除键值为key的节点 282 node.right = remove(node.right, key); 283 284 //返回删除节点后新的二分搜索树的根 285 return node; 286 } else { //key == node.key,也就是找到了这个节点 287 288 //当前节点的左孩子为null 289 if (node.left == null) { 290 //保存右孩子节点 291 QNode rightNode = node.right; 292 //个数减1 293 count--; 294 295 //删除 296 node = null; 297 298 //右节点作为新的根 299 return rightNode; 300 } 301 302 //当前节点的右孩子为null 303 if (node.right == null) { 304 //保存左孩子的节点 305 QNode leftNode = node.left; 306 //个数减1 307 count--; 308 309 //删除 310 node = null; 311 312 //左节点作为新的根 313 return leftNode; 314 } 315 316 //上面的情况也包括了左右两个孩子都是null 317 //这样的情况就走第一种，node.left==null的条件中。也满足 318 319 320 //下面是 node.left != null && node.right != null的情况 321 322 //找到右子树中最小节点 323 QNode min = minimum(node.right); 324 325 //用最小节点新建一个节点,因为等会要删除最小的节点，所以这里我们要新建一个最小节点 326 QNode s = new QNode(min); 327 328 //s的右孩子，就是删除node右子树中最小节点返回的根 329 s.right = removeMin(node.right); 330 331 //s的左孩子，就是删除节点的左孩子 332 s.left = node.left; 333 334 //返回新的根 335 return s; 336 } 337 } 338 339 340 private <E> void checkNotNull(E e, String message) { 341 if (e == null) { 342 throw new IllegalArgumentException(message); 343 } 344 } 345 346}