如何解析括号表示法二叉树字符串并实现中序遍历

在面试或实际开发中，常遇到这样的需求：给定字符串如 `G(Y(u)(5))(2()(t))`，需要将其还原为二叉树，并输出中序遍历结果（预期输出 `u Y 5 G 2 t`）。解析过程中，栈的用法、父子关系的维护、空子树的识别等环节容易出现错误，值得仔细处理。

括号表示法本质上是递归结构的序列化。每个非括号字符代表一个节点，其后第一个 `(...)` 对应左子树，第二个 `(...)` 对应右子树。`()` 明确表示该子树为空。常见错误包括：看到 `)` 就创建新节点、左右子树归属关系搞反、空栈调用 `lastElement()` 导致异常。

避免这些问题的核心思路是同步维护两个栈：

• 一个栈存放待填充子节点的父节点（`Stack`）；
• 另一个栈标记下一个子节点应挂在左边还是右边（`Stack`，`false` 表示左，`true` 表示右）。

解析过程逐字符扫描输入字符串：

• 遇到字母或数字（如 `G`、`u`），新建节点；
• 若栈为空，该节点为树根；
• 否则，根据 `sidestack.peek()` 决定挂到父节点的哪一侧，挂完后立即翻转侧标志（`push(!side)`），为另一个子节点做准备；
• 遇到 `)` 且前一字符不是 `(`，说明当前节点子树处理完毕，从两个栈中弹出；
• 遇到 `(` 直接跳过，仅作结构分隔。

以下是简洁健壮的完整实现：

public class BinaryTree {
    Node root;

    public BinaryTree(String input) {
        root = null;
        Stack stack = new Stack<>();
        Stack sidestack = new Stack<>(); // false → left, true → right

        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);
            if (ch == ')') {
                // 结束当前节点的子树定义：若前一字符不是 '('，说明此节点有实际内容，可弹出
                if (i > 0 && input.charAt(i - 1) != '(') {
                    stack.pop();
                    sidestack.pop();
                }
            } else if (ch != '(') { // 字母或数字
                Node node = new Node(ch);
                if (stack.isEmpty()) {
                    root = node;
                } else {
                    boolean isRight = sidestack.peek();
                    Node parent = stack.peek();
                    if (isRight) {
                        parent.right = node;
                    } else {
                        parent.left = node;
                    }
                    sidestack.pop();
                    sidestack.push(true); // 下一次应填右子树
                }
                stack.push(node);
                sidestack.push(false); // 新节点默认先填左子
            }
        }
    }

    public void inOrderTra verse() {
        Node.inOrderTra verse(root);
    }

    static class Node {
        char data;
        Node left;
        Node right;

        Node(char data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }

        static void inOrderTra verse(Node root) {
            if (root == null) return;
            inOrderTra verse(root.left);
            System.out.print(root.data + " ");
            inOrderTra verse(root.right);
        }
    }

    // 测试入口
    public static void main(String[] args) {
        String input = "G(Y(u)(5))(2()(t))"; 
        // 注意：原题例 "G(Y(u)(5))(2(t))" 缺少左空子树标记，
        // 规范写法应为 "G(Y(u)(5))(2()(t))"，否则解析歧义
        BinaryTree tree = new BinaryTree(input);
        tree.inOrderTra verse(); // 输出：u Y 5 G 2 t
    }
}

关键注意事项

空子树必须显式声明：`2(t)` 写法不规范，应写成 `2()(t)`，否则解析器无法区分“右子树为 t”与“左子树缺失、右子树为 t”。括号对 `()` 为语义必需。

Node 类无需 root 字段：`root` 仅属于 `BinaryTree`，避免混淆。`inOrderTra verse` 设为 `static`，消除对 `this` 的误依赖。

避免冗余字段：`BinaryTree` 中无需保留 `parent`、`c`、`r`、`tree` 等成员变量。构造完成后输入字符串即可释放。

测试用例验证：输入 `"G(Y(u)(5))(2()(t))"`，输出 `u Y 5 G 2 t`，与预期一致。

时间复杂度为 O(n)（一次扫描），空间复杂度为 O(h)（h 为树高，取决于栈深度）。该实现兼具正确性、可读性与工程健壮性。