java - 从字符串输入构建树

Question

当提供字符串输入时，我被困在如何生成树的逻辑上。例如当我有以下形式的输入时 -

(1 (2 (3) (4)) (5 (6) ())

表示树会像这样-

            1
           / \
          2   5
         / \  /\
         3 4 6 ()

我可以像 tree.add(data) 这样从平常构建树，然后通过判断它是否大于或小于父节点来寻找要自添加的新节点。但是我无法理解如何实现如何以二进制数据结构形式存储上述字符串。

这是我到目前为止尝试过的 -

public class BinaryTree {

static Node root;

public static void levelorder(Node<?> n) {
    Queue<Node<?>> nodequeue = new LinkedList<Node<?>>();
    if (n != null)
        nodequeue.add(n);
    while (!nodequeue.isEmpty()) {
        Node<?> next = nodequeue.remove();
        System.out.print(next.data + " ");
        if (next.getLeft() != null) {
            nodequeue.add(next.getLeft());
        }
        if (next.getRight() != null) {
            nodequeue.add(next.getRight());
        }
    }
}

private static String[] breakString(String elements) {
    int indexOfOpenBracket = elements.indexOf("(");
    int indexOfLastBracket = elements.lastIndexOf(")");
    String removedPString = elements.substring(indexOfOpenBracket + 1,
            indexOfLastBracket);
    String[] breakRemovedPString = removedPString.split(" ");
    if (breakRemovedPString[1].contains("(")) {
        add(breakRemovedPString[0], breakRemovedPString[1], breakRemovedPString[2]);
    }
    return breakRemovedPString;
}

static void add(String parent, String leftString, String rightString) {

    Node<String> nodeToAdd = new Node<String>(parent);
    if (root == null) {
        root = nodeToAdd;
        root.left = new Node<String>(leftString);
        root.right = new Node<String>(rightString);
    } else {

    }

}

public static void main(final String[] args) {

    String treeString = "(1 (2) (3))";

    breakString(treeString);

    levelorder(root);
    System.out.println();
 }
}

请针对此问题提出一些实现建议。

Answer 1

这是一个经典的解析问题。最简单的方法可能是递归下降。这是树语言的语法:

T -> ( number T T )
   | ( number )
   | ()

要将其转换为解析器，我们可以通过形式化转换为 LL(1) 形式，然后进行编码。我会让您继续阅读并展示结果。

package treereader;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.io.Reader;

enum Token { LPAREN, RPAREN, NUMBER, EOF, ERROR };

class Scanner {

    final Reader in;
    final char [] buf = new char[1];
    final StringBuilder token = new StringBuilder();

    private static final char EOF_MARK = Character.MIN_VALUE;

    Scanner(Reader in) {
        this.in = in;
        read();
    }

    final void read() {
        try {
            if (in.read(buf) < 1) {
                buf[0] = EOF_MARK;
            }
        } catch (IOException ex) {
            System.err.println("i/o error");
            buf[0] = EOF_MARK;
        }
    }

    Token getNext() {
        while (Character.isWhitespace(buf[0])) {
            read();
        }
        if (Character.isDigit(buf[0])) {
            token.setLength(0);
            do {
                token.append(buf[0]);
                read();
            } while (Character.isDigit(buf[0]));
            return Token.NUMBER;
        }
        if (buf[0] == '(') {
            read();
            return Token.LPAREN;
        }
        if (buf[0] == ')') {
            read();
            return Token.RPAREN;
        }
        if (buf[0] == EOF_MARK) {
            return Token.EOF;
        }
        return Token.ERROR;
    }

    String getString() {
        return token.toString();
    }
}

class Node {
    public void print(PrintStream out) {
        out.print("()");
    }
}

class UnaryNode extends Node {

    int val;

    public UnaryNode(int val) {
        this.val = val;
    }

    @Override
    public void print(PrintStream out) {
        out.print("(" + val + ")");
   }
}

class BinaryNode extends Node {

    int val;
    Node left, right;

    public BinaryNode(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public void print(PrintStream out) {
        out.print("(" + val + " ");
        left.print(out);
        out.print(' ');
        right.print(out);
        out.print(')');
    }
}

class Parser {

    final Scanner scanner;
    Token lookAhead;

    Parser(Reader in) {
        scanner = new Scanner(in);
        lookAhead = scanner.getNext();
    }

    void advance() {
        lookAhead = scanner.getNext();
    }

    void match(Token token) throws IOException {
        if (lookAhead == token) {
            advance();
        } else {
            throw new IOException("Expected " + token + ", found " + lookAhead);
        }
    }

    Node parse() throws IOException {
        Node tree;
        match(Token.LPAREN);
        if (lookAhead == Token.NUMBER) {
            int val = Integer.valueOf(scanner.getString());
            advance();
            if (lookAhead == Token.LPAREN) {
                Node left = parse();
                Node right = parse();
                tree = new BinaryNode(val, left, right);
            } else {
                tree = new UnaryNode(val);
            }
        } else {
            tree = new Node();
        }
        match(Token.RPAREN);
        return tree;
    }
}

public class TreeReader {

    public static void main(String[] args) {
        try {
            Parser parser = new Parser(new BufferedReader(new FileReader(new File(args[0]))));
            Node tree = parser.parse();
            tree.print(System.out);
        } catch (IOException ex) {
            System.err.println(ex.getMessage());
        }
    }    
}