玩转数据结构（十三）构建BST

秒速五厘米 2022-05-21 12:27 140阅读 0赞

### 1、二分搜索树简介 ###

![70][]

二分搜索树又称为二叉搜索树、排序二叉树等，是指一棵空树或者具有以下性质的二叉树：

*  若任意一个结点的左子树不为空，则左子树所有结点的值均小于它的根结点的值
 *  若任意一个结点的右子树不为空，则右子树所有结点的值均大于它的根结点的值
 *  任意结点的左右子树分别也为二分搜索树
 *  没有数值相等的结点

二分搜索树是一种基本的数据结构，可以用来构建更为抽象的数据结构，如：set、map等。

二分搜索树和其他数据结构相比较优势在于插入和查找时间复杂度低，为O（logn）。

### 2、二分搜索树的实现 ###

#### 2.1 树结点的定义 ####

注意：BST定义时，泛型需要继承Comparable接口，只有具有可比较性的数据类型，才能构建二分搜索树。

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

在BST定义内部类Node:

private class Node {
            public E e;         //结点存储的数据
            public Node left;   //左孩子
            public Node right;  //右孩子
    
            public Node(E e) {
                this.e = e;
                this.left = null;
                this.right = null;
            }
        }

#### 2.2 初始化BST ####

private Node root;//根结点
        private int size; 
    
        public BST() {//构造方法
            root = null;
            size = 0;
        }

#### 2.3 获取size和判空 ####

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

#### 2.4 向BST中添加结点 ####

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);
            }//这里并没有对值相等进行判断，因为此BST不支持重复元素
    
            return node;
        }

#### 2.5 判断BST中是否包含某个元素 ####

public boolean contains(E e) {
            return contains(root, e);
        }
    
        public 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.6 前序遍历 ####

递归实现：

####  ####

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 preOrderNR() {
            if(size == 0) {
                throw new IllegalArgumentException("BST is empty！");
            }
    
            Stack<Node> stack = new Stack<Node>();
            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);
                }
            }
        }

#### 2.7 中序遍历 ####

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

#### 2.8 后序遍历 ####

public void postOrder() {
            postOrder(root);
        }
    
        //后序遍历--递归算法
        private void postOrder(Node node) {
            if(node == null) {
                return;
            }
    
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.e);
        }

#### 2.9 层序遍历 ####

层序遍历需要借助队列。当遍历时，首先将根结点入队，在访问根结点（根出队）时，要是根结点的左孩子不为空，则将左孩子入队，要是右孩子不为空，则将右孩子入队。要是队列不为空，一直循环此过程。

public void levelOrder() {
            if(size == 0) {
                throw new IllegalArgumentException("BST is empty！");
            }
    
            Queue<Node> q = new ArrayDeque<Node>();
            q.add(root);//入队
    
            while(!q.isEmpty()) {
                Node cur = q.poll();//出队
                System.out.println(cur.e);
    
                if(cur.left != null) {
                    q.add(cur.left);
                }
    
                if(cur.right != null) {
                    q.add(cur.right);
                }
            }
        }

#### 2.10 查找BST中的最小值 ####

public E minimum() {
            return minimum(root).e;
        }
    
        private Node minimum(Node node) {
            if(size == 0) {
                throw new IllegalArgumentException("BST is empty！");
            }
    
            if(node.left == null) {
                return node;
            }
            else {
                return minimum(node.left);
            }
        }

#### 2.11 查找BST中的最大值 ####

public E maximum() {
            return maximum(root).e;
        }
    
        private Node maximum(Node node) {
            if(size == 0) {
                throw new IllegalArgumentException("BST is empty！");
            }
    
            if(node.right == null) {
                return node;
            }
            else {
                return maximum(node.right);
            }
        }

#### 2.12 删除BST中的最小值 ####

public E removeMin() {
            Node res = minimum(root);//找到最小结点返回
            root = removeMin(root);
            return res.e;
        }
    
        //删除以node为根的最小节点
        //返回删除结点后的新的二叉搜索树的根
        private Node removeMin(Node node) {
            //递归结束条件
            if(node.left == null) {
                Node rightNode = node.right;//将最小节点的右子树保存（也许右子树为null）
                node.right = null;
                size--;
                return rightNode;
            }
    
            node.left = removeMin(node.left);
            return node;
        }

#### 2.13 删除BST中的最大值 ####

public E removeMax() {
            Node res = maximum(root);//返回删除的最大结点值
            root = removeMax(root);
            return res.e;
        }
    
        //删除以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;
        }

### 2.14 删除BST中指定元素结点 ###

