Java表达式树中序遍历问题排查：未处理中间元素及括号错误

兄弟，我瞅了下你的问题——实现表达式树中序遍历的时候，中间元素处理完全跑偏了，比如前缀表达式* 1 + 2 3（如果对应你说的正确输出(1+(2*3))，那应该是前缀表达式写错了，实际应该是+ 1 * 2 3？不过不管这个细节，重点是你的遍历逻辑肯定出问题了），你得到的输出却是(1(23)+)*，这明显是遍历顺序、括号逻辑还有元素拼接全错了。

先看你贴的代码片段：

public String toStringPrettyInFix(){ 
    return printInorder(root)+")"; 
}
String printInorder(FCNSTreeNode root) { 
    String s=""; 
    if (root == null) return "";
    // 你没写完的部分就是问题核心所在

问题根源分析 #

1. 遍历顺序完全搞反了：中序遍历的核心规则是「左子树 → 根节点 → 右子树」，但你的输出里运算符位置颠倒、操作数直接粘连，说明你大概率是先处理了根节点，或者把左右子树的遍历顺序写反了，完全没遵循中序的基本逻辑。
2. 括号添加逻辑缺失：表达式树的中序遍历必须根据运算符优先级加括号，不然会直接改变运算顺序。比如当父节点运算符优先级低于子节点时，子树的结果必须用括号包裹。
3. 操作数与运算符的拼接错误：你没有在操作数和运算符之间做正确分隔，导致2和3直接粘在一起变成23，完全不符合表达式格式。

修复后的代码示例 #

我给你写了一个带优先级判断和括号处理的完整实现，你可以直接参考：

// 先补充节点类的定义（假设你没贴出来）
public class FCNSTreeNode {
    String value;
    FCNSTreeNode left;
    FCNSTreeNode right;

    public FCNSTreeNode(String value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 以下是表达式树类中的核心方法
private FCNSTreeNode root; // 你的根节点

public String toStringPrettyInFix() {
    if (root == null) return "";
    String result = printInorder(root);
    // 如果根节点是运算符，外层加括号（匹配你示例的输出格式）
    if (!isOperand(root.value)) {
        return "(" + result + ")";
    }
    return result;
}

private String printInorder(FCNSTreeNode root) {
    if (root == null) return "";

    // 叶子节点是操作数，直接返回值
    if (root.left == null && root.right == null) {
        return root.value;
    }

    String leftStr = printInorder(root.left);
    String rightStr = printInorder(root.right);
    String op = root.value;

    // 根据优先级判断是否给左右子树加括号
    int currentPriority = getPriority(op);
    int leftPriority = root.left != null ? getPriority(root.left.value) : Integer.MAX_VALUE;
    int rightPriority = root.right != null ? getPriority(root.right.value) : Integer.MAX_VALUE;

    // 左子树优先级低于当前运算符，加括号
    if (leftPriority < currentPriority) {
        leftStr = "(" + leftStr + ")";
    }
    // 右子树优先级低于当前，或者同级且是左结合运算符（加减乘除都是左结合），加括号
    if (rightPriority < currentPriority || (rightPriority == currentPriority && isLeftAssociative(op))) {
        rightStr = "(" + rightStr + ")";
    }

    // 按中序顺序拼接：左 + 运算符 + 右
    return leftStr + op + rightStr;
}

// 获取运算符优先级：乘除高于加减
private int getPriority(String op) {
    return switch (op) {
        case "+", "-" -> 1;
        case "*", "/" -> 2;
        default -> Integer.MAX_VALUE; // 操作数优先级最高，不需要括号
    };
}

// 判断是否为左结合运算符（加减乘除都是左结合）
private boolean isLeftAssociative(String op) {
    return "+-*/".contains(op);
}

// 判断是否为操作数（简单判断是否不是运算符）
private boolean isOperand(String value) {
    return !"+-*/".contains(value);
}

为什么这样写就对了？ #

• 先区分操作数和运算符：叶子节点直接返回值，不需要处理括号。
• 递归遍历左右子树后，根据优先级和结合性决定是否给子树结果加括号，从根本上保证运算顺序不会出错。
• 外层的括号根据根节点是否是运算符来添加，完美匹配你想要的输出格式。

比如对于前缀表达式+ 1 * 2 3（对应你说的正确输出(1+(2*3))），用这个方法遍历后，会自动给*的子树加括号，最终输出符合预期的结果。

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