数据结构学习笔记：二分搜索树
目录：
1.二分搜索树定义
2.添加数据（递归 / 非递归）
3.查询数据（递归）
4.前序、中序、后序遍历（递归 / 非递归）
5.层序遍历
6.查找最值（递归 / 非递归）
7.删除数据
8.寻找BTS的front和ceil
在说二分搜索树（Binary Search Tree）之前，我们来介绍一下二叉树。
所谓二叉树，就是每个节点最多含有两个子树的树。二叉树，具有唯一的根节点（root），而二叉树的左节点和右节点，可以为空，我们分别称左右节点为左孩子和右孩子。如果一个节点的左孩子和右孩子都不存在，我们就叫它为叶子节点。下图中13、22、29、42就为叶子节点。二叉树和链表一样，都是动态数据结构。
一颗二叉树
二叉树的不一定是满的，下图也是一颗二叉树。
又一棵二叉树
二叉树从根开始，每一个节点又可以分出一颗小的二叉树。即使是叶子结点，它也是一颗二叉树，虽然它的左孩子和右孩子都为 NULL （空值也是二叉树）。
说完了二叉树的概念，我们就来介绍二分搜索树。
对于二分搜索树的每一个节点的值，他的左子树所有的值一定比这个节点的值小，右子树所有的值一定比这个节点的值大。二分搜索树的每一颗子树，都是一颗二分搜索树。我们可以看到第一张图，那就是一颗二分搜索树。
我们在树状数据结构中存储的元素，必须具有可比较性。
下面我们利用 Java 语言来简单实现一个树结构。
我们知道，在二叉树中，一个个数据就是一个个节点。在新建的类中，还要为一个节点创建左右两个左右孩子节点。
public class BST<E extends Comparable<E>> { //使我们新建的类支持泛型，而这个泛型变量应具有可比较性
private class Node{
public E e;
public Node left, right;
public Node(E e){
this.e = e;
left = null;
right = null;
}
}
private Node root; //根节点
private int size; //存储数据数量
public BST(){ //初始化二分搜索树
root = null;
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
这样一个简单的二分搜索树就完成了。下面我们将探索在二分搜索树中的基本操作。
对于二叉树而言，其结构是个天然的递归结构。在二分搜索树中使用递归实现基本操作，可以大大简化代码量。在这里，我将介绍递归和非递归两种方法来实现基本操作。
首先，我们来看看如何实现添加数据操作。
在二分搜索树中，我们要判断添加的数据和当前节点的值的大小。如果比当前节点值小，则进入左孩子节点进行下一轮判断，反之则进入右孩子节点判断。在本文中，我们不考虑重复元素的情况。
说到这里，你应该想到利用递归来实现了。在这里我做一个小提醒，由于我们用的数据类型不属于 Java 的基础数据类型，所以不能用大于小于号来比较数据大小。我们之前定义的元素 E 类型是满足 Comparable 的，所以我们应该使用 compareTo() 方法进行比较。其用法如下：
compareTo() 方法用于将 Number 对象与方法的参数进行比较。可用于比较 Byte, Long, Integer等。
该方法用于两个相同数据类型的比较，两个不同类型的数据不能用此方法来比较。
如果指定的数与参数相等返回0。
如果指定的数小于参数返回 -1。
如果指定的数大于参数返回 1。
完成了知识储备，接下来我们来用代码实现。
我们的递归从根节点开始进行递归，由于采用递归方法，我们需要构造两个方法。
public void add(E e){
//从根节点开始进行递归
if(root == null){
root = new Node(e);
size ++;
}else{
add(root, e);
}
}
private void add(Node node, E e){
if(e.equals(node.e))
return;
else if(e.compareTo(node.e) < 0 && node.left == null){ //如果待添加元素数据比节点小，且左孩子为空，则直接将该节点的左孩子设为此元素
node.left = new Node(e);
size ++;
return;
}
else if(e.compareTo(node.e) > 0 && node.right == null){
node.right = new Node(e);
size ++;
return;
}
//如果不满足上述要求，则进入下一轮递归
if(e.compareTo(node.e) < 0)
add(node.left, e);
else //e.compareTo(node.e) > 0
add(node.right, e);
}
实际上，我们只要判断该节点的左右孩子是否为空就可以添加。
我们改写一下代码，直接返回根节点即可。
public void add(E e){
root = add(root, e);
}
private Node add(Node node, E e){
if(node == null){
size ++;
return new Node(e);
}
if(e.compareTo(node.e) < 0)
node.left = add(node.left, e);
else if(e.compareTo(node.e) > 0)
node.right = add(node.right, e);
return node;
}
利用非递归方法也同理，检测到节点为空就可以添加。但由于我们需要连接节点，我们需要利用一个变量存储父节点，然后再将子节点用父节点的left或right节点表示出来。最后在连接起来。（prev.left=cur;）
public void add(E e) {
if (root == null){
root = new Node(e);
}else{
Node cur = root;
Node prev = root;
while (cur != null) {
if (e.compareTo(cur.e) < 0) {
prev=cur;
cur = cur.left;
if (cur == null) {
cur = new Node(e);
prev.left=cur;
break;
}
}else if (e.compareTo(cur.e) > 0) {
prev=cur;
cur = cur.right;
if (cur == null) {
cur = new Node(e);
prev.right=cur;
break;
}
}else{
return;
}
}
}
size++;
}
写完了添加语句，查询某元素是否存在应该很简单了，我们使用递归来实现。
首先从根节点开始找起，依然是构造两个函数。
public boolean contains(E e){
return contains(root, e);
}
private boolean contains(Node node, E e){
if(node == null)
return false;
if(e.compareTo(node.e) == 0)
return true;
else if(e.compareTo(node.e) < 0)
return contains(node.left, e);
else // e.compareTo(node.e) > 0
return contains(node.right, e);
}
接下来，我们来谈谈二分搜索树的遍历操作。
所谓遍历，就是把各个节点的值全部遍历一遍。在线性结构下，我们遍历数据十分容易。在二分搜索树中，也十分容易。我们知道一颗二分搜索树有两个子节点和自己。我们可以先从左子树开始遍历，遍历完后再查询自己，之后再进行右子树的遍历。这就叫做二分搜索树的中序遍历。那么前序遍历和后序遍历就是左中右三颗子树的顺序不同而命名的。
与上文一样，我们使用递归来实现前序遍历。
public void preOrder(){
preOrder(root);
}
private void preOrder(Node node){
if(node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
中序遍历逻辑很简单，我们可以从结果看到，中序遍历的遍历结果是从小到大排列的。
public void inOrder(){
inOrder(root);
}
// 中序遍历以node为根的二分搜索树, 递归算法
private void inOrder(Node node){
if(node == null)
return;
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
后续遍历（左右中）在此不再赘述。
当然，我们可以利用非递归方法实现遍历。
由于二分搜索树有两个节点，而节点又可以分出多个子节点，那我们怎么记录当前访问到拿个节点了呢？在这里，我们可以运用栈（Stack）来实现。
前序遍历比较简单，我们首先将root压入栈，也就是图中的28。
开始进入循环，我们首先将栈顶的28拿出，接下来将28的右孩子先压入栈，再将左孩子压入，因为栈是后入先出的。于是进行下一轮循环，将16拿出，然后将其右孩子先入栈，左孩子后入栈，如此往复，直到栈内无元素即完成遍历。
public void preOrderNR(){
Stack<Node> stack = new Stack<Node>();
if(root != null)
stack.push(root);
while(!stack.isEmpty()){
Node cur = stack.pop();
System.out.println(cur.e);
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
}
}
然而到了中序遍历，便稍微有点难度了。
我们知道中序遍历是先看左节点，再看自己，最后看右节点。那我们就需要循环到根节点的最深层左节点为止，然后一层层上来，最后再进行右节点的循环。
public void inOrderNR() {
Stack<Node> stack = new Stack<Node>();
Node cur = root;
while (!stack.isEmpty() || cur != null) {
while (cur != null) { //遍历到最深层的左孩子
stack.push(cur);
cur = cur.left;
}
Node prev = stack.pop();
System.out.println(prev.e);
cur = prev.right;
}
}
同样以下图数据为例。
1.找到最深层的左孩子13，此时栈内情况 Bottom [13,16,28] Top，cur=13所在节点
之后将13出栈，输出13，cur为13的右孩子，进入下一层循环，此时栈内情况 Bottom [16,28] Top;
2.由于13没有右孩子，故第二层循环不执行。此时prev等于栈顶元素16，此时栈内情况 Bottom [16,28] Top，输出16，cu等于16的右孩子22；
3.进入第二层循环，22入栈，cur等于22的左孩子，此时栈内情况 Bottom [22,28] Top。prev=22,22出栈并输出，此时cur等于22的右孩子。
4.由于22没有右孩子，故第二层循环不执行。prev=28，28出栈并输出。此时cur等于28的右孩子30.
……
最后我们来看后序遍历（我写这个代码的时候被中间的死循环卡住了）。我们在后续遍历时需找到最深层元素（即叶子节点），由于从深层向上进行遍历，我们还要多加一个变量记录上一层节点，当其所指向的节点的左子树和右子树均被访问过，则将该节点从栈中弹出。
public void postOrderNR(){
Stack<Node> stack = new Stack<Node>();
if(root != null)
stack.push(root);
Node prev = stack.peek();
while(!stack.isEmpty()){
Node cur = stack.peek();
while((cur.left != null || cur.right != null) && prev != cur.left && prev != cur.right){
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
cur=stack.peek();
}
cur=stack.pop();
System.out.println(cur.e);
prev=cur;
}
}
讲完了二分搜索树遍历，我们来学习层序遍历。
所谓层序遍历，就是按层进行遍历。如上图，先遍历第一层28，之后再是第二层16、30，最后到第三层。对于层序遍历，我们采取的是先进先出的队列（Queue）数据结构。
public void levelOrder(){
if(root == null)
return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
Node cur = queue.remove();
System.out.println(cur.e);
if(cur.left != null)
queue.add(cur.left);
if(cur.right != null)
queue.add(cur.right);
}
}
关于BTS的最值问题，我们知道，一棵树最深层的左节点就是最小值，最大值就是最深层的右节点。
最小值递归实现：
public E minimum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty");
Node minNode = minimum(root);
return minNode.e;
}
// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node){
if( node.left == null )
return node;
return minimum(node.left);
}
非递归实现：
public E minimum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty");
E min=root.e;
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
Node cur= stack.pop();
min=cur.e;
if (cur.left != null)
stack.push(cur.left);
}
return min;
}
接下来我们来探索如何删除BTS的最值元素。
以最小值为例，当删除叶子结点时，我们直接删除即可。
当删除非叶子节点时，将其删除，再将其子节点接上来即可。
当最左边的元素没有子节点时，我们就可以判定其为最小值。我们将最小值节点的右孩子返回给上一层元素。例如删除图2的22时，我们将22的右节点返回给上一层节点的左节点，即41的左孩子为33。
public E removeMin(){
E ret = minimum();
root = removeMin(root);
return ret;
}
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
我们再来探索如何删除任意值。
要删除58这种左右都有节点的元素，我们要找到它的继承者，即他右节点中最小的元素，也是和58最相近的元素，然后将其在原位置删除，代替58成为父节点。
我们有三种情况，当前节点比待删除大、小、相等的情况。前两种情况是继续进行下一层的递归。当相等时，我们又有三种情况：待删除节点的左子树为空、待删除节点的右子树为空、待删除节点的左右子树都不为空。前两种情况比较好处理，直接把子节点接上即可。第三种情况，我们需要找到他的继承者，即利用之前写的minimum函数找到该节点右子树的最小值，进行上面所讲述的步骤进行连接即可。
public void remove(E e){
root=remove(root,e);
}
public Node remove(Node node,E e){
if (node==null)
return node;
if(e.compareTo(node.e)<0){
node.left=remove(node.left,e);
return node;
}else if(e.compareTo(node.e)>0){
node.right=remove(node.right,e);
return node;
}else{
if (node.left==null){
Node rightNode=node.right;
node.right=null;
size--;
return rightNode;
}
if (node.right==null){
Node leftNode=node.left;
node.left=null;
size--;
return leftNode;
}
Node successor=minimum(node.right);
successor.right = removeMin(node.right); //size--,此时node还未被删除
successor.left = node.left;
node.left = node.right=null;//此时node被删除
return successor;
}
}
来看看如何寻找二分搜索树的front和ceil。所谓front和ceil，就是给定一个数，这个数不一定存在在BTS中，front就是比这个数小的最大的元素，ceil就是比这个大的最小的元素。在下图中，45的floor就是42，ceil就是50。
我们需要一层一层进行对比。当45输入时，我们应该判断他和根元素的大小关系。他比41大，所以我们应该进入右子树进行对比，也就是58。58又比41大。所以我们应该进入58的左子树50。50又比45大，所以进入左子树。由于42比45小，而42没有子树，所以42就是front。而50肯定是比45大的最小的元素，所以ceil就是50。
我们同样适用递归来实现。
public E floor(E e) {
Node minNode = floor(root, e);
return minNode == null ? null : minNode.e;
}
private Node floor(Node node, E e) {
if (node == null)
return null;
if (e.compareTo(node.e) == 0)
return node;
if (e.compareTo(node.e) < 0)
return floor(node.left, e);
Node rightNode = floor(node.right, e);//当前节点值小于输入值
if (rightNode != null)//查看当前节点的右节点是否为空，为空则为front，不为空查询其右子树
return rightNode;
else
return node;
}
文章写了三个晚上...就先这样吧，之后想到再补充，希望能给你带来帮助。：）
