java - 评估二叉树 Java 中的表达式

Question

我创建了一个表达式的二叉树，并将运算符(+、-、/、*)作为根，将操作数(值)作为左/右子项。我需要使用参数 (T, v) 在二叉树中评估该表达式，其中“T”是二叉树，“v”是后序遍历开始的节点。

我搜索了后序遍历的工作原理以及我所理解的所有内容。但是我不知道如何使用节点'v'来实现后序遍历的代码。

我的方法是这样的......

public int evaluateExpression (LinkedBinaryTree<T> tree, Position<T> v) {

}

这应该返回正在其运算符(根的子级)上使用的运算符。所以，我明白该怎么做，我被困在如何实际去做上。 -.-

Answer 1

您不需要提供整棵树，也不需要单独的 Position 类。每个子树都是一棵树。你只需要这样的东西:

public class <T extends Number> ExpressionTree<T> {
    private ExpressionTree<T> left, right;
    private T value;
    private int operator;

    // constructors, getters, setters, etc. elided

    public T evaluateExpression() {
        // Here I am assuming a <T> value field that is set if the node
        // is a literal value rather than an expression subtree with left and right children.
        if (this.value != null)
            return this.value;
        // Evaluate the subtree
        switch (this.operator) {
        case '+':
            return left.evaluateExpression()+right.evaluateExpression();
        // etc for the other operators
        }
    }

您不应使用下面评论中提到的 LinkedBinaryTree 类。它不是为此目的而设计的，在我看来，即使是为了它自己的目的，它也显得不必要地复杂。