引言
二叉搜索树又称为（二叉排序树、二叉查找树），什么是二叉搜索树？
它是一棵空树，或者具有下列性质的二叉树
① 它的左子树不为空，则左子树上所有的节点的值均小于它的根节点的值。
② 它的右子树不为空，则右子树上所有的节点的值均大于它的根节点的值。
③ 它的左、右子树也分别为二叉搜索树。
二叉搜索树的中序遍历的数据是一个已排序好的数据。然而，构造一棵二叉搜索树的目的，不是为了排序，而是为了提高查找、添加、删除数据的速度。
一、说明
本篇博客实现的二叉搜索树的形状如下，也即是对下面这棵树进行操作。
二、代码实现增查删
1. 创建一个 java 文件，里面放着两个类
一个是 Node 类，表示某个节点的当前状态
另一个是 SearchTree，表示二叉树的当前状态
class Node{ public int val; public Node left; public Node right; public Node(int val){ this.val = val; } } public class SearchTree { public Node root = null; /** * 在搜索树中查找某个值 key */ public int search(int key){ if(root == null){ return -1; } Node cur = root; while(cur != null){ if(key == cur.val){ return cur.val; }else if(key < cur.val){ cur = cur.left; }else { cur = cur.right; } } return -1; } /** * 在搜索树中添加数据 * ① 插入的数据不能与节点相同 * ② 插入的数据只能在叶子节点 */ public boolean insertData(int data){ if(root == null){ root = new Node(data); return true; } Node cur = root; Node parent = null; //让 parent 始终为 cur 的双亲节点 while(cur != null){ if(data == cur.val){ return false; } else if (data < cur.val) { parent = cur; cur = cur.left; } else { parent = cur; cur = cur.right; } } if(data < parent.val){ parent.left = new Node(data); return true; }else { parent.right = new Node(data); return true; } } /** * 中序遍历 */ public void inorder(Node root){ if(root == null) return; inorder(root.left); System.out.print(root.val+" "); inorder(root.right); } /** * 删除搜索树中的值 key */ public boolean remove(int key){ if(root == null) return false; Node cur = root; Node parent = null; //让 parent 始终为 cur 的双亲节点 while(cur != null){ if (key == cur.val){ execute(key,cur,parent); return true; }else if (key < cur.val) { parent = cur; cur = cur.left; }else { parent = cur; cur = cur.right; } } return false; } public void execute(int key, Node cur, Node parent){ //1. 删除叶子节点 if(cur.left == null && cur.right == null && parent.left == cur){ parent.left = null; } if(cur.left == null && cur.right == null && parent.right == cur){ parent.right = null; } //2.删除左子树为空的节点 if(cur.left == null){ if(cur == root){ root = root.right; } else if (parent.left == cur) { parent.left = cur.right; }else { parent.right = cur.right; } } //3.删除右子树为空的节点 else if(cur.right == null){ if(cur == root){ root = root.left; } else if (parent.left == cur) { parent.left = cur.left; }else { parent.right = cur.left; } } //4.删除左右子树都不为空的节点 //方法① 找此节点左子树的最大值，进行交换当前节点 //方法② 找此节点右子树的最小值，进行交换当前节点 else { //方法② Node flagParent = cur; Node flag = cur.right;//让flag去找右子树的最小值 //右子树的最小值一定在右子树的最左边 while(flag.left!= null){ flagParent = flag; flag = flag.left; } cur.val = flag.val; if(flag == flagParent.left){ flagParent.left = flag.right; }else { flagParent.right = flag.right; } //方法① // Node flagParent = cur; // Node flag = cur.left;//让flag去找左子树的最大值 // // //左子树的最大值一定在左子树的最右边 // while (flag.right != null){ // flagParent = flag; // flag = flag.right; // } // cur.val = flag.val; // if(flagParent.right == flag){ // flagParent.right = flag.left; // }else { // flagParent.left = flag.left; // } } } }
2. 创建另一个 java 文件，里面放着一个类 Test，用来测试
public class Test { public static void main(String[] args) { SearchTree searchTree = new SearchTree(); int[] arr = {10,6,14,4,8,12,17,3,5,7,9,11,13,15,18,16}; for (int x:arr) { searchTree.insertData(x);//往树中添加数据 } System.out.println("------------ 中序遍历 ------------"); searchTree.inorder(searchTree.root); System.out.println(); System.out.println("------------ 查找 key ------------"); System.out.println(searchTree.search(0)); System.out.println("------------ 删除 key ------------"); searchTree.remove(14); searchTree.inorder(searchTree.root); System.out.println(); searchTree.remove(5); searchTree.inorder(searchTree.root); System.out.println(); searchTree.remove(16); searchTree.inorder(searchTree.root); System.out.println(); } }
输出结果：
三、代码分析
在二叉搜索树中添加数据或查找数据，都较为简单，这都需要按照二叉搜索树的性质来进行操作，( 二叉搜索树的左子树比双亲节点小，右子树的比双亲节点大，这一独特的性质 )，使得增查操作效率较高。
而相对来说，删去元素的代码实现并不简单，考虑的情况有很多种。
- 当前删除的节点为叶子节点
- 当前删除节点的左子树为空
分三种情况，考虑当前删除的节点与其双亲节点的位置 - 当前删除节点的右子树为空
分三种情况，考虑当前删除的节点与其双亲节点的位置 - 当前删除节点的左右子树都不为空
方法① 找此节点左子树的最大值，进行交换当前节点
方法② 找此节点右子树的最小值，进行交换当前节点
四、二叉搜索树的时间复杂度
二叉搜索树的时间复杂度：O(n)
由于最坏情况下二叉搜索树就是一棵单树，即相当于链表结构。
