使用带有数组参数的构造函数制作二叉树

Question

我目前正在尝试通过使用以对象数组作为参数的构造函数来制作我自己的二叉树。我希望它逐个深入，并在每个级别从左到右。我目前有这样的东西：

public BinaryTree(Object... args) {
        makeBinaryTree(args, root, 0);
    }
    public Node makeBinaryTree(Object[] args, Node node, int h) {
        if (h < args.length && root == null) {
            setRoot(new Node(args[0]));
            node.setLeft(makeBinaryTree(args, node.getLeft(), 2 * h + 1));
            node.setRight(makeBinaryTree(args, node.getRight(), 2 * h + 2));
        }
        return root;
    }

所以如果我要这样称呼：new BinaryTree(1,2,3,4,5,6) 它看起来像这样：

如果不完整：new Binary Tree(1,2,3,4,5,7) 将如下所示：

有人知道如何实现吗？

Answer 1

类似于层序遍历二叉树，我认为你不应该使用递归。用队列构建树：

public class BinaryTree {

    public BinaryTree(Object... args) {
        if (args == null || args.length == 0) {
            return;
        }
        root = new Node(args[0]);
        LinkedList<Node> queue = new LinkedList<>();
        Node current = root;
        int i = 0;
        while (current != null) {
            if(2 * i + 1 < args.length){
                current.left = new Node(args[2 * i + 1]);
                queue.add(current.left);
            }
            if (2 * i + 2 < args.length){
                current.right = new Node(args[2 * i + 2]);
                queue.add(current.right);
            }
            current = queue.poll();
            i++;
        }
    }


    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    static class Node {
        Node left;
        Node right;

        Object val;

        public Node(Object val) {
            this.val = val;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }
}

Answer 2

一些问题：

当您第一次调用 makeBinaryTree 时，node 参数是 null，因此对 node.getLeft()、node.setLeft(), ...等无效。尽管 root 接收到一个值，但该值与局部变量 node 不同，后者不会因该更新而改变（“按值调用”）。
第二个函数只在root为null时创建一个新节点，这只会发生一次。所以总的来说它永远不会创建超过一个节点。
第二个函数总是 return 是 root 节点，这不是您想要从更深层次的递归调用中得到的 return。

完全省略此 Node 参数是一种更好的编码模式。相反，让 makeBinaryTree 的工作是创建给定索引的节点，然后 return 它，然后让它不知道 root。这样第一次调用就可以将 returned Node 实例分配给 root.

这是更正后的代码：

public BinaryTree(Object... args) {
    if (args != null && args.length > 0) {
        setRoot(makeBinaryTree(args, 0));
    }
}

public Node makeBinaryTree(Object[] args, int h) {
    if (h >= args.length) return null;
    Node node = new Node(args[h]);
    node.setLeft(makeBinaryTree(args, 2 * h + 1));
    node.setRight(makeBinaryTree(args, 2 * h + 2));
    return node;
}

如果你有一个 Node 构造函数可以接受三个参数（值、左和右），那么第二个函数可以缩短为：

public Node makeBinaryTree(Object[] args, int h) {
    return h >= args.length ? null
         : new Node(args[h], 
                    makeBinaryTree(args, 2 * h + 1),
                    makeBinaryTree(args, 2 * h + 2));
}

使用带有数组参数的构造函数制作二叉树

Making a binary tree with a constructor with an array parameter

java

arrays

constructor

binary-tree