java实现数据结构05（二分搜索树详解代码之自定义二分搜索树）

た入场券 2023-06-22 14:55 10阅读 0赞

## 此处的层级排序需要用到循环队列，可参考[java实现数据结构03.02（队列详解代码之循环队列）][java_03.02] ##

自定义二分搜索树

/**
     * @description: 二分搜索树
     * @author: liangrui
     * @create: 2019-12-16 17:24
     **/
    public class BinarySearchTree<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 BinarySearchTree(){
            //初始树为空
            root=null;
            size=0;
        }
    
        /**
         * 查询树元素个数
         * @return 元素个数
         */
        public int getSize(){
            return size;
        }
    
        /**
         * 判断树是否为空
         * @return 为空返回true,不为空返回false
         */
        public boolean isEmpty(){
            return size==0;
        }
    
    
        /**
         * 递归添加元素
         * @param node 根节点
         * @param e 添加的元素
         * @return 返回根节点
         */
        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);
            }
            //如果添加的元素比节点元素大，则向右递归
            if(e.compareTo(node.e)>0){
                node.right=add(node.right,e);
            }
            return node;
        }
    
        /**
         * 给树添加元素
         * @param e 添加的元素
         */
        public void add(E e){
            root=add(root,e);
        }
    
        /**
         * 递归查询元素是否存在
         * @param node 比较的节点
         * @param e 查询的元素
         * @return 存在返回true，不存在返回false
         */
        private boolean contains(Node node,E e){
            if (node==null){
                return false;
            }else if (e.compareTo(node.e)==0){
                return true;
            }else if (e.compareTo(node.e)<0){
                return contains(node.left,e);
            }else {
                return contains(node.right,e);
            }
        }
    
        /**
         * 查询指定元素是否存在
         * @param e 指定查询的元素
         * @return 存在返回true，不存在返回false
         */
        public boolean contains(E e){
            return contains(root,e);
        }
    
        /**
         * 前序遍历:根->左->右
         * @param node 节点
         */
        private void preOrder(Node node){
            if (node==null){
                return;
            }
            System.out.println(node.e);
            preOrder(node.left);
            preOrder(node.right);
        }
    
        /**
         * 前序遍历
         */
        public void preOrder(){
            preOrder(root);
        }
    
        /**
         * 中序遍历：左->根->右
         * @param node 节点
         */
        private void inOrder(Node node){
            if (node==null){
                return;
            }
            inOrder(node.left);
            System.out.println(node.e);
            inOrder(node.right);
        }
    
        /**
         * 中序遍历，就是把元素从小到大排序
         */
        public void inOrder(){
            inOrder(root);
        }
    
        /**
         * 层序遍历:一层一层遍历输出，1->2->3
         * 1            *
         * 2          *   *
         * 3         * * * *
         */
        public void levelOrder(){
            Queue<Node> queue=new LoopQueue<>();
            queue.enqueue(root);
            while (!queue.isEmpty()){
                Node cur = queue.dequeue();
                System.out.println(cur.e);
                if (cur.left!=null){
                    queue.enqueue(cur.left);
                }
                if (cur.right!=null){
                    queue.enqueue(cur.right);
                }
            }
        }
    
        /**
         * 前序遍历输出树形图
         * @return
         */
        @Override
        public String toString() {
            StringBuilder res=new StringBuilder();
            generateBSTString(root,0,res);
            return res.toString();
        }
    
        /**
         * 创建深度树形图
         * @param node 节点
         * @param depth 深度
         * @param res 创建的字符串树形图
         */
        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);
        }
    
        /**
         * 创建深度
         * @param depth 深度
         * @return 返回深度字符串
         */
        private String generateDepthString(int depth){
            StringBuilder res=new StringBuilder();
            for (int i = 0; i < depth; i++) {
                res.append("--");
            }
            return res.toString();
        }
    
        /**
         * 获取树中最大的元素
         * @return 返回最大的元素
         */
        public E getMax(){
            if (size==0){
                throw new IllegalArgumentException("BinarySearchTree is empty.");
            }
            return getMax(root).e;
        }
    
        /**
         * 递归获取最大元素
         * @param node 节点
         * @return 返回最大元素
         */
        private Node getMax(Node node){
            if (node.right==null){
                return node;
            }else {
                return getMax(node.right);
            }
        }
    
        /**
         * 获取树中最小的元素
         * @return 返回最小的元素
         */
        public E getMin(){
            if (size==0){
                throw new IllegalArgumentException("BinarySearchTree is empty.");
            }
            return getMin(root).e;
        }
    
        /**
         * 递归获取最小元素
         * @param node 节点
         * @return 返回最小元素
         */
        private Node getMin(Node node){
            if (node.left==null){
                return node;
            }else {
                return getMin(node.left);
            }
        }
    
        /**
         * 删除最大元素
         * @return 返回删除的元素
         */
        public E removeMax(){
            Node maxNode=getMax(root);
            root=removeMax(root);
            return maxNode.e;
        }
    
        /**
         * 递归删除最大元素
         * @param node 节点
         * @return 返回新的树
         */
        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;
        }
    
        /**
         * 删除最小元素
         * @return 返回删除的元素
         */
        public E removeMin(){
            Node minNode=getMin(root);
            root=removeMin(root);
            return minNode.e;
        }
    
        /**
         * 递归删除最小元素
         * @param node 节点
         * @return 返回新的树
         */
        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;
        }
    
        /**
         * 删除指定元素节点
         * @param node 节点
         * @param e 元素
         * @return 返回删除后的节点
         */
        public 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 {
                //如果被删除节点的左节点为空
                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 reNode=getMin(node.right);
                reNode.right=removeMin(node.right);
                reNode.left=node.left;
                node.left=node.right=null;
    
                return reNode;
            }
        }
    
        public void remove(E e){
            root=remove(root,e);
        }
    
    }

main测试：

public class Main {
    
        public static void main(String[] args) {
           BinarySearchTree<Integer> binarySearchTree=new BinarySearchTree();
           int[] arr={5,3,6,8,4,2};
    
           //添加元素
            for (int i : arr) {
                binarySearchTree.add(i);
            }
            //前序遍历
            System.out.println("前序遍历:");
            binarySearchTree.preOrder();
            //中序遍历
            System.out.println("中序遍历:");
            binarySearchTree.inOrder();
            //层序遍历
            System.out.println("层序遍历:");
            binarySearchTree.levelOrder();
    
            System.out.println("删除前的树：");
            System.out.println(binarySearchTree);
            binarySearchTree.removeMax();
            binarySearchTree.removeMin();
            binarySearchTree.remove(4);
            System.out.println("删除后的树：");
            System.out.println(binarySearchTree);
    
        }
    }

测试结果：

> 前序遍历:  
> 5  
> 3  
> 2  
> 4  
> 6  
> 8  
> 中序遍历:  
> 2  
> 3  
> 4  
> 5  
> 6  
> 8  
> 层序遍历:  
> 5  
> 3  
> 6  
> 2  
> 4  
> 8  
> 删除前的树：  
> 5  
> –3  
> \----2  
> \------null  
> \------null  
> \----4  
> \------null  
> \------null  
> –6  
> \----null  
> \----8  
> \------null  
> \------null  
> 删除后的树：  
> 5  
> –3  
> \----null  
> \----null  
> –6  
> \----null  
> \----null

[java_03.02]: https://blog.csdn.net/liangruilz/article/details/103554795