public void remove(E e) {
            root = remove(root, e);
        }
    
        //删除以node为根中的e结点
        //返回删除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);
            }
    
            else if(e.compareTo(node.e) > 0) {
                node.right = remove(node.right, e);
            }
    
            else {//e == node.e
    
                //待删结点的左子树为null
                if(node.left == null) {
                    Node rightNode = node.right;
                    node.right = null;
                    size--;
                    return rightNode;
                }
    
                //待删结点的右子树为null
                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;
            }
    
            return null;
        }

### 3、测试 ###

public class Main {
        public static void main(String[] args) {
            BST<Integer> bst = new BST<Integer>();
    
            int[] nums = {2, 1, 3, 6, 5};
            for (int num : nums) {
                bst.add(num);
            }
    
            bst.preOrder();
            System.out.println("-------");
            bst.remove(2);
            bst.preOrder();
            System.out.println("size:" + bst.size());
            System.out.println("-------");
            bst.inOrder();
            System.out.println("-------");
            System.out.println("删除：" + bst.removeMax());
            System.out.println("-------");
            bst.inOrder();
        }
    }

结果：

2
    1
    3
    6
    5
    -------
    3
    1
    6
    5
    size:4
    -------
    1
    3
    5
    6
    -------
    删除：6
    -------
    1
    3
    5

### 3、完整代码 ###

import java.util.ArrayDeque;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * 二叉搜索树
     * @param <E>
     */
    public class BST<E extends Comparable<E>> {
    
        /**
         * 树结点的定义
         */
        private class Node {
            public E e;         //结点存储的数据
            public Node left;   //左孩子
            public Node right;  //右孩子
    
            public Node(E e) {
                this.e = e;
                this.left = null;
                this.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;
        }
    
        //向树中添加结点
        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);
        }
    
        public 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 preOrderNR() {
            if(size == 0) {
                throw new IllegalArgumentException("BST is empty！");
            }
    
            Stack<Node> stack = new Stack<Node>();
            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 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);
            postOrder(node.right);
            System.out.println(node.e);
        }
    
        //层序遍历算法
        public void levelOrder() {
            if(size == 0) {
                throw new IllegalArgumentException("BST is empty！");
            }
    
            Queue<Node> q = new ArrayDeque<Node>();
            q.add(root);//入队
    
            while(!q.isEmpty()) {
                Node cur = q.poll();//出队
                System.out.println(cur.e);
    
                if(cur.left != null) {
                    q.add(cur.left);
                }
    
                if(cur.right != null) {
                    q.add(cur.right);
                }
            }
        }
    
        //查找二分搜索树中的最小值
        public E minimum() {
            return minimum(root).e;
        }
    
        private Node minimum(Node node) {
            if(size == 0) {
                throw new IllegalArgumentException("BST is empty！");
            }
    
            if(node.left == null) {
                return node;
            }
            else {
                return minimum(node.left);
            }
        }
    
        //查找二分搜索树中的最大值
        public E maximum() {
            return maximum(root).e;
        }
    
        private Node maximum(Node node) {
            if(size == 0) {
                throw new IllegalArgumentException("BST is empty！");
            }
    
            if(node.right == null) {
                return node;
            }
            else {
                return maximum(node.right);
            }
        }
    
        //删除二分搜索树中的最小结点
        public E removeMin() {
            Node res = minimum(root);//找到最小结点返回
            root = removeMin(root);
            return res.e;
        }
    
        //删除以node为根的最小节点
        //返回删除结点后的新的二叉搜索树的根
        private Node removeMin(Node node) {
            //递归结束条件
            if(node.left == null) {
                Node rightNode = node.right;//将最小节点的右子树保存（也许右子树为null）
                node.right = null;
                size--;
                return rightNode;
            }
    
            node.left = removeMin(node.left);
            return node;
        }
    
        //删除二分搜索树中的最大结点
        public E removeMax() {
            Node res = maximum(root);//返回删除的最大结点值
            root = removeMax(root);
            return res.e;
        }
    
        //删除以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;
        }
    
        //删除二分搜索树中的任意结点
        public void remove(E e) {
            root = remove(root, e);
        }
    
        //删除以node为根中的e结点
        //返回删除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);
            }
    
            else if(e.compareTo(node.e) > 0) {
                node.right = remove(node.right, e);
            }
    
            else {//e == node.e
    
                //待删结点的左子树为null
                if(node.left == null) {
                    Node rightNode = node.right;
                    node.right = null;
                    size--;
                    return rightNode;
                }
    
                //待删结点的右子树为null
                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;
            }
    
            return null;
        }
    }

[70]: /images/20220521/833412c5836141aaa36195fb4407a7ef.png