从 InOrder 字符串表示构建二叉树

Question

我得到了一个像这样的字符串：(((!D!)B!)A((!F(!H!))C(!G!))) 其中从来没有任何空格。一种 '！'意味着节点的那一侧没有 child 。为了形象化这一点，前面提到的字符串看起来像：https://i.stack.imgur.com/WywYm.png

我必须有一个可以调用递归方法通过传入字符串来构建树的构造函数，这就是我这里的：

public BinaryTree(String tree) {
    //build the tree from the inOrder representation of the tree
    //in the inOrder representation an empty tree is ! and a non-empty tree is (leftdataright)
    if(tree.charAt(0) == '!') root = null;
    root = buildTree(tree).root;
}

从这里开始，我通过私有 BuildTree 方法进入，该方法应该使用递归和 return 对完全组装树的根的引用。我的代码是：

private BinaryTree buildTree(String tree) {
    char data = tree.charAt(0);
    BinaryTree b1;
    BinaryTree b2;      
    if(tree.charAt(0) == '!') return new BinaryTree();
    b1 = buildTree(tree.substring(1, tree.length()));
    b2 = buildTree(tree.substring(1, tree.length()));
    return new BinaryTree(b1, data, b2);
}

我猜我对 InOrder 表示感到困惑，在这种表示中，您不会运行进入完整树的根，直到您深入到字符串中。我当前的代码没有做任何事情，而且我完全不知道如何在不立即了解根的情况下完成此操作。如果有人可以更好地解释这一点，让我更接近解决方案，请告诉我。谢谢。

Answer 1

这样的事情怎么样：

private static BinaryTree buildTree(String tree) {
    try {
        return buildTree(new StringReader(tree));
    } catch (IOException ex) {
        throw new RuntimeException(ex.getMessage());
    }
}

private static BinaryTree buildTree(Reader in) throws IOException {
    char c = (char)in.read();
    if (c == '!') {
        return null;
    } else if (c != '(') {
        throw new IOException("Syntax error");
    }
    BinaryTree left = buildTree(in);
    char data = (char)in.read();
    BinaryTree right = buildTree(in);
    c = (char)in.read();
    if (c != ')') {
        throw new IOException("Syntax error");
    }
    return new BinaryTree(left, data, right);
}

从 InOrder 字符串表示构建二叉树

Building a BinaryTree from an InOrder String Representation

java

binary-tree

inorder