二叉树括号表示转中序遍历异常问题排查求助

输入表达式G(Y(u)(5))(2(t))对应的二叉树结构为：

G
      /   \
     Y     2
    / \     \
   u   5     t

预期中序遍历结果为u Y 5 G 2 t，但当前代码输出错误，以下是问题分析与修正方案：

代码核心错误 #

1. strToTree方法逻辑混乱 #

• 栈与队列的使用逻辑完全错误，未正确维护二叉树的父子节点关系
• 遇到右括号)时，每次新建root和parent节点，直接覆盖之前的树结构，导致仅保留部分节点
• 未区分左、右子树的创建时机，无法构建完整的二叉树

2. inOrderTraverse方法硬编码失效 #

• 手动通过字符下标创建节点，完全未使用strToTree构建的树结构
• 多次调用遍历方法处理孤立节点，不符合中序遍历从根节点递归的标准逻辑

3. Node类冗余成员 #

• Node类中的root变量无意义，混淆了节点本身与树的根节点概念

修正后的代码 #

import java.util.Stack;

public class BinaryTree {
    Node root;
    String tree;

    public BinaryTree(String tree) {
        this.tree = tree;
        this.root = strToTree(tree); // 构造时直接完成树的构建
    }

    // 正确解析括号表达式为二叉树
    public Node strToTree(String tree) {
        if (tree == null || tree.isEmpty()) {
            return null;
        }

        Stack<Node> stack = new Stack<>();
        Node currentRoot = null;
        boolean isLeftChild = true; // 标记下一个节点是左/右子节点

        for (int i = 0; i < tree.length(); i++) {
            char c = tree.charAt(i);
            if (c == '(') {
                // 左括号：将当前节点压栈，准备处理子节点
                stack.push(currentRoot);
                isLeftChild = true;
            } else if (c == ')') {
                // 右括号：弹出父节点，回到上层
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (Character.isLetterOrDigit(c)) {
                // 字符/数字：创建节点并挂载到对应位置
                Node node = new Node(c);
                if (currentRoot == null) {
                    // 第一个节点作为根节点
                    currentRoot = node;
                } else {
                    Node parent = stack.peek();
                    if (isLeftChild) {
                        parent.left = node;
                    } else {
                        parent.right = node;
                    }
                    isLeftChild = false; // 下一个默认是右子节点
                }
                currentRoot = node;
            }
        }

        return currentRoot;
    }

    // 中序遍历入口：从根节点开始递归
    public void inOrderTraverse() {
        if (root != null) {
            root.inOrderTraverse();
        }
    }

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

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

        // 节点的中序遍历递归实现
        public void inOrderTraverse() {
            if (left != null) {
                left.inOrderTraverse();
            }
            System.out.print(data + " ");
            if (right != null) {
                right.inOrderTraverse();
            }
        }
    }

    // 测试示例
    public static void main(String[] args) {
        String input = "G(Y(u)(5))(2(t))";
        BinaryTree bt = new BinaryTree(input);
        bt.inOrderTraverse(); // 输出：u Y 5 G 2 t
    }
}

修正说明 #

1. 二叉树构建逻辑：

   • 用栈维护父节点层级，遇到(压栈、)弹栈
   • 通过isLeftChild标记区分左/右子节点，正确挂载新建节点
   • 遍历过程中动态维护当前处理的节点，确保树结构完整

2. 中序遍历逻辑：

   • 入口方法直接调用根节点的递归遍历
   • Node类的遍历方法严格遵循「左子树→当前节点→右子树」的中序规则

3. 冗余清理：

   • 删除Node类中无用的root变量
   • 简化类成员，仅保留必要的树结构与输入字符串变量

内容的提问来源于stack exchange，提问作者dogood92