将字符串数组传输到二叉树

Question

我正在尝试编写一种可以将数组转换为二叉树的方法。我知道代码不正确，我运行它并希望它能显示一些我可以继续修复它的东西。但它一直在加载，没有任何错误或结果。请任何人给我一些建议！这是 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;
    }
}

还有我的方法：

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

感谢您的宝贵时间！

Answer 1

初始化 root 后，您已经插入了第一个元素，因此您可以立即递增 i。

您设置了 left 和 right 指针，但没有跟踪先前的值。

您永远不会在循环中更改 current 的值，并且当您立即将其分配给 parent 时，您也不会更改 parent。

您应该 return root 而不是 current 节点。

这样的事情怎么样：

    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;

更新：

您可以通过将结果保存在变量中来避免冗余比较：

    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;

Answer 2

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


}

将字符串数组传输到二叉树

Transferring a String array to Binary Tree

java

binary-tree

binary-search-tree