u011352239
友谊地久天长
采纳率0%
2019-12-07 14:14 阅读 218

数据结构求问:想用层次遍历序列构造二叉树,但是下面的代码运行之后只能构造一层,具体应该怎么改?

5

图片说明

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • u010597819 会灰翔的灰机 2019-12-09 17:06

    可以参考这个AVL树的实现,遍历序列insert node即可

    public class AvlNode<T> {
    
        private T data;
        private Integer height;
        private AvlNode<T> left;
        private AvlNode<T> right;
        private AvlNode<T> parent;
    
        public AvlNode(T data) {
            this(data, null, null);
        }
    
        public AvlNode(T data, AvlNode left, AvlNode right) {
            this.height = 0;
            this.data = data;
            this.left = left;
            this.right = right;
        }
    
        public T getData() {
            return data;
        }
    
        public void setData(T data) {
            this.data = data;
        }
    
        public Integer getHeight() {
            return height;
        }
    
        public void setHeight(Integer height) {
            this.height = height;
        }
    
        public AvlNode<T> getLeft() {
            return left;
        }
    
        public void setLeft(AvlNode<T> left) {
            this.left = left;
        }
    
        public AvlNode<T> getRight() {
            return right;
        }
    
        public void setRight(AvlNode<T> right) {
            this.right = right;
        }
    
        public AvlNode<T> getParent() {
            return parent;
        }
    
        public void setParent(AvlNode<T> parent) {
            this.parent = parent;
        }
    
        @Override
        public String toString() {
            return "AvlNode{" + "height=" + height + ", data=" + data + '}';
        }
    }
    import lombok.Data;
    @Data
    public class SimpleAvlTree {
    
        public static AvlNode<Integer> insert(Integer data, AvlNode<Integer> node) {
            if (node == null) {
                return new AvlNode<Integer>(data);
            }
            int compareResult = compare(data, node.getData());
            if (compareResult < 0) {
                node.setLeft(insert(data, node.getLeft()));
                if (height(node.getLeft()) - height(node.getRight()) == 2 ) {
                    if (compare(data, node.getLeft().getData()) < 0) {
                        node = rotateWithLeftChild(node);
                    } else {
                        node = doubleWithLeftChild(node);
                    }
                }
            } else if (compareResult > 0) {
                node.setRight(insert(data, node.getRight()));
                if (height(node.getRight()) - height(node.getLeft()) == 2 ) {
                    if (compare(data, node.getRight().getData()) > 0) {
                        node = rotateWithRightChild(node);
                    } else {
                        node = doubleWithRightChild(node);
                    }
                }
            }
            node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
            return node;
        }
    
        /**
         * 根据左子节点右旋
         * @param k2 : 
         * @return org.gallant.tree.avl.AvlNode<java.lang.Integer> : 
         */
        public static AvlNode<Integer> rotateWithLeftChild(AvlNode<Integer> k2){
            AvlNode<Integer> k1 = k2.getLeft();
            k2.setLeft(k1.getRight());
            k1.setRight(k2);
            k2.setHeight(Math.max(height(k2.getLeft()), height(k2.getRight())) + 1);
            k1.setHeight(Math.max(height(k1.getLeft()), k2.getHeight()) + 1);
            return k1;
        }
        /**
         * 根据右子节点左旋
         * @param k2 : 
         * @return org.gallant.tree.avl.AvlNode<java.lang.Integer> : 
         */
        public static AvlNode<Integer> rotateWithRightChild(AvlNode<Integer> k2){
            AvlNode<Integer> k1 = k2.getRight();
            k2.setRight(k1.getLeft());
            k1.setLeft(k2);
            k2.setHeight(Math.max(height(k2.getRight()), height(k2.getLeft())) + 1);
            k1.setHeight(Math.max(height(k1.getRight()), k2.getHeight()) + 1);
            return k1;
        }
        /**
         * 先左旋再右旋
         * @param k3 : 
         * @return org.gallant.tree.avl.AvlNode<java.lang.Integer> : 
         */
        public static AvlNode<Integer> doubleWithLeftChild(AvlNode<Integer> k3){
            k3 = rotateWithRightChild(k3.getLeft());
            return rotateWithLeftChild(k3);
        }
        /**
         * 先右旋再左旋
         * @param k3 : 
         * @return org.gallant.tree.avl.AvlNode<java.lang.Integer> : 
         */
        public static AvlNode<Integer> doubleWithRightChild(AvlNode<Integer> k3){
            k3 = rotateWithLeftChild(k3.getRight());
            return rotateWithRightChild(k3);
        }
    
        /**
         * 比较两个节点的大小
         * @param data1 :
         * @param data2 :
         * @return java.lang.Integer :
         */
        public static Integer compare(Integer data1, Integer data2) {
            return data1 - data2;
        }
        /**
         * 获取节点高度,如果为空则为-1
         * @param node :
         * @return java.lang.Integer :
         */
        public static Integer height(AvlNode<Integer> node) {
            return node == null ? -1 : node.getHeight();
        }
    
        public static AvlNode<Integer> test(){
            AvlNode<Integer> node = SimpleAvlTree.insert(20, null);
            node = SimpleAvlTree.insert(25, node);
            node = SimpleAvlTree.insert(15, node);
            node = SimpleAvlTree.insert(18, node);
            node = SimpleAvlTree.insert(10, node);
            node = SimpleAvlTree.insert(13, node);
            return node;
        }
    
        public static AvlNode<Integer> test2(){
            AvlNode<Integer> node = SimpleAvlTree.insert(20, null);
            node = SimpleAvlTree.insert(25, node);
            node = SimpleAvlTree.insert(15, node);
            node = SimpleAvlTree.insert(18, node);
            node = SimpleAvlTree.insert(16, node);
            return node;
        }
    
        public static AvlNode<Integer> test3(){
            AvlNode<Integer> node = SimpleAvlTree.insert(20, null);
            node = SimpleAvlTree.insert(25, node);
            node = SimpleAvlTree.insert(30, node);
            return node;
        }
    
        public static void main(String[] args) {
            AvlNode<Integer> node = test();
            System.out.println(node);
            fillParent(node);
            print(node, 0, 25);
        }
    
        /**
         * 打印目标节点的路径
         * @param node : 
         * @param summary :
         * @param aim :
         */
        public static void print(AvlNode<Integer> node, Integer summary, Integer aim){
            if (node == null) {
                return;
            }
            summary += node.getData();
            if (summary.equals(aim)) {
                System.out.println(summary);
                printPath(node);
                return;
            }
            print(node.getLeft(), summary, aim);
            print(node.getRight(), summary, aim);
        }
    
        /**
         * 打印当前节点至root节点路径
         * @param node :
         */
        public static void printPath(AvlNode<Integer> node) {
            if (node.getParent() != null) {
                printPath(node.getParent());
            }
            System.out.print(node.getData()+",");
        }
    
        /**
         * 填充指向父的指针
         * @param node :
         */
        public static void fillParent(AvlNode<Integer> node) {
            if (node == null) {
                return;
            }
            if (node.getLeft() != null) {
                node.getLeft().setParent(node);
            }
            if (node.getRight() != null) {
                node.getRight().setParent(node);
            }
            fillParent(node.getLeft());
            fillParent(node.getRight());
        }
    }
    
    点赞 评论 复制链接分享

相关推荐