1 搜索二叉树（BST）

1.1 搜索二叉树的定义

简单来说，它是一个加了限定条件的二叉树，
它可以使最坏情况下的平均搜索的时间复杂度降低到O(log n).

其中的限定条件是：

• 一个节点的左子树只能包含值小于该节点的值的节点
• 一个节点的右子树只能包含值大于该节点的值的节点
• 左右子树也都必须是二叉搜索树

比如我们想向一颗空树中添加下面元素：3,2,1,4,5
最后我们得到的树结构应该如下：

通过限制节点存储值的方式，使得这样的二叉树的搜索效率极高(二分查找),这样的结构查找很快，

但是在试图修改树结构的时候我们也要维护树结构。

在上面的树中删除元素4,我们则需要调整树结构为：

但是真实的情况远比上面的复杂，我们可以分情况来进行讨论：

• 情况1：如果待删除的元素为叶子节点，这个很简单，直接将其父节点的左/右指向null即可

现在需要删除上面树中的2.5这个元素，很简单，我们只需要将2的右孩子节点置空

• 情况2：如果待删除节点有一个孩子节点，这种情况下，只需要将其待删除节点和孩子节点设置为其父亲节点的左/右节点即可
  例如我们要删除下面的树结构中的元素4

我们则可以直接将5设置为3的右孩子

• 情况3：如果待删除节点有两个孩子节点，
  通常的做法是从其左子树中找到最大的元素替代它， 然后删除左子树的那个最大的元素.

现在需要删除元素8，我们可以先将7替换掉8得到：

然后删除5的右节点7，可以知道删除5的右节点7属于情况2，我们直接将5的右节点设置为6即可：

这样就完成了BST的删除操作。

1.2 Java实现二叉搜索树

1.2.1 二叉搜索树节点的要素

节点数据data，左孩子节点引用left，右孩子节点引用right

其节点数据结构为：

public class Node {//用于存储节点数据public Integer data;//左孩子节点引用public Node left;//右孩子节点引用public Node right;public Node(){}public Node(int data){this.data = data;}}

1.2.2 二叉搜索树插入操作实现

class BSTree{/*  插入元素*  基本思想是顺着树往下走，根据规则将其插入合适的位置，*  找个图，对着这个过程走一遍即可理解, 此树很明显不能存储相同值的节点* @param root 根节点* @param data* @return*/Node insert(Node root ,int data) {// 这一步很简单，就是root为空去情况if(root == null) {root = new Node();root.setData(data);} else {if(data < root.getData()){root.setLeft(insert(root.getLeft(),data));} else if(data > root.getData()) {root.setRight(insert(root.getRight(),data));}}return root;}
}

1.2.3 二叉搜索树删除操作实现

注意： 删除操作可能会修改二叉树的整体结构

class BSTree {/* 基本思想是先找到目标节点，* 若此节点的左右孩子都不为空* 找到其左子树的最大值，将其设置为目标节点数据* 后面的递归进行删除原来的那个左子树的最大值操作,* 二叉搜索树的删除操作需要修改树的结构* 若有一个孩子为空则只需将其设置为孩子节点即可* @param root* @param data* @return*/Node delete(Node root,int data) {Node temp;Node find = find(root,data);if(find==null) {System.out.println("没有该元素");}else {Node father = root;Node son = root;//找到待删除节点while (son != null) {if (data == son.getData())break;else if (data > son.getData()) {father = son;son = son.getRight();} else {father = son;son = son.getLeft();}}// oldSon为待删除节点Node oldSon = son;//情况3if(son.getLeft()!=null && son.getRight()!=null) {temp = findMax(son.getLeft());son.setData(temp.getData());son.setLeft(delete(son.getLeft(), son.getData()));}// 情况1,2else {//情况2if(son.getLeft()==null)son = son.getRight();else if(son.getRight()==null)son = son.getLeft();// 情况1else son = null;if(father.getRight()==oldSon){father.setRight(son);}else if(father.getLeft()==oldSon){father.setLeft(son);}}}return root;}
}

1.2.4 二叉搜索树的查找操作

注意： 由于二叉搜索树的存储性质，二叉搜索树的查找操作效率很高，相当于二分查找

class BSTree{/* 返回目标节点* @param root 二叉树根节点* @param data 要寻找的数据* @return 值等于data的节点*/Node find(Node root,int data) {if(root==null) return null;while (root!=null) {if(data==root.getData())return root;else if(data>root.getData())root = root.getRight();else root = root.getLeft();}return null;}
}

1.2.5 获得树的极值

由于二叉搜索树是顺序存储的，所以，我们可以通过方法获取到树的最大值,最小值,

class BSTree{/* 寻找树中最小元素* 基本思想是此树的最小元素一定在最左边* @param root* @return*/Node findMin(Node root) {if(root==null) return null;while(root.getLeft()!=null)root = root.getLeft();return root;}/* 寻找树中最大元素* 基本思想是此树的最大元素一定在最右边* @param root* @return*/Node findMax(Node root) {if(root==null) return null;while(root.getRight()!=null)root = root.getRight();return root;}
}

1.2.6 按大小顺序打印元素

由于二叉搜索树的存储特性, 我们可以用中序遍历获取元素顺序

    /* 树的中序遍历(左根右)* 中序遍历出来的数据是有顺序的* @param root 根节点*/public void middleTraverse(Node root) {if(root!=null) {middleTraverse(root.getLeft());System.out.print(root.getData()+" ");middleTraverse((root.getRight()));}}

1.3 完整代码仓库地址

https://gitee.com/yan-jiadou/algorithm-study/blob/master/algorithmStudy/src/main/java/course/p7_binaryTree/s3_BSTree/BSTreeTest.java