二分搜索树

二分搜索树

本篇文章,主要讲解二分搜索树结构,关于二分搜索树的理论概念,就不在复述因为网上有专业的理论:维基百科:二分查找树,需要熟悉链表的知识:数据结构中的表.
一个二叉树需要每个节点都会存储左右子树的节点和节点的值. 同时左子树一定会小于右子树.新建一个BST类来创建二叉树结构,泛型要继承Comparable 方便进行比较运算.具体代码如下:

public class BST<T extends Comparable<T>>{
//节点类
public static class Node<T> {
        public T value;
        public Node<T> left;
        public Node<T> right;
        public Node(T value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
}
//根节点
private Node<T> root;
//大小
private int size;
public BST() {
   root = null;
   size = 0;
}
public boolean isEmpty() {
    return size == 0;
}
public int size() {
    return size;
}
}

常用操作之一:添加元素

如何添加元素呢? 已知我们需要比较添加的元素,如果小于则添加到左子树,如果大于则添加到右子树.但是我们并不知道二叉树中有多少个子树,所以我们需要遍历所有的子树来进行判断,最好的办法就是使用递归来实现. 我们需要将添加到元素与每个子树的元素进行比较,如果大于则比较右子树如果小于则比较左子树,如果遍历到某个节点为空,则new 节点,将该元素添加到节点中.

注意:写递归要先写终止条件

public void add(T value){
   if(value == null) return;
   //如果根节点为空 则创建根节点
   if(root == null){
      root = new Node(value);
      size++;
   }else{
     add(root,value);
   }
}
private void add(Node<T> node,T value){
    //递归的终止条件 添加的元素重复
    if(value.equals(node.value)) return;
    //如果元素小于节点的值 且节点的左子树为空,则将该元素添加到左子树中
    else if (value.compareTo(node.value) < 0 && node.left == null) {
           node.left = new Node<>(value);
           size++;
            return;
    }
    //如果元素大于的节点的值,且节点的右子树为空,则将该元素添加到右子树中 
    else if (value.compareTo(node.value) > 0 && node.right == null) {
            node.right = new Node<>(value);
            size++;
            return;
    }
    //递归调用
    if(value.compareTo(node.value)<0){//递归左子树
       add(node.left, value);
     }else {//添加的元素大于节点 递归右子树
        add(node.right, value);
     }
}

思考:上述代码是否还可以优化.上述代码 if else太多了,我们可以进行优化,直接判断节点为空则new 节点.优化代码如下:

public void add(T value) {
        root = add(root, value);
    }
private Node<T> add(Node<T> node, T value) {
        if (node == null) {
            size++;
            return new Node<>(value);
        }
        if (value.compareTo(node.value) < 0) {
            node.left = add(node.left, value);
        } else if (value.compareTo(node.value) > 0) {
            node.right = add(node.right, value);
        }
        return node;
    }

测试添加元素的方法是否成立,覆写toString来打印出一个二叉树

@Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }
    //生成以root 为跟节点，深入为depth的描述二叉树的字符串
    private void generateBSTString(Node<T> root, int depth, StringBuilder res) {
        if (root == null) {
            res.append(generateDepthString(depth) + "null\n");
            return;
        }
        res.append(generateDepthString(depth) + root.value + "\n");
        generateBSTString(root.left, depth + 1, res);
        generateBSTString(root.right, depth + 1, res);
    }
    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("--");
        }
        return res.toString();
    }

测试用例如下:

BST<Integer> bst = new BST<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            bst.add(num);
        }
System.out.println(bst);

打印结果如下:

//      5
        //     / \
        //    3   6
        //   / \   \
        //  2   4   8
5
--3
----2
------null
------null
----4
------null
------null
--6
----null
----8
------null
------null

上述打印结构很直观的返回给我们,添加元素的方法成立的. 我们还可以更直观的来输出二叉树那就是二叉树的遍历.

前序遍历

什么是二叉树的前序遍历? 我通过下面的图来演示

//      5
        //     / \
        //    3   6
        //   / \   \
        //  2   4   8
我们可以把每个节点看成三个部分:值 左子树 右子树. 前序遍历的允许就是遍历每个节点的:值 -> 左子树 -> 右子树
我们看上图的二叉树:先遍历值5输出,然后遍历左子树.左子树节点先遍历值3,然后遍历左子树.左子树线遍历值2,然后遍历左子树,左子树为空,然后遍历右子树,右子树为空然后遍历节点3的右子树.右子树节点4,先遍历值4输出,然后遍历左子树为空,遍历右子树为空.这时候节点3已经遍历完毕.然后遍历节点5的右子树.节点6先遍历值6输出,然后遍历左子树为空,遍历右子树8节点,节点6遍历完成,先遍历值8输出,左子树和右子树为空.到此整个二叉树前序遍历完成.
遍历的结果:5 3 2 4 6 8

