Java二分搜索树及其添加删除遍历

对于树这种结构，相信大家一定耳熟能详，二叉树、二分搜索树、AVL树、红黑树、线段树、Trie等等，但是对于树的应用以及编写一棵解决特定问题的树，不少同学都会觉得不是一件简单的事情，没关系，我们将一步一步的揭开树的神秘面纱，从这篇博客开始，将会注重每一个步骤的代码细节，不同于前面博客的线性数据结构，比较简单，顺着代码就可以读下来，从这里将会和同学们一起，一步一步的实现不同类型的树结构。

首先，在这篇博客，我们先来看二分搜索树，关于二分搜索树的定义，这里就不再详细赘述，可以简单理解为左子树小于节点值小于右子树，我们这里设计的二分搜索树不包括相同的元素。

既然二分搜索树有着节点比较的定义，那么我们在设计类的时候，需要实现Comparable接口

BST<E extends Comparable<E>>

接着，我们来设计BST内部的Node节点，有了链表的基础，再来看树的节点，就明晰很多了，同样采用的链式结构，不过不同于链表的next，我们这里维护了left和right两个引用

private class Node {
        E e;
        Node left, right;

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

构造方法和获取容量，都是很容易的

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

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

接下来，我们看向二分搜索树中的添加元素的操作，这里我们设计一个public方法，暴露给用户，用户不需要知道我们内部是怎么定义节点，怎么实现添加，然后在写一个私有的方法，向以node为根的人分搜索树中插入元素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;
    }

有了添加操作之后，我们再来设计一个树里是否包含某个元素的操作，同样还是设计一个暴露给用户的公有方法，和内部处理的私有方法，同样使用递归算法。

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);
    }
}

接下来，我们再来封装2个常用的算法，返回给用户二分搜树里的最大值和最小值，由于二分搜索树的性质，最小值我们直接递归去找最左边的那个孩子节点、最大值我们直接递归去找最右边的那个孩子节点就可以了。设计风格还是和以前保持一致，用户调用的公有方法和内部逻辑实现的私有方法，这个系列的博客都会保持这种设计风格，后面将不再赘述。

    
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }
        return minimum(root).e;
    }

   
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }

        return minimum(node.left);
    }

 
    public E maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }
        return maximum(root).e;
    }

  
    private Node maximum(Node node) {
        if (node.right == null) {
            return node;
        }

        return maximum(node.right);
    }

接下来便是删除操作了，删除操作对于树来说，博主认为是最复杂的一个操作了，不过我们慢慢的来一步一步的分解它，我们先来看删除最大值和最小值的操作，在删除最小值的时候，首先我们先往树的最坐节点走，走不动了便对应的是最小值节点，这时候会分为最小值节点有没有右子树的情况，没有右子树时比较简单，直接删除这个节点就可以，如果有右子树，那么便需要先保存右子树的根节点，然后删除最小值节点，在返回保存的右子树节点，便实现了删除最小值的操作，最大值同理，那么我们来看具体的代码实现。

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;
    }

这里私有的removeMin函数表示删除以node为根的二分搜索树的最小节点，返回删除节点后新的二分搜索树的根。这里需要大家对递归算法有着深刻的理解，如果有不熟悉递归算法的同学，建议可以先画一颗简单的二分搜索树，对照代码走一遍逻辑，然后自己动手实现相关逻辑，相信你一定可以掌握。明白删除最小值的方法后，那么接下来删除最大值便是信手拈来了。

public E removeMax() {
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

细心的同学可能会发现，在递归逻辑里，我们并没有对右子树是否为空进行判断，其实这里无论右子树是否为空，逻辑上都是统一的，如果右子树为空，返回的就是空。有了这个基础之后，接下来我们看最复杂的删除任意节点算法。同样，我们还是一步一步的分析，先看简单的情况，如果待删除的节点，左子树为空或者右子树为空，那么删除逻辑和上面的删除最小最大节点的逻辑一致；复杂的情况是，如果待删除的节点即有左子树，也有右子树，那么我们只需要找到右子树的最小节点，用它来代替当前删除的节点即可。同学们可以画一棵二分搜索树来加深理解，接下来我们看代码实现。

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

private Node remove(Node node, E e) {

        if (node == null) {
            return null;
        }

        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 { //e == node.e

            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);
            successor.left = node.left;

            node.left = node.right = null;
            return successor;
        }
    }

这段代码较为复杂，在这里和大家一起分析一下，首先，我们先递归的去找要删除的元素，如果在左边，即e.compileTo(node.e)<0那么我们只需要返回删除了这个元素的左子树，让当前节点的左引用指向已经删除了待元素的左子树，递归函数就是一个功能函数，不过实现一样的功能而已，注重对递归函数的理解！同理，如果在右边，那么只需要将当前节点的右引用指向已经删除了待删除元素的右子树。当找到了待删除元素后，首先我们看左右子树是否为空，如果为空删除起来非常容易，即node.left ==null和node.right==null里的逻辑。难点在待删除元素左右子树都不为空，那么我们先找到右子树的最小节点，即Node successor = minimun(node.right);然后让这个节点的右子树指向删除了以右子树为根的最小值节点的子树，即successor.right = removeMin(node.right);最后，让保存当前节点的左子树不变，即successor.left = node.left;并且将当前节点的左右引用都指向空即可。

相信有同学会发现，既然让右子树的最小节点来代替待删除节点，那么让左子树的最大节点来代替可以吗？答案是可以的，但是在这里，就不为大家展示这种写法了，因为这片博客还要介绍树的遍历写法，现在写到这里已经很长了，都不知道同学们有没有耐心看到这里... 但是希望看到这里的同学，自己去实现让左子树的最大节点来代替待删除元素，是一个很好的练习。

