Making a binary tree with a constructor with an array parameter-CodePudding

I'm currently trying to make my own binary tree by using a constructor with an array of objects as a parameter. I want it to go depth-by-depth, and going left-to-right in each level. I currently have something like this:

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

So if I were to call this: new BinaryTree(1,2,3,4,5,6) it'll look like this:

If it's not complete: new Binary Tree(1,2,3,4,5,7) will look like this:

Anyone know how to achieve this?

CodePudding user response：

Some issues:

When you make the first call to makeBinaryTree, the node argument is null, and thus any access to node.getLeft(), node.setLeft(), ...etc, is invalid. Although root receives a value, that is a different variable than the local variable node, which does not change by that update ("call by value").
The second function only creates a new node when root is null, which happens only once. So in total it will never create more than one single node.
The second function always returns the root node, which is not what you want to get returned from the deeper recursive calls.

It is a better coding pattern when you omit this Node parameter completely. Instead let the job of makeBinaryTree be to create the node for the given index, and return it, and let it be ignorant of root. That way the first call can assign that returned Node instance to root.

Here is the corrected code:

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

If you have a Node constructor that can take three arguments (value, left and right), then the second function can be shortened to:

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

CodePudding user response：

Similar to level order traversal binary tree, I don't think you should use recursion. Build tree with a queue:

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