如何代码实现前序遍历呢? 其实很简单我们可以通过递归就可以实现.先输出值然后递归左子树,然后递归右子树.代码如下,递归可以更能让我们理解思路.

//前序遍历
    public void preOrder() {
        preOrder(root);
    }
    //前序遍历递归实现
    private void preOrder(Node<T> node) {
        if (node == null)
            return;
        System.out.println("node = [" + node.value + "]");
        preOrder(node.left);//遍历左子树 不为空就会一直遍历
        preOrder(node.right);//遍历右子树 不为空就会一直遍历
    }

进阶: 如何非递归的实现前序遍历.
我们都知道栈结构,把根节点放入栈中,while循环所有节点.先取出根节点,然后压入右子树和左子树.栈是先入后出结构.这样我们就会先取出左子树节点,然后压入左子树节点的右子树. 这样我们就能然着前序遍历的顺序取出:值 -> 左子树 -> 右子树.
这样的实现就是,深度优先遍历就是栈结构.
来看下图:

//      5
        //     / \
        //    3   6
        //   / \   \
        //  2   4   8
初始化栈:先将节点5压入栈中.
|  |
|  |
|  |
|5 |
|__|
取出节点5,压入右子树和左子树:
|  |  5
|  |
|3 |
|6 |
|__|
取出节点3,压入右子树和左子树:
|  |  5 3
|2 |
|4 |
|6 |
|__|
取出节点2,左子树和右子树为空不用压入栈:
|  |  5 3 2
|  |
|4 |
|6 |
|__|
取出节点4,左子树和右子树为空不用压入栈:
|  |  5 3 2 4
|  |
|  |
|6 |
|__|
取出节点6,左子树为空不用压入栈 右子树不为空压入栈:
|  |  5 3 2 4 6
|  |
|  |
|8 |
|__|
取出节点8,左子树和右子树为空,最终栈中没有数据,整个树遍历完成:
|  |  5 3 2 4 6 8
|  |
|  |
|  |
|__|

代码实现如下:
代码的逻辑很简单,取出栈顶元素输出,先压入右子树,再压入左子树

//前序遍历非递归实现 通过栈结构深度优先遍历
    public void preOrderNR() {
        if (root != null) {
            //新建一个栈
            Stack<Node<T>> stack = new Stack<>();
            stack.push(root);
            //遍历栈 直到栈元素为空为止
            while (!stack.empty()) {
                //取出栈顶元素 然后判断该元素是否有左子树或者右子树
                Node<T> cur = stack.pop();
                System.out.println(cur.value);
                //先压入右子树
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                //再压入左子树
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
    }

进阶: 既然栈结构能够显示二叉树的深度优先遍历,那么和栈结构差不多的队列结构能否实现呢? 答案是肯定的. 那就是广度优先遍历.只不过广度优先遍历不是二叉树的前序遍历.

先回忆一下队列的结构:先入先出. 继续通过画图来思考,

//      5
        //     / \
        //    3   6
        //   / \   \
        //  2   4   8
初始化队列:先将节点5添加到队列中.
| 5|
|  |
|  |
|  |
|  |
| 3| 5
| 6|
|  |
|  |
|  |
| 6| 5 3
| 2|
| 4|
|  |
|  |
| 2| 5 3 6
| 4|
| 8|
|  |
|  |
| 4| 5 3 6 2
| 8|
|  |
|  |
|  |
| 8| 5 3 6 2 4
|  |
|  |
|  |
|  |
|  | 5 3 6 2 4 8
|  |
|  |
|  |
|  |

代码实现如下:

//广度优先遍历又叫做层序遍历
    public void lastOrder() {
        Queue<Node<T>> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node<T> cur = q.remove();
            System.out.println(cur.value);
            if (cur.left != null) {
                q.add(cur.left);
            }
            if (cur.right != null) {
                q.add(cur.right);
            }
        }
    }

中序遍历

中序遍历顺序:左子树 -> 值 -> 右子树.实现很简单这里就不再详细讲解了,只要读懂了前序遍历其他遍历的实现都是一样的原理.
代码如下:

//中序遍历 二分搜索树排序的结果 是顺序排列的
    public void inOrder() {
        inOrder(root);
    }
    private void inOrder(Node<T> node) {
        if (node == null)
            return;
        inOrder(node.left);
        System.out.println("node = [" + node.value + "]");
        inOrder(node.right);
    }

//      5
        //     / \
        //    3   6
        //   / \   \
        //  2   4   8
中序遍历:2 3 4 5 6 8

后序遍历

后序遍历:左子树 -> 右子树 -> 值

//后序遍历
    public void postOrder() {
        postOrder(root);
    }
    private void postOrder(Node<T> node) {
        if (node == null)
            return;
        postOrder(node.left);
        postOrder(node.right);
        //遍历完左右节点才会进行操作
        System.out.println("node = [" + node.value + "]");
    }

//      5
        //     / \
        //    3   6
        //   / \   \
        //  2   4   8
后序遍历:2 4 3 8 6 5

查找最小节点和最大节点

查找最小节点和最大节点很简单,最小节点就是一直遍历左子树,最大节点就是一直遍历右子树.

//查找最小节点 一直查找左子树
    public T minimum() {
        if (size == 0)
            throw new IllegalArgumentException("BST is empty");
        return minimum(root).value;
    }
    private Node<T> minimum(Node<T> node) {
        if (node.left == null)
            return node;
        return minimum(node.left);
    }
    //查找二分搜索树最大节点 一直查找右子树
    public T maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }
        return maximum(root).value;
    }
    private Node<T> maximum(Node<T> node) {
        if (node.right == null) {
            return node;
        }
        return maximum(node.right);
    }

