二叉树(BST树) 前序，中序，后序遍历 java实现

一时失言乱红尘 2021-09-23 07:24 321阅读 0赞

class BSTNode<T extends Comparable<T>>{
        private T data;   // 数据域
        private BSTNode<T> left; // 左孩子域
        private BSTNode<T> right; // 右孩子域
    
        public BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    
        public T getData() {
            return data;
        }
    
        public void setData(T data) {
            this.data = data;
        }
    
        public BSTNode<T> getLeft() {
            return left;
        }
    
        public void setLeft(BSTNode<T> left) {
            this.left = left;
        }
    
        public BSTNode<T> getRight() {
            return right;
        }
    
        public void setRight(BSTNode<T> right) {
            this.right = right;
        }
    }
    
    /**
     * BST树的实现
     * @param <T>
     */
    class BST<T extends Comparable<T>> {
        public BSTNode<T> root; // 指向根节点
    
        /**
         * BST树的初始化
         */
        public BST() {
            this.root = null;
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * BST树的非递归插入操作
         *
         * @param data
         */
        public void non_insert(T data) {
            //1.判断：根节点root为空,直接生成根节点，让root指向，结束！
    
            if (root == null) {
                this.root = new BSTNode<>(data, null, null); //创建根节点, 这个节点就是根节点
                return;
            }
    
            //2.如果根节点root不空，则从根节点搜索一个合适的位置，放新节点。
            BSTNode<T> cur = this.root;
            BSTNode<T> parent = null;
            while (cur != null) {
                if (cur.getData().compareTo(data) > 0) {   //如果插入的值小于根节点，将根节点的左孩子置为根节点，
                    parent = cur;
                    cur = cur.getLeft();
                } else if (cur.getData().compareTo(data) < 0) {    //如果插入的值大于根节点，将根节点的右孩子置为根节点，
                    parent = cur;
                    cur = cur.getRight();
                } else {   //相等，则直接返回
                    return;
                }
            }
    
            // 3.生成新节点，把节点的地址，写入父节点相应的地址域。
            if (parent.getData().compareTo(data) > 0) {  //插到父节点的左孩子
                parent.setLeft(new BSTNode<>(data, null, null));
            } else if (parent.getData().compareTo(data) < 0) { //插入到父节点的右孩子
                parent.setRight(new BSTNode<>(data, null, null));
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 非递归实现BST树的删除操作
         *
         * @param data
         */
        public void non_remove(T data) {
            if (this.root == null) {
                return;
            }
            // 1. 先搜索BST树，找到待删除的节点
            BSTNode<T> cur = this.root;
            BSTNode<T> parent = null;
    
            while (cur != null) {    //不为空,搜索
                if (cur.getData().compareTo(data) > 0) {  //在左边查
                    parent = cur;
                    cur = cur.getLeft();
                } else if (cur.getData().compareTo(data) < 0) {  //在右边查
                    parent = cur;
                    cur = cur.getRight();
                } else {  //相等的话，待删除节点就是当前这个cur节点
                    break;
                }
            }
            if (cur == null) {       //没有为data的节点，
                return;
            }
            // 2. 判断删除节点是否有两个孩子，如果有，用前驱的值代替，直接删除前驱
            if (cur.getRight() != null && cur.getLeft() != null) {  //删除的节点有俩孩子
                //找前驱节点，用前驱代替要删除的节点的值，然后直接删除前驱节点
    
                BSTNode<T> old = cur;   //标记一下删除的节点
                parent = cur;
                cur = cur.getLeft(); //前驱节点是左子树最大的节点
                while (cur.getRight() != null) {
                    parent = cur;   //更新父节点
                    cur = cur.getRight(); //得到要删除节点的前驱节点
                }
                old.setData(cur.getData());  //直接用前驱节点的值代替
            }
            // 3. 删除有一个孩子的节点，或者没有孩子的节点（看作有一个孩子，孩子是null）
            BSTNode<T> child = cur.getLeft(); //
            if (child == null) {
                child = cur.getRight();
            }
    
            if (parent == null) {   //根节点没有左子树，删除的就是根节点，
                this.root = child;
            } else {
                if (parent.getLeft() == cur) {
                    parent.setLeft(child);
                } else {
                    parent.setRight(child);
                }
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 非递归实现BST树的搜索，找到返回true，找不到返回false
         *
         * @param data
         */
        public boolean non_select(T data) {
            //根节点为空，直接返回。
            if (this.root == null) {
                return false;
            }
    
            BSTNode<T> cur = this.root;
    
            while (cur != null) {    //不为空,搜索
                if (cur.getData().compareTo(data) > 0) {  //在左边查
                    cur = cur.getLeft();
                } else if (cur.getData().compareTo(data) < 0) {  //在右边查
                    cur = cur.getRight();
                } else {  //相等的话，待删除节点就是当前这个cur节点
                    System.out.println(" 有data:  " + data);
                    return true;
                }
            }
            if (cur == null) {       //没有为data的节点，
                System.out.println("没有data:  " + data);
                return false;
            }
            System.out.println(" 没有data:  " + data);
            return false;
        }
    
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 前序遍历BST树的API接口
         */
        public void preOrder() {
            System.out.println("递归前序遍历：");
            preOrder(this.root);
            System.out.println();
        }
    
        /**
         * 前序遍历BST树的具体操作函数  VLR
         *
         * @param root
         */
        public void preOrder(BSTNode<T> root) {
            if (root != null) {
                System.out.print(root.getData() + " ");
                preOrder(root.getLeft());
                preOrder(root.getRight());
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * LVR  中序遍历BST树的API接口
         */
        public void inOrder() {
            System.out.println("递归中序遍历：");
            inOrder(this.root);
            System.out.println();
        }
    
        /**
         * LVR  中序遍历BST树的具体操作函数
         *
         * @param root
         */
        public void inOrder(BSTNode<T> root) {
            if (root != null) {
                inOrder(root.getLeft());
                System.out.print(root.getData() + " ");
                inOrder(root.getRight());
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 后序遍历BST树的API接口
         */
        public void postOrder() {
            System.out.println("递归后序遍历：");
            postOrder(this.root);
            System.out.println();
        }
    
        /**
         * 后序遍历BST树的具体操作函数
         *
         * @param root
         */
        public void postOrder(BSTNode<T> root) {
            if (root != null) {
                postOrder(root.getLeft());
                postOrder(root.getRight());
                System.out.print(root.getData() + " ");
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 层序遍历BSt树的API接口
         *
         * @return
         */
        public void levelOrder() {
            System.out.println("递归层序遍历：");
            int hight = level();
            for (int i = 0; i < hight; i++) {
                levelOrder(this.root, i);
            }
            System.out.println();
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 以root为根节点层序遍历BSt树的具体操作
         *
         * @return
         */
        public void levelOrder(BSTNode<T> root, int i) {
            if (root != null) {
                if (i == 0) {
                    System.out.print(root.getData() + " ");
                    return;
                }
                levelOrder(root.getLeft(), i - 1);
                levelOrder(root.getRight(), i - 1);
    
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 返回BST树中所有节点个数的API
         *
         * @return
         */
        public int number() {
            return number(this.root);
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 以Root为根节点计算BST树的节点个数
         *
         * @return
         */
        private int number(BSTNode<T> root) {
            if (root == null) {
                return 0;
            } else {
                return number(root.getLeft()) + number(root.getRight()) + 1;
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 返回BST树中的高度/层数的API
         *
         * @return int
         */
        public int level() {
            return level(this.root);
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 计算以Root为根节点的BST数的高度
         *
         * @return int
         */
        private int level(BSTNode<T> root) {
            if (root == null) {
                return 0;
            } else {
                int left = level(root.getLeft());
                int right = level(root.getRight());
                return left > right ? left + 1 : right + 1;
    
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /*
         * 求BSt树的镜像反转API
         * */
        public void mirror() {
            mirror(this.root);
    
        }
    
        /*
         * 求BSt树的镜像反转的具体操作
         * */
        private void mirror(BSTNode<T> root) {
            if (root == null) {
                return;
            } else {
    
                BSTNode<T> tmp = root.getLeft();
                root.setLeft(root.getRight());
                root.setRight(tmp);
    
                mirror(root.getLeft());
                mirror(root.getRight());
             //   System.out.print(root.getData() + " ");
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
    
        /*
         * 把BST树中满足[begin，end]区间的所有元素打印出来
         * API
         * */
        public void printAreaDatas(T begin, T end) {
            printAreaDatas(this.root, begin, end);
            System.out.println();
        }
    
        /*
         * 把BST树中满足[begin，end]区间的所有元素打印出来具体操作
         *
         * */
        public void printAreaDatas(BSTNode<T> root, T begin, T end) {
            if (root == null) {
                return;
            }
    
            // 如果当前节点的值小于begin，就不用再递归节点的左子树了
            if(root.getData().compareTo(begin) > 0) {
                printAreaDatas(root.getLeft(), begin, end);
            }
            if (root.getData().compareTo(begin) >= 0 && root.getData().compareTo(end) <= 0) {
                System.out.print(root.getData() + " ");
            }
            // 当前节点的值小于end，才有必要继续访问当前节点的右子树
            if(root.getData().compareTo(end) < 0) {
                printAreaDatas(root.getRight(), begin, end);
            }
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /*
         *  判断一颗二叉树是否为BST树,是则返回true，否则返回false
         *  错误解法：这个函数只是判断了固定root的左右孩子。验证的结果不准确
         * */
        public boolean isBST() {
            return isBST(this.root);
        }
    
        private boolean isBST(BSTNode<T> root) {
            if (root == null) {
                return true;
            }
    
            if (root.getLeft() != null && root.getLeft().getData().compareTo(root.getData()) > 0) {
                return false;
            }
            if (root.getRight() != null && root.getRight().getData().compareTo(root.getData()) < 0) {
                return false;
            }
    
            return isBST(root.getLeft()) && isBST(root.getRight());
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /*/
         * 判断是否为BST。
         * 正解：value 记录中序遍历上一个数据的值,
         * */
        public boolean isBstTrue() {
            T value = null;
            return isBstTrue(this.root, value);
        }
    
        private boolean isBstTrue(BSTNode<T> root, T value) {
            if (root == null) {
                return true;
            }
            //左子树不满足BST树的性质，直接返回，不用再递归
            if (!isBstTrue(root.getLeft(), value)) {
                return false;
            }
            //判断root和记录的上一个value进行比较
            if (root != null && root.getData().compareTo(value) < 0) {
                return false;
            }
            //每次判断完之后要更新value的值进行下一次判断
            value = root.getData();
    
            return isBstTrue(root.getRight(), value);
    
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /*
         * 返回两个节点的最近公共祖先节点的值
         * */
        public T getLCA(T data1, T data2) {
            return getLCA(this.root, data1, data2);
        }
    
        private T getLCA(BSTNode<T> root, T data1, T data2) {
            if (this.root == null) {
                return null;
            }
            if (root.getData().compareTo(data1) > 0 && root.getData().compareTo(data2) > 0) {  //在左边找
                return getLCA(root.getLeft(), data1, data2);
            } else if (root.getData().compareTo(data1) < 0 && root.getData().compareTo(data2) < 0) {   //在右边找
                return getLCA(root.getRight(), data1, data2);
            } else {   //d1在左，d2在右,公共祖先为根节点
                return root.getData();
            }
    
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         *返回中序遍历倒数第K个值
         *
         */
        public T getOrderValue(int k) {
            int num = number();   num - k    1 2 3 4 5 6 7   k=3
            return getOrderValue(this.root, num - k);
        }
    
        private int i = 0;
    
        private T getOrderValue(BSTNode<T> root, int k) {
            if (root == null) {
                return null;
            }
            T value = getOrderValue(root.getLeft(), k);
            if (value != null) {  //
                return value;
            }
            if (i++ == k) {
                return root.getData();
            }
            return getOrderValue(root.getRight(), k);
    
        }
    
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         *  判断参数tree是否是当前BST树的子树，是返回true，否则返回false
         */
    
        public boolean isChildTree(BSTNode<T> tree) {
             BSTNode<T> cur = this.root;
            //现在主树里找到子树的根节点，找到进行判断
            while (cur!= null) {
                if (cur.getData().compareTo(tree.getData()) > 0) {   //在左边寻找
                 cur = cur.getLeft();
                } else if (cur.getData().compareTo(tree.getData()) < 0) {   //在右边寻找
                    cur = cur.getRight();
                } else {
                    break;
                }
            }
            if(cur == null) {
                return false;
            }
            return isChildTree(this.root,tree);
        }
    
        private boolean isChildTree(BSTNode<T> root, BSTNode<T> tree) {
            if(root == null && tree == null){
                return true;
            }
            if(root == null){
                return false;
            }
            if(tree == null){
                return  true;
            }
            if(root.getData().compareTo(tree.getData()) != 0){
                return false;
            }
            return isChildTree(root.getLeft(),tree.getLeft())
                    && isChildTree(root.getRight(),tree.getRight());
    
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * 根据参数传入的pre前序遍历数组和in中序遍历数组，重建二叉树
         * @param pre
         * @param in
         */
        public void rebuild(T[] pre, T[] in) {
           this.root = rebuild(pre,0,pre.length-1,in,0,in.length-1);
        }
    
        private BSTNode<T> rebuild(T[] pre, int i, int j, T[] in, int m, int n) {
            if(i > j || m > n){
                return null;
            }
            //先创建主树的根节点(是前序遍历的第一个值)
           BSTNode<T> node= new BSTNode<>(pre[i],null,null);
            for (int k = m; k <= n; ++k) {
                //在中序遍历中找到根节点pre[0], 左子树的中序列范围[m,k-1]，右子树的范围[k+1,n]
                if(pre[i].compareTo(in[k]) == 0){
                    //递归创建左子树
                    node.setLeft(rebuild(pre,i+1,i+(k-m),in,m,k-1));
                    //递归创建右子树
                    node.setRight(rebuild(pre,i+(k-m)+1,j,in,k+1,n));
                    break;
                }
            }
            return node;
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
    
        /**
         * BST树的递归插入操作
         * 以root为起始节点，寻找适合的位置，插入data
         * 并把插入号的二叉树的根节点返回
         * @param root
         * @param data
         */
    
        public BSTNode<T> insert(BSTNode<T> root,T data) {
            if(root.getData().compareTo(data) > 0){
                insert(root.getLeft(),data);
            }else if(root.getData().compareTo(data) < 0){
                insert(root.getRight(),data);
            }else {
            }
            return root;
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
        /**
         * BST树的递归删除操作
         * 以root为根节点，找到值为data的节点进行删除，并把删除节点的孩子进行返回
         * @param data
         */
        public void remove(T data){
            this.root = remove(this.root,data);
        }
    
        private BSTNode<T> remove(BSTNode<T> root, T data) {
            if(root == null){
               return null;
            }
            if(root.getData().compareTo(data) > 0){
                root.setLeft(remove(root.getLeft(),data));
            }else if(root.getData().compareTo(data) < 0){
                root.setRight(remove(root.getRight(),data));
            }else {   //找到要删除的节点
                if(root.getLeft() != null && root.getRight() != null){ //两个孩子
                    BSTNode<T> pre = root;
                    pre = pre.getLeft();
                    while(pre.getRight()!= null){
                        pre = pre.getRight();
                    }
                    root.setData(pre.getData());
                    root.setLeft(remove(root.getLeft(),pre.getData()));
                }else {
                    if(root.getLeft() != null){
                        return root.getLeft();
                    }else if(root.getRight() != null){
                        return root.getRight();
                    }else {
                        return null;
                    }
                }
            }
            return root;
        }
    /*----------------------------------------------------------------------------------------------------------------------------------------*/
    
        /* *
         *
         * 判断以参数root为根节点的BST树是否为一个平衡树
         * @return true/false
         * *//*
        class BSTNode<T extends Comparable<T>>{
            int data;
            BSTNode left;
            BSTNode right;
        }
        public boolean isAVL(BSTNode<T>  root) {
            //root为null，是AVL树
            if(root == null){
                return true;
            }
    
            return false;
        }*/
    }
    
    public class BSTDemo {
    
        public void test01(){
            BST<Integer> bst = new BST<>();
            BSTNode<Integer> node1 = new BSTNode<>(40, null, null);
            BSTNode<Integer> node2 = new BSTNode<>(20, null, null);
            BSTNode<Integer> node3 = new BSTNode<>(10, null, null);
            BSTNode<Integer> node4 = new BSTNode<>(50, null, null);
            BSTNode<Integer> node5 = new BSTNode<>(80, null, null);
            BSTNode<Integer> node6 = new BSTNode<>(30, null, null);
            BSTNode<Integer> node7 = new BSTNode<>(90, null, null);
    
            node1.setLeft(node2);
            node1.setRight(node5);
    
            node2.setLeft(node3);
            node2.setRight(node4);
    
            node5.setLeft(node6);
            node5.setRight(node7);
    
            bst.root = node1;
    
            System.out.println(bst.isBST());
        }
    
    
        public static void main(String[] args) {
            /*
            * 重建2叉数的测试用例
            * */
           /* Integer[] pre = {58, 23, 12, 18, 35, 47, 82, 69, 74, 87, 95};
            Integer[] in = {12, 18, 23, 35, 47, 58, 69, 74, 82, 87, 95};
            BST<Integer> bst = new BST<>();
            bst.rebuild(pre, in);  //重建
    
            bst.preOrder();  //前
            bst.inOrder();  //中
            bst.postOrder();   //后*/
    
            BST<Integer> bst = new BST<>();
            int[] ar = {58,23,82,12,35,69,87,18,47,74,95};
            for (int val : ar) {
                bst.non_insert(val);
            }
          bst.non_remove(1);
            bst.non_select(23);
            System.out.println();
            bst.preOrder();
            System.out.println();
            bst.inOrder();
            System.out.println();
            bst.postOrder();
            System.out.println();
            bst.levelOrder();
    
            System.out.println();
            System.out.println("BST树中的节点个数为： "+bst.number());
            System.out.println("BST树的层数/高度为： "+ bst.level());
            System.out.println( );
    
            System.out.println("镜像反转：");
            bst.mirror();
            System.out.println( );
            System.out.print("在区间的元素为：");
            bst.printAreaDatas(23,50);
    
           // System.out.println(bst.isBST());
            // System.out.println(bst.isBstTrue());
    
            //bst.getLCA(23,25);
    
            System.out.println("倒数第k个节点为： "+bst.getOrderValue(2));
    
            bst.remove(47);
         }
    }