【数据结构】详解二叉搜索树及其实现

前言：

二叉搜索树是红黑树等的前身，掌握其操作和性质很重要。总结自用and分享。

一、基本概念

二、其常见操作及其实现

1.定义节点

2.查找元素

3.插入元素

4.删除元素【难点】

三、性质分析

一、基本概念

如下所示：对于所有节点都满足该性质：子树上所有节点的值都小于该节点的值。对于每个节点，右子树上所有节点的值都大于该节点的值。每个节点的左子树和右子树也是一个二叉搜索树。

其也叫二叉排序树，对其进行中序遍历可以得到排好序的序列。

二、其常见操作及其实现

1.定义节点

public class BinarySearchTree {private TreeNode root = null;//根节点// 定义节点class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}
}

2.查找元素

思想：

运用一个递归的思想：

1.先看看根节点是不是该元素，是的话，直接当前节点。

2.若不是，判断其位置，若该元素比根大，那就去右子树找（跳到1）。

3.若该元素比根小，那就去左子树找（跳到1）。

4.若遍历完所有节点都找不到，返回null。

代码实现：

public TreeNode search(int val) {TreeNode curRoot = root;//当前的双亲节点while (curRoot != null) {if (curRoot.val == val) {return curRoot;} else if (curRoot.val > val) {curRoot = curRoot.left;} else {curRoot = curRoot.right;}}return null;}

3.插入元素

注意：二叉树的插入是不会破坏原有的结构的，插入元素，总是能找到合适的叶子节点插入，你们可以画图感受一下。

思想：

1.若该树为空，直接插入。

2.若树不为空：根据二叉树的性质，找到它的容身之处的双亲节点。

3.找到双亲节点之后，若比双亲节点大，插入其右边，若比双亲节点小，插入其左边。

代码实现：

    // 2.插入元素public boolean insert(int val) {// 如果根节点为空，直接插入，返回trueif (root == null) {root = new TreeNode(val);return true;}TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (val == cur.val) {System.out.println("值为" + val + "的节点已经存在");return false;} else if (val > cur.val) {parent = cur;cur = cur.right;} else {parent = cur;cur = cur.left;}}// 抵达该位置时，已经找到合适的插入位置的双亲节点：parent// 要判断一下插入哪一边if (val > parent.val) {parent.right = new TreeNode(val);} else {parent.left = new TreeNode(val);}return true;}

4.删除元素【难点】

注意：刚说的插入元素不会破坏原有的树结构，但是删除元素就可能不得不破坏原有的树结构了，毕竟要把某个在中间的元素搬走...

a:初步思路：

先找到该节点和其双亲节点，若找不到该节点，返回false。若找到了该节点，再根据情况进行删除调整。

 public boolean remove(int val) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (cur.val < val) {parent = cur;cur = cur.right;} else if (cur.val > val) {parent = cur;cur = cur.left;} else {//找到要删除的元素和其双亲节点了removeNode(parent, cur);return true;}}System.out.println("删除失败，没找到值为"+val+"的节点");return false;}

b:删除:(难点)

删除叶子节点：直接删除。
删除只有一边子节点的节点：用子节点替代该节点。（可涵盖情况1）
删除有两个子节点的节点【难点所在】：找到该节点的中序后继节点，用它的值替换被删除节点的值，然后删除该中序后继节点，并把该中序后继节点的子节点继承过去。

再捋一下删除的情况：

情况1、2：我们找到了要删除的节点和其双亲节点。上述的情况2是可以包含情况1的：叶子节点也可以视为只有一边子节点（实际是null）的节点，然后子节点（实际是null），替代原本的节点。但是有一种情况我们要特殊处理，那就是要删除的节点是根节点时（此时对parent修改，只是流动了parent，影响不了root），我们需要直接拿到root去修改指向。

情况3： 删除有两个子节点的节点【难点所在】

找到要删除节点的右子树的最左节点，我们因为是最左节点，该节点肯定没有左子树了。

我们把最左节点的值直接覆盖到要删除的节点，原因：最左节点是要删除节点的右子树里最小的，把它放在要删除的节点处，既可以满足，右子树中所有元素比节点大，也可以满足本来左子树中所有元素比节点小。（天然，右子树中任一元素大于左子树中的）

善后阶段：最左节点的值已经被拿去，应该要删掉。这时候就回到情况1、2的问题了，且最左节点肯定不是头结点，处理起来也更简单。

private void removeNode(TreeNode parent, TreeNode cur) {// 情况1：要删除的节点没有左子节点if (cur.left == null) {// 如果要删除的节点是根节点，则直接将根节点指向其右子节点if (cur == root) {root = cur.right;} else if (cur == parent.left) {// 如果要删除的节点是其父节点的左子节点，则更新父节点的左指针parent.left = cur.right;} else {// 如果要删除的节点是其父节点的右子节点，则更新父节点的右指针parent.right = cur.right;}}// 情况2：要删除的节点没有右子节点else if (cur.right == null) {// 如果要删除的节点是根节点，则直接将根节点指向其左子节点if (cur == root) {root = cur.left;} else if (cur == parent.left) {// 如果要删除的节点是其父节点的左子节点，则更新父节点的左指针parent.left = cur.left;} else {// 如果要删除的节点是其父节点的右子节点，则更新父节点的右指针parent.right = cur.left;}}// 情况3：要删除的节点有左右子节点else {// 找到要删除节点的右子树中的最左（最小）节点TreeNode t = cur.right;TreeNode tp = cur;while (t.left != null) {tp = t;t = t.left;}// 将最左节点的值赋值给要删除的节点cur.val = t.val;// 删除最左节点，更新其父节点的左指针或右指针if (tp.left == t) {tp.left = t.right;} else {tp.right = t.right;}}}