如何从字符串表达式构建二叉树

Question

给定一个字符串(((!D!)B!) a ((!F(!H!))C(!G!))))，没有空白。如何构建二叉树?

我应该实现一个构造函数，并使用索引遍历来构建它。这个字符串将输出

任何帮助/提示将非常感激!!

Answer 1

试试这个

static Node parse(String input) {
return new Object() {
final int length = input.length();
int index = 0;
int ch = get();
int get() { return ch = index < length ? input.charAt(index++) : -1; }
Node node() {
if (ch == '!') {
get();
return null;
} else if (ch == '(') {
get();
Node left = node();
char data = (char)ch;
get();
Node right = node();
if (ch != ')')
throw new RuntimeException("')' expected");
get();
return new Node(left, data, right);
} else
throw new RuntimeException("'!' or '(' expected");
}
Node parse() {
Node node = node();
if (ch != -1)
throw new RuntimeException("extra string: " + input.substring(index - 1));
return node;
}
}.parse();
}

和

public static void main(String[] args) {
String input = "(((!D!)B!)A((!F(!H!))C(!G!)))";
Node root = parse(input);
System.out.println(root);
}

输出:

Node[left=Node[left=Node[left=null, data=D, right=null], data=B, right=null], data=A, right=Node[left=Node[left=null, data=F, right=Node[left=null, data=H, right=null]], data=C, right=Node[left=null, data=G, right=null]]]

Answer 2

可以使用递归进行解析:

public BinaryTree(String t) {
this.root = parse(new StringReader(t));
}
private static Node parse(StringReader reader) {
char c = (char)reader.read();
if (c == '!')
return null;
if (c == '(') {
Node left = parse(reader);
char data = (char)reader.read();
Node right = parse(reader);
if (reader.read() != ')')
throw new IllegalArgumentException();
return new Node(left, data, right);
}
throw new IllegalArgumentException();
}