删除最小节点和最大节点

删除最小节点:要删除最小节点,我们需要找到最小节点,上述我们已经实现了查找最小节点的方法minimum.然后我们需要保存最小节点的右子树,然后将右子树赋给最小节点的父节点的左子树节点.

//      5
        //     / \
        //    3   6
        //   / \   \
        //  2   4   8

代码如下:

//删除二分搜索树最小节点
    public T removeMin() {
        //找到最小值
        T minimum = minimum();
        //删除最小值
        root = removeMin(root);
        return minimum;
    }
    private Node<T> removeMin(Node<T> node) {
        //先写递归的终止条件
        //如果递归的节点的左子树为null那么就查找到最小的节点
        if (node.left == null) {
            //保存右子树
            Node<T> rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        //然后将最小的节点进行赋值
        node.left = removeMin(node.left);
        return node;
    }

删除最大节点如下:

//删除二分搜索树中最大的节点
    public T removeMax() {
        T max = maximum();
        root = removeMax(root);
        return max;
    }
    private Node<T> removeMax(Node<T> node) {
        if (node.right == null) {
            Node<T> leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

删除任意一个元素

首先,我们需要找到要删除元素的节点,然后判断删除的节点是否有左子树和右子树,如果要删除的节点只有左子树或者右子树,则将子树赋给要删除的节点.如果要删除的节点左右子树都存在,我们可以找到该节点左子树的最大节点替换删除的节点或者找到删除节点右子树的最小节点替换删除的节点. 我们可以使用上述代码的删除最小节点和最大节点操作

//      5
        //     / \
        //    3   6
        //   / \   \
        //  2   4   8

代码如下:

private Node<T> remove(Node<T> node, T e) {
        if (node == null)
            return null;
        //查找节点
        //如果查找的节点大于当前的节点值 则查找当前节点的右子树
        if (e.compareTo(node.value) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else if (e.compareTo(node.value) < 0) {//小于 查找左子树
            node.left = remove(node.left, e);
            return node;
        } else {//e == root.node
            //要删除的节点只有右子树
            if (node.left == null) {
                return moveRight((Node<T>) node);
            }
            //要删除的节点只有左子树
            if (node.right == null) {
                return moveLeft((Node<T>) node);
            }
            //左右子树都存在的情况
            //后继方式 找到该节点右子树最小的节点
//            Node<T> s = minimum(node.right);
//
//            //将s节点从删除节点的右子树中移除,然后将s节点指向右子树指向删除节点的右子树
//            s.right = removeMin(node.right);//removeMin中已经将size-1了
//            //s节点的左子树=删除节点的左子树
//            s.left = node.left;
//            //前驱方式 找到该节点左子树最大的节点
            Node<T> p = maximum(node.left);
            //先将p节点移除在做其他操作
            p.left = removeMax(node.left);
            p.right = node.right;
            //将删除节点置空
            node.right = null;
            node.left = null;
            return p;
        }
    }
 private Node<T> moveLeft(Node<T> node) {
        Node<T> leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
    }
    private Node<T> moveRight(Node<T> node) {
        Node<T> rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
    }

OK,至此我们了解了二分搜索树的基本结构实现,二叉树的探索绝对不止这些,大家可以试着实现中序遍历和后序遍历的非递归实现以及leetcode的练习.

我会尽量已清晰的方式来讲解复杂的算法.