数据结构基础：Java版手撕BST二叉搜索树（含前序、中序、后序、层序遍历，树的高度计算）

前传

文章中的图形化演示请在下述网址模拟：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

一、BST概述

和链表一样，二叉搜索树也是一种动态数据结构。但其查询效率更高，查询的均摊时间复杂度为O(logn)。

二叉搜索树的特点：

1. 只有一个根节点，每个节点最多有两个孩子节点，每个节点最多只有一个父节点。
2. 二叉搜索树具有天然递归结构。每个节点的左/右子树也是二叉搜索树。
3. 二叉搜索树的每个节点的值大于左子树所有节点的值，小于右子树所有节点的值。
4. 存储的元素必须具有可比性，即实现Comparable接口。
5. 在极端情况BST会变成链表结构。
6. 二分搜索树可以支持重复元素。

二叉搜索树的遍历：

• 前序遍历：跟节点 – 左子节点 – 右子节点
• 中序遍历：左子节点 – 根节点 – 右子节点
  二分搜索树排序过后的结果。
• 后序遍历：左子节点 – 右子节点 --跟节点

我们代码的版本是不允许插入重复元素的。像下图所示，其支持重复插入数据的版本也只是简单的在已存在节点的右子树上创建一个新节点。

删除重复节点是将第一个找到的节点删除。

二、代码实现

1、树通用接口

package com.saint.base.datastructure.tree;

/**
 * 树接口
 *
 * @author Saint
 * @version 1.0
 * @createTime 2021-09-09 8:43
 */
public interface Tree<E> {

    /**
     * 元素个数
     *
     * @return int
     */
    int size();

    /**
     * 添加元素
     *
     * @param e
     */
    void add(E e);

    /**
     * 删除元素
     *
     * @param e
     */
    void remove(E e);

    /**
     * 树中是否包含元素e
     *
     * @param e
     * @return boolean
     */
    boolean contains(E e);

}

2、树节点

package com.saint.base.datastructure.tree;

/**
 * 树节点
 *
 * @author Saint
 * @version 1.0
 * @createTime 2021-09-09 8:43
 */
public class TreeNode<E> {

    /**
     * 用于存放数据
     */
    public E e;

    /**
     * 左子节点
     */
    public TreeNode left;

    /**
     * 右子节点
     */
    public TreeNode right;

    public TreeNode(E e) {
        this.e = e;
        this.left = null;
        this.right = null;
    }
}

3、BST实现

package com.saint.base.datastructure.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二分搜索树
 *
 * @author Saint
 */
public class BSTree<E extends Comparable<E>> implements Tree<E> {

    /**
     * 树容器
     */
    TreeNode<E> root;

    /**
     * 树节点个数
     */
    int size;

    public BSTree() {
        root = null;
        size = 0;
    }

    @Override
    public void add(E e) {
        root = add(root, e);
    }

