玩转数据结构(11)删除二分搜索树的节点

一、删除二分搜索树的最小值和最大值

1.先找到二分搜索树的最小值和最大值

最小值&＃xff1a;二叉树中的最左侧的元素&＃xff08;不存在左孩子的节点&＃xff09;

最大值&＃xff1a;二叉树中的最右侧的元素&＃xff08;不存在右孩子的节点&＃xff09;

2.再删除二分搜索树的最小值和最大值

    1.当要删除的节点为叶子节点时&＃xff0c;直接删除即可

2.当要删除的节点不是叶子节点时&＃xff0c;将该节点删除&＃xff0c;删除后将其整个右子树变为根节点的左子树即可

代码实现&＃xff1a;

BST.java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class BST> {private class Node{public E e;public Node left, right;public Node(E e){this.e &＃61; e;left &＃61; null;right &＃61; null;}}private Node root;private int size;public BST(){root &＃61; null;size &＃61; 0;}public int size(){return size;}public boolean isEmpty(){return size &＃61;&＃61; 0;}// 向二分搜索树中添加新的元素epublic void add(E e){root &＃61; add(root, e);}// 向以node为根的二分搜索树中插入元素e&＃xff0c;递归算法// 返回插入新节点后二分搜索树的根private Node add(Node node, E e){if(node &＃61;&＃61; null){size &＃43;&＃43;;return new Node(e);}if(e.compareTo(node.e) <0)node.left &＃61; add(node.left, e);else if(e.compareTo(node.e) > 0)node.right &＃61; add(node.right, e);return node;}// 看二分搜索树中是否包含元素epublic boolean contains(E e){return contains(root, e);}// 看以node为根的二分搜索树中是否包含元素e, 递归算法private boolean contains(Node node, E e){if(node &＃61;&＃61; null)return false;if(e.compareTo(node.e) &＃61;&＃61; 0)return true;else if(e.compareTo(node.e) <0)return contains(node.left, e);else // e.compareTo(node.e) > 0return contains(node.right, e);}// 二分搜索树的前序遍历public void preOrder(){preOrder(root);}// 前序遍历以node为根的二分搜索树, 递归算法private void preOrder(Node node){if(node &＃61;&＃61; null)return;System.out.println(node.e);preOrder(node.left);preOrder(node.right);}// 二分搜索树的非递归前序遍历public void preOrderNR(){Stack stack &＃61; new Stack<>();stack.push(root);while(!stack.isEmpty()){Node cur &＃61; stack.pop();System.out.println(cur.e);if(cur.right !&＃61; null)stack.push(cur.right);if(cur.left !&＃61; null)stack.push(cur.left);}}// 二分搜索树的中序遍历public void inOrder(){inOrder(root);}// 中序遍历以node为根的二分搜索树, 递归算法private void inOrder(Node node){if(node &＃61;&＃61; null)return;inOrder(node.left);System.out.println(node.e);inOrder(node.right);}// 二分搜索树的后序遍历public void postOrder(){postOrder(root);}// 后序遍历以node为根的二分搜索树, 递归算法private void postOrder(Node node){if(node &＃61;&＃61; null)return;postOrder(node.left);postOrder(node.right);System.out.println(node.e);}// 二分搜索树的层序遍历public void levelOrder(){Queue q &＃61; new LinkedList<>();q.add(root);while(!q.isEmpty()){Node cur &＃61; q.remove();System.out.println(cur.e);if(cur.left !&＃61; null)q.add(cur.left);if(cur.right !&＃61; null)q.add(cur.right);}}// 寻找二分搜索树的最小元素&＃xff08;新增代码&＃xff09;public E minimum(){if(size &＃61;&＃61; 0) //二叉树中没有元素throw new IllegalArgumentException("BST is empty");Node minNode &＃61; minimum(root);return minNode.e;}// 返回以node为根的二分搜索树的最小值所在的节点&＃xff08;新增代码&＃xff09;private Node minimum(Node node){if( node.left &＃61;&＃61; null ) //最左侧为空的节点return node;return minimum(node.left);}// 寻找二分搜索树的最大元素&＃xff08;新增代码&＃xff09;public E maximum(){if(size &＃61;&＃61; 0)throw new IllegalArgumentException("BST is empty");return maximum(root).e;}// 返回以node为根的二分搜索树的最大值所在的节点&＃xff08;新增代码&＃xff09;private Node maximum(Node node){if( node.right &＃61;&＃61; null )return node;return maximum(node.right);}// 从二分搜索树中删除最小值所在节点, 返回最小值&＃xff08;新增代码&＃xff09;public E removeMin(){E ret &＃61; minimum();root &＃61; removeMin(root); //从root 开始尝试删除最小节点return ret;}// 删除掉以node为根的二分搜索树中的最小节点&＃xff08;新增代码&＃xff09;// 返回删除节点后新的二分搜索树的根private Node removeMin(Node node){if(node.left &＃61;&＃61; null){ //node 没有左孩子的情况Node rightNode &＃61; node.right; //保存当前节点的右子树node.right &＃61; null; //将当前的node节点从二叉树中脱离关系size --;return rightNode; //使右孩子成为新的节点}node.left &＃61; removeMin(node.left);//node 有左孩子的情况&＃xff0c;删除掉当前树的左子树对应的最小值return node;}// 从二分搜索树中删除最大值所在节点&＃xff08;新增代码&＃xff09;public E removeMax(){E ret &＃61; maximum();root &＃61; removeMax(root);return ret;}// 删除掉以node为根的二分搜索树中的最大节点&＃xff08;新增代码&＃xff09;// 返回删除节点后新的二分搜索树的根private Node removeMax(Node node){if(node.right &＃61;&＃61; null){Node leftNode &＃61; node.left;node.left &＃61; null;size --;return leftNode;}node.right &＃61; removeMax(node.right);return node;}&＃64;Overridepublic String toString(){StringBuilder res &＃61; new StringBuilder();generateBSTString(root, 0, res);return res.toString();}// 生成以node为根节点&＃xff0c;深度为depth的描述二叉树的字符串private void generateBSTString(Node node, int depth, StringBuilder res){if(node &＃61;&＃61; null){res.append(generateDepthString(depth) &＃43; "null\n");return;}res.append(generateDepthString(depth) &＃43; node.e &＃43;"\n");generateBSTString(node.left, depth &＃43; 1, res);generateBSTString(node.right, depth &＃43; 1, res);}private String generateDepthString(int depth){StringBuilder res &＃61; new StringBuilder();for(int i &＃61; 0 ; i }


Main.java

import java.util.ArrayList;
import java.util.Random;public class Main {public static void main(String[] args) {BST bst &＃61; new BST<>();Random random &＃61; new Random();int n &＃61; 1000; //向二叉树中添加1000个元素// test removeMinfor(int i &＃61; 0 ; i nums &＃61; new ArrayList<>();while(!bst.isEmpty()) //bst 不为空的话&＃xff0c; nums.add(bst.removeMin()); //从 bst 中取出元素&＃xff0c;将取出元素的最小值添加到 nums 的ArrayList中 System.out.println(nums);for(int i &＃61; 1 ; i nums.get(i))throw new IllegalArgumentException("Error!");System.out.println("removeMin test completed.");// test removeMaxfor(int i &＃61; 0 ; i ();while(!bst.isEmpty())nums.add(bst.removeMax());System.out.println(nums);for(int i &＃61; 1 ; i }


输出&＃xff1a;

二、删除二分搜索树的任意元素

1.删除只有左孩子的节点&＃xff1a;节点删除之后&＃xff0c;将左孩子所在的二叉树取代其位置&＃xff1b;连在原来父亲元素右节点的位置

2.删除只有右孩子的节点&＃xff1a;节点删除之后&＃xff0c;将右孩子所在的二叉树取代其位置&＃xff1b;连在原来父亲元素左节点的位置

3.难点&＃xff1a;删除有左右孩子的节点&＃xff08;删除左右都有孩子的节点d&＃xff09;

在图中&＃xff0c;要删除58&＃xff0c;就是要找到58的替代节点&＃xff0c;找 58 &＃xff08;d&＃xff09;的后继&＃xff1a;所有元素中&＃xff0c;离 58 最近的且比 58 大的节点&＃xff0c;即图中的 59 (s)【即右子树中的最小值】

示例代码&＃xff1a;BST.java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class BST> {private class Node{public E e;public Node left, right;public Node(E e){this.e &＃61; e;left &＃61; null;right &＃61; null;}}private Node root;private int size;public BST(){root &＃61; null;size &＃61; 0;}public int size(){return size;}public boolean isEmpty(){return size &＃61;&＃61; 0;}// 向二分搜索树中添加新的元素epublic void add(E e){root &＃61; add(root, e);}// 向以node为根的二分搜索树中插入元素e&＃xff0c;递归算法// 返回插入新节点后二分搜索树的根private Node add(Node node, E e){if(node &＃61;&＃61; null){size &＃43;&＃43;;return new Node(e);}if(e.compareTo(node.e) <0)node.left &＃61; add(node.left, e);else if(e.compareTo(node.e) > 0)node.right &＃61; add(node.right, e);return node;}// 看二分搜索树中是否包含元素epublic boolean contains(E e){return contains(root, e);}// 看以node为根的二分搜索树中是否包含元素e, 递归算法private boolean contains(Node node, E e){if(node &＃61;&＃61; null)return false;if(e.compareTo(node.e) &＃61;&＃61; 0)return true;else if(e.compareTo(node.e) <0)return contains(node.left, e);else // e.compareTo(node.e) > 0return contains(node.right, e);}// 二分搜索树的前序遍历public void preOrder(){preOrder(root);}// 前序遍历以node为根的二分搜索树, 递归算法private void preOrder(Node node){if(node &＃61;&＃61; null)return;System.out.println(node.e);preOrder(node.left);preOrder(node.right);}// 二分搜索树的非递归前序遍历public void preOrderNR(){Stack stack &＃61; new Stack<>();stack.push(root);while(!stack.isEmpty()){Node cur &＃61; stack.pop();System.out.println(cur.e);if(cur.right !&＃61; null)stack.push(cur.right);if(cur.left !&＃61; null)stack.push(cur.left);}}// 二分搜索树的中序遍历public void inOrder(){inOrder(root);}// 中序遍历以node为根的二分搜索树, 递归算法private void inOrder(Node node){if(node &＃61;&＃61; null)return;inOrder(node.left);System.out.println(node.e);inOrder(node.right);}// 二分搜索树的后序遍历public void postOrder(){postOrder(root);}// 后序遍历以node为根的二分搜索树, 递归算法private void postOrder(Node node){if(node &＃61;&＃61; null)return;postOrder(node.left);postOrder(node.right);System.out.println(node.e);}// 二分搜索树的层序遍历public void levelOrder(){Queue q &＃61; new LinkedList<>();q.add(root);while(!q.isEmpty()){Node cur &＃61; q.remove();System.out.println(cur.e);if(cur.left !&＃61; null)q.add(cur.left);if(cur.right !&＃61; null)q.add(cur.right);}}// 寻找二分搜索树的最小元素public E minimum(){if(size &＃61;&＃61; 0)throw new IllegalArgumentException("BST is empty!");return minimum(root).e;}// 返回以node为根的二分搜索树的最小值所在的节点private Node minimum(Node node){if(node.left &＃61;&＃61; null)return node;return minimum(node.left);}// 寻找二分搜索树的最大元素public E maximum(){if(size &＃61;&＃61; 0)throw new IllegalArgumentException("BST is empty");return maximum(root).e;}// 返回以node为根的二分搜索树的最大值所在的节点private Node maximum(Node node){if(node.right &＃61;&＃61; null)return node;return maximum(node.right);}// 从二分搜索树中删除最小值所在节点, 返回最小值public E removeMin(){E ret &＃61; minimum();root &＃61; removeMin(root);return ret;}// 删除掉以node为根的二分搜索树中的最小节点// 返回删除节点后新的二分搜索树的根private Node removeMin(Node node){if(node.left &＃61;&＃61; null){Node rightNode &＃61; node.right;node.right &＃61; null;size --;return rightNode;}node.left &＃61; removeMin(node.left);return node;}// 从二分搜索树中删除最大值所在节点public E removeMax(){E ret &＃61; maximum();root &＃61; removeMax(root);return ret;}// 删除掉以node为根的二分搜索树中的最大节点// 返回删除节点后新的二分搜索树的根private Node removeMax(Node node){if(node.right &＃61;&＃61; null){Node leftNode &＃61; node.left;node.left &＃61; null;size --;return leftNode;}node.right &＃61; removeMax(node.right);return node;}// 从二分搜索树中删除元素为e的节点&＃xff08;新增代码&＃xff09;public void remove(E e){root &＃61; remove(root, e);}// 删除掉以node为根的二分搜索树中值为e的节点, 递归算法&＃xff08;新增代码&＃xff09;// 返回删除节点后新的二分搜索树的根private Node remove(Node node, E e){//&＃xff08;新增代码&＃xff09;if( node &＃61;&＃61; null )return null;if( e.compareTo(node.e) <0 ){ //要删除的元素 e 要比 node上的元素 e 要小的话node.left &＃61; remove(node.left , e); //到左子树中删除return node;}else if(e.compareTo(node.e) > 0 ){//要删除的元素 e 要比 node上的元素 e 要大的话node.right &＃61; remove(node.right, e); //到右子树中删除return node;}else{ // e.compareTo(node.e) &＃61;&＃61; 0// 待删除节点左子树为空的情况//&＃xff08;新增代码&＃xff09;if(node.left &＃61;&＃61; null){ Node rightNode &＃61; node.right; //保存右子树内容node.right &＃61; null; //将 右子树与二叉树断开关系size --;return rightNode; //返回原来元素的右孩子【右子树的根节点】}// 待删除节点右子树为空的情况if(node.right &＃61;&＃61; null){Node leftNode &＃61; node.left;node.left &＃61; null;size --;return leftNode;}// 待删除节点左右子树均不为空的情况//&＃xff08;新增代码&＃xff09;// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点// 用这个节点顶替待删除节点的位置Node successor &＃61; minimum(node.right); //要找到 node 节点的后继successor.right &＃61; removeMin(node.right); //从node.right中removeMin 掉其中的最小节点&＃xff0c;根节点返回作为后继的右子树successor.left &＃61; node.left; // successor 替代原来的 node 节点node.left &＃61; node.right &＃61; null; //node 节点与二分搜索树脱离关系return successor;} }&＃64;Overridepublic String toString(){StringBuilder res &＃61; new StringBuilder();generateBSTString(root, 0, res);return res.toString();}// 生成以node为根节点&＃xff0c;深度为depth的描述二叉树的字符串private void generateBSTString(Node node, int depth, StringBuilder res){if(node &＃61;&＃61; null){res.append(generateDepthString(depth) &＃43; "null\n");return;}res.append(generateDepthString(depth) &＃43; node.e &＃43;"\n");generateBSTString(node.left, depth &＃43; 1, res);generateBSTString(node.right, depth &＃43; 1, res);}private String generateDepthString(int depth){StringBuilder res &＃61; new StringBuilder();for(int i &＃61; 0 ; i }


补充&＃xff1a;

总结&＃xff1a;

1.二分搜索树的顺序性&＃xff1a;放入.二分搜索树的元素都是有序的&＃xff1b;

2.floor 和 ceil:floor:比45小的最大元素&＃xff1b;ceil:比45大的最小元素【这两个可以不在二分搜索树中】

3.rank &＃xff1a;58 在整个树中所有的元素里排第几

4.select:rank 的反向操作

5.维护 size 的二分搜索树

6.支持重复元素的二分搜索树&＃xff08;定义左子树的节点 <&＃61; 父节点的值&＃xff09;