I'm trying to write a method that can transfer an array into a Binary tree. I know the code is not right, I run it and hope it would show something that I can continue to fix it. But it just kept loading without any error or result. May anyone give me some advice, please! Here is the BST class:

public class BSTNode {
    private String data;

    private BSTNode left;
    private BSTNode right;

    public BSTNode(String data) {
        this.data = data;
        this.right = null;
        this.left = null;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public BSTNode getLeft() {
        return left;
    }

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

    public BSTNode getRight() {
        return right;
    }

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

And my method:

public BSTNode fromArray(String[] array, int start, int end) {
    int i = start;
    BSTNode root = new BSTNode(array[i]);
    BSTNode current = root;
    BSTNode parent = null;
    while (i <= end) {
        if (array[i].compareTo(current.getData()) < 0) {
            parent = current;
            current.setLeft(current); //Should I put current.setLeft(root) here?
        } else {
            parent = current;
            current.setRight(current);
        }
        // Create the new node and attach it to the parent node
        if (array[i].compareTo(parent.getData()) < 0) {
            parent.setLeft(new BSTNode(array[i]));
        } else {
            parent.setRight(new BSTNode(array[i]));
        }
        i  ;
    }
    return current;
}

Thank you for your time!

CodePudding user response：

After you've initialized the root, you've already inserted the first element, so you can increment i right away.

You set the left and right pointers without keeping track of the prior value.

You never change the value of current within the loop, and, as you immediately assign it to parent, you don't change parent either.

You should return the root instead of the current node.

How about something like this:

    while (  i <= end) {
        current = root;
        while (current != null) {
            parent = current;
            if (array[i].compareTo(current.getData()) < 0) {
                current = current.getLeft();
            } else {
                current = current.getRight();
            }
        }
        // Create the new node and attach it to the parent node
        if (array[i].compareTo(parent.getData()) < 0) {
            parent.setLeft(new BSTNode(array[i]));
        } else {
            parent.setRight(new BSTNode(array[i]));
        }
    }
    return root;

UPDATE:

You can avoid a redundant comparison by keeping its result in a variable:

    while (  i <= end) {
        boolean left;
        current = root;
        do {
            parent = current;
            left = array[i].compareTo(current.getData()) < 0;
            if (left) {
                current = current.getLeft();
            } else {
                current = current.getRight();
            }
        } while (current != null);
        // Create the new node and attach it to the parent node
        if (left) {
            parent.setLeft(new BSTNode(array[i]));
        } else {
            parent.setRight(new BSTNode(array[i]));
        }
    }
    return root;

CodePudding user response：

public class Main {

    public static final class Node {

        public static final String NULL = "_";
        public static final String SPLIT = ",";

        private final String val;
        private Node left;
        private Node right;

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

    }

    public static void main(String... args) {
        Node root = createBinaryTree();
        String str = serialize(root);   // 0,1,3,7,_,9,_,_,_,4,_,_,2,5,_,8,_,_,6,_,_
        Node newRoot = deserialize(str);
    }

    private static String serialize(Node root) {
        StringBuilder buf = new StringBuilder();
        serialize(root, buf);
        return buf.toString();
    }

    private static void serialize(Node node, StringBuilder buf) {
        if (buf.length() > 0)
            buf.append(Node.SPLIT);

        if (node == null)
            buf.append(Node.NULL);
        else {
            buf.append(node.val);
            serialize(node.left, buf);
            serialize(node.right, buf);
        }
    }

    private static Node deserialize(String str) {
        String[] values = str.split(Node.SPLIT);
        return deserialize(values, new AtomicInteger());
    }

    private static Node deserialize(String[] values, AtomicInteger i) {
        if (i.get() >= values.length)
            return null;

        String value = values[i.getAndIncrement()];

        if (Node.NULL.equalsIgnoreCase(value))
            return null;

        Node node = new Node(value);
        node.left = deserialize(values, i);
        node.right = deserialize(values, i);

        return node;

    }

    /*
     *         0
     *       /  \
     *      1    2
     *     / \  / \
     *    3  4 5  6
     *   /      \
     *  7        8
     *   \
     *    9
     */
    private static Node createBinaryTree() {
        Node[] nodes = { new Node("0"), new Node("1"), new Node("2"), new Node("3"),
                new Node("4"), new Node("5"), new Node("6"), new Node("7"),
                new Node("8"), new Node("9") };

        nodes[0].left = nodes[1];
        nodes[0].right = nodes[2];
        nodes[1].left = nodes[3];
        nodes[1].right = nodes[4];
        nodes[2].left = nodes[5];
        nodes[2].right = nodes[6];
        nodes[3].left = nodes[7];
        nodes[5].right = nodes[8];
        nodes[7].right = nodes[9];

        return nodes[0];
    }


}