    /**
     * 往指定树中添加节点
     *
     * @param node
     * @param e
     * @return
     */
    private TreeNode<E> add(TreeNode<E> node, E e) {
        // 如果树节点为null,新建节点
        if (null == node) {
            size++;
            return new TreeNode<>(e);
        }

        // 要添加的数据小于根节点，则插入到node的左子树
        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);
        } else {
            // do nothing, e的值和node.e相等时不做任何操作，这里大家可以自定义操作
        }

        // 递归返回当前跟节点
        return node;
    }

    @Override
    public void remove(E e) {
        root = remove(root, e);
    }

    private TreeNode<E> remove(TreeNode<E> node, E e) {
        if (null == node) {
            throw new RuntimeException("BST is empty!");
        }
        // 如果要删除的节点值比node节点值小
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            // 如果要删除的节点值比node节点值大
            node.right = remove(node.right, e);
            return node;
        } else {
            // 要删除的节点就是当前节点
            // 下面要分三种情况进行考虑：node的左子树为null，node的右子树为null，node的左右子树都不为null。

            // 1）node的左子树为null
            if (node.left == null) {
                TreeNode<E> rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            // 2）node的右子树为null
            if (node.right == null) {
                TreeNode<E> leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            // 3）node的左右子树都不为null

            // 我们的思路是：1.获取node右子树的最小值做为新树的根节点newNode
            // 2.然后将node右子树中的最小值从右子树中删除。
            // 3.然后将node.left 和 node.right(移除最小值之后)的树结构分别挂在newNode的左右子树上。
            TreeNode<E> newNode = minimum(node.right);
            // removeMin()方法里进行了size --
            TreeNode<E> rightNode = removeMin(node.right);
            newNode.left = node.left;
            node.left = null;
            node.right = null;
            newNode.right = rightNode;
            return newNode;
        }
    }

    /**
     * 移除node树中的最小值
     *
     * @param node
     * @return
     */
    public TreeNode<E> removeMin(TreeNode<E> node) {
        if (node.left == null) {
            TreeNode<E> rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        return removeMin(node.left);
    }

    /**
     * 移除node树的最大值
     *
     * @param node
     * @return
     */
    public TreeNode<E> removeMax(TreeNode<E> node) {
        if (null == node.right) {
            TreeNode<E> leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        return removeMax(node.right);
    }


    @Override
    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(TreeNode<E> node, E e) {
        if (null == node) {
            return false;
        }
        if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            return contains(node.right, e);
        }
        return true;
    }

    /**
     * 获取BST树的最大值
     *
     * @return
     */
    public E maximum() {
        if (size == 0) {
            throw new RuntimeException("BST is empty!");
        }
        return maximum(root).e;
    }

    private TreeNode<E> maximum(TreeNode<E> node) {
        if (node.right == null) {
            return node;
        }
        return maximum(node.right);
    }


    /**
     * 获取树的最小值
     *
     * @return
     */
    public E minimum() {
        if (size == 0) {
            throw new RuntimeException("BST is empty!");
        }
        return minimum(root).e;
    }

    private TreeNode<E> minimum(TreeNode<E> node) {
        if (node.left == null) {
            return node;
        }
        return minimum(node.left);
    }

    @Override
    public int size() {
        return size;
    }

    /**
     * 树的高度
     *
     * @return
     */
    public void height() {
        System.out.println("----树的高度----");
        System.out.println("DFS方式：" + getHeightDFS(root));
        System.out.println("BFS方式：" + getHeightBFS(root));
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }

    private void generateBSTString(TreeNode<E> root, int depth, StringBuilder res) {

        if (root == null) {
            return;
        }
        res.append(generateDepthString(depth) + root.e + "\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();
    }

}

4、树的遍历–DFS

树的很多操作都是基于树的遍历。由于树的前序遍历规则是跟左右，所以针对前序遍历我们有两种方式：递归和非递归。而中序遍历、后续遍历则只能递归。

/**
 * BST的前序遍历 -- 跟左右
 */
public void preOrder() {
    System.out.println("递归方式的前序遍历");
    preOrder(root);
    System.out.println();
    System.out.println("非递归方式的前序遍历：");
    preOrderNR(root);
    System.out.println();

}

/**
 * 递归方式的前序遍历
 *
 * @param node
 */
private void preOrder(TreeNode<E> node) {
    if (null == node) {
        return;
    }
    // 此处的输出可以使用业务逻辑替代。
    System.out.print(node.e + " ");
    preOrder(node.left);
    preOrder(node.right);
}

/**
 * 非递归方式的前序遍历
 *
 * @param root
 */
private void preOrderNR(TreeNode<E> root) {
    Stack<TreeNode<E>> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode<E> popNode = stack.pop();

        // 此处的输出可以使用业务逻辑替代。
        System.out.print(popNode.e + " ");

        // 因为栈是先进后出的，而前序遍历是跟左右，所以我们先将当前节点的右子树放进栈。
        if (popNode.right != null) {
            stack.push(popNode.right);
        }
        if (popNode.left != null) {
            stack.push(popNode.left);
        }
    }
}

/**
 * BST的中序遍历 -- 左跟右
 */
public void inOrder() {
    System.out.println("递归方式的中序遍历:");
    inOrder(root);
    System.out.println();

}

/**
 * 递归方式的中序遍历
 *
 * @param node
 */
private void inOrder(TreeNode<E> node) {
    if (null == node) {
        return;
    }
    inOrder(node.left);
    // 此处的输出可以使用业务逻辑替代。
    System.out.print(node.e + " ");
    inOrder(node.right);
}

/**
 * BST的后序遍历 -- 左右根
 */
public void postOrder() {
    System.out.println("递归方式的后序遍历:");
    postOrder(root);
    System.out.println();

}

/**
 * 递归方式的后序遍历
 *
 * @param node
 */
private void postOrder(TreeNode<E> node) {
    if (null == node) {
        return;
    }
    postOrder(node.left);
    postOrder(node.right);
    // 此处的输出可以使用业务逻辑替代。
    System.out.print(node.e + " ");
}

5、树的遍历–BFS

树的前序遍历递归方式实际也可以看做是一种特殊的BFS，
BFS的要旨是一层一层遍历树。

/**
 * 广度遍历
 */
public void levelOrder() {
    System.out.println("广度遍历:");
    Queue<TreeNode<E>> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode<E> cur = queue.remove();
        System.out.print(cur.e + " ");
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
}

6、树的高度

同样的获取树的高度我们可以采用DFS或BFS。DFS只需找到路径最深的一纵节点（从上到下）；BFS是在逐层遍历时，记录下一共有多少层。

DFS：

/**
 * DFS -- 获取树的高度
 *
 * @param node
 * @return
 */
public int getHeightDFS(TreeNode<E> node) {
    if (null == node) {
        return 0;
    }
    return Math.max(getHeightDFS(node.left), getHeightDFS(node.right)) + 1;
}

BFS:

/**
 * BFS -- 获取树的高度
 *
 * @param node
 * @return
 */
public int getHeightBFS(TreeNode<E> node) {
    Queue<TreeNode<E>> queue = new LinkedList<>();
    queue.add(node);

    // 树的高度
    int height = 0;
    // 用于遍历每一层数据的队列
    Queue<TreeNode<E>> temp;
    while (!queue.isEmpty()) {
        temp = new LinkedList<>();
        for (TreeNode<E> cur : queue) {
            if (cur.left != null) {
                temp.add(cur.left);
            }
            if (cur.right != null) {
                temp.add(cur.right);
            }
        }
        height++;
        queue = temp;
    }
    return height;
}

7、测试

package com.saint.base.datastructure.tree;

/**
 * @author Saint
 */
public class BSTreeTest {

    public static void main(String[] args) {
        BSTree<Integer> bsTree = new BSTree<>();
        bsTree.add(4);
        System.out.println("after add, root is : \n" + bsTree.toString());
        System.out.println();
        bsTree.add(2);
        System.out.println("after add, root is : \n" + bsTree.toString());
        System.out.println();
        bsTree.add(6);
        System.out.println("after add, root is : \n" + bsTree.toString());
        System.out.println();
        bsTree.add(1);
        System.out.println("after add, root is : \n" + bsTree.toString());
        System.out.println();
        bsTree.add(3);
        System.out.println("after add, root is : \n" + bsTree.toString());
        System.out.println();
        bsTree.add(5);
        System.out.println("after add, root is : \n" + bsTree.toString());
        System.out.println();
        bsTree.add(7);
        System.out.println("after add, root is : \n" + bsTree.toString());
        System.out.println();
        bsTree.add(8);
        System.out.println("after add, root is : \n" + bsTree.toString());

        // 前序遍历
        bsTree.preOrder();

        // 中序遍历
        bsTree.inOrder();

        // 后序遍历
        bsTree.postOrder();

        // 广度遍历
        bsTree.levelOrder();

        // 树的高度
        bsTree.height();
        
        // 删除一个既有左子树又有右子树的节点
        bsTree.remove(6);
        System.out.println("after remove, root is : \n" + bsTree.toString());

    }
}

此时的树结构为：

1）当我们删除节点006时：
我们的删除节点版本和网站的删除也是不一样的，它是直接把左子树的最大值当做根节点的，而我们是把右子树中的最小值当做根节点。有兴趣的老哥们可以自己实现一把，基础方法我们都已经有了。


另外集中删除方式就咕咕咕了

还是简单说一下吧：

bsTree.remove(1);
// 删除右子树不为null的节点
bsTree.remove(3);

bsTree.remove(1);
// 删除左子树不为null的节点
bsTree.remove(2);

控制台输出：

after add, root is : 
4


after add, root is : 
4
--2


after add, root is : 
4
--2
--6


after add, root is : 
4
--2
----1
--6


after add, root is : 
4
--2
----1
----3
--6


after add, root is : 
4
--2
----1
----3
--6
----5


after add, root is : 
4
--2
----1
----3
--6
----5
----7


after add, root is : 
4
--2
----1
----3
--6
----5
----7
------8

递归方式的前序遍历
4 2 1 3 6 5 7 8 
非递归方式的前序遍历：
4 2 1 3 6 5 7 8 
递归方式的中序遍历:
1 2 3 4 5 6 7 8 
递归方式的后序遍历:
1 3 2 5 8 7 6 4 
广度遍历:
4 2 6 1 3 5 7 8 ----树的高度----
DFS方式：4
BFS方式：4
after remove, root is : 
4
--2
----1
----3
--7
----5
----8

LeetCode中体现

像计算树的高度；数据的DFS、BFS遍历；树的前中后序遍历在leetcode中都有体现：
二叉树的深度
二叉树的中序遍历
二叉树的后序遍历
二叉树的层序遍历

进阶版的大家可以先尝试自己做一下下面三道题：