接下来，和大家分享二分搜索树的前中后序遍历写法。首先来看前序：

在这里我们还是使用递归写法。

 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);
    }

private void inOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

后序：

public void postOrder() {
        postOrder(root);
    }

private void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        System.out.println(node.e);
        postOrder(node.right);
    }

有的同学可能会发现，这里通篇采用的都是递归写法，那么树可不可以使用非递归写法呢？答案是可以的，不过非递归写法难度会难于递归写法，不过掌握非递归写法，对同学们的编程思维是很好的提升。

首先我们先来看两个简单的非递归写法，就是上面的寻找最大值节点和最小值节点，由于二分搜索树的性质，最小值节点一定是在最左节点，最大值节点一定是在最右节点，我们只需要一直向左向右找就可以了，是不是很像链表的操作，是的，这里其实就可以理解为一直向左或者向右的链表，我们一起来看代码：

public E minimumNR() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }
        Node cur = root;
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur.e;
    }

public E maximumNR() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }
        Node cur = root;
        while (cur.right != null) {
            cur = cur.right;
        }
        return cur.e;
    }

是不是很清晰，我们循序渐进，来看遍历的非递归写法，这里和大家分享前序遍历和层序遍历的非递归写法，即深度优先和广度优先。

深度优先遍历，我们需要借助栈来帮助我们实现遍历操作，我们首先将根节点入栈，然后循环体展开，只要栈不为空，我们就把栈里的节点出栈，在出栈的同时，判断出栈节点有无左右节点，有的话，按照先右后左的顺序入栈，因为栈是后进先出的数据结构，我们先进右孩子，那么先出来的就是左孩子，符合我们深度优先遍历的思想，接下里我们来看代码：

public void preOrderNR() {
        Stack<Node> stack = new Stack<>();
        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 levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);

            if (cur.left != null) {
                q.add(cur.left);
            }
            if (cur.right != null) {
                q.add(cur.right);
            }
        }
    }

在寻找最左最右节点的时候，会很像链表的操作，这也在一定程度上也反映出了二分搜索树的局限性，即在最差的时候会退化成链表，不过在后面和大家分享的平衡二叉树、红黑树等数据结构中，将会处理这个问题。

到此为止，二分搜索树相关的一些方法，就和大家分享完了，内容比较长信息量也比较大，感谢同学们坚持到这里，其实这也是和普通程序员拉开差距的地方，大家细细体会。上面的代码没有添加注释，是因为在看的时候，希望大家可以注重代码本身的理解，下面会贴出带注释的完整代码供同学们参考。感谢阅读～

还请需要转载的同学注明出处：https://blog.csdn.net/sinat_33150417/article/details/82493335

完整代码：

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

public class BST<E extends Comparable<E>> {

    private int size;
    private Node root;

    private class Node {
        E e;
        Node left, right;

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

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

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    //向二分搜索树中添加新的元素e
    public void add(E e) {
//        if (root == null) {
//            root = new Node(e);
//            size++;
//        } else {
//            add(root, e);
//        }

        root = add(root, e);
    }

    //向以node为根的二分搜索树中插入元素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 {
//            add(node.right, 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;
    }

    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 preOrderNR() {
        Stack<Node> stack = new Stack<>();
        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 levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);

            if (cur.left != null) {
                q.add(cur.left);
            }
            if (cur.right != null) {
                q.add(cur.right);
            }
        }
    }

    // 二分搜索树的前序遍历
    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);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    // 寻找二分搜索树的最小元素(非递归写法)
    public E minimumNR() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }
        Node cur = root;
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur.e;
    }

    // 寻找二分搜索树的最大元素(非递归写法)
    public E maximumNR() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }
        Node cur = root;
        while (cur.right != null) {
            cur = cur.right;
        }
        return cur.e;
    }

    // 寻找二分搜索树的最小元素(递归写法)
    public E minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }
        return minimum(root).e;
    }

    // 返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }

        return minimum(node.left);
    }

    // 寻找二分搜索树的最大元素（递归写法）
    public E maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty");
        }
        return maximum(root).e;
    }

    // 返回以node为根的二分搜索树的最大值所在的节点
    private Node maximum(Node node) {
        if (node.right == null) {
            return node;
        }

        return maximum(node.right);
    }

    public void postOrder() {
        postOrder(root);
    }


    private void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        System.out.println(node.e);
        postOrder(node.right);
    }

    //从二分搜索树中删除最小值所在的节点，返回最小值
    public E removeMin() {
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    //删除以node为根的二分搜索树中的最小节点
    //返回删除节点后新的二分搜索树的根
    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;
    }

    //从二分搜索树中删除最da值所在的节点，返回最大值
    public E removeMax() {
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

    //删除以node为根的二分搜索树中的最大节点
    //返回删除节点后新的二分搜索树的根
    private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

    // 从二分搜索树中删除元素为e的节点
    public void remove(E e) {
        root = remove(root, e);
    }

    //删除以node为根的二分搜索树中值为e节点，递归算法
    //返回删除节点后新的二分搜索树的根
    private Node remove(Node node, E e) {

        if (node == null) {
            return null;
        }

        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 { //e == node.e

            //待删除节点左子树为空
            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);
            successor.left = node.left;

            node.left = node.right = null;
            return successor;
        }
    }

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

    private void generateBSTString(Node node, int depth, StringBuilder res) {
        if (node == null) {
            res.append(generateDepthString(depth) + "null\n");
            return;
        }

        res.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.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();
    }