java - 评估二叉表达式树的算法？

Question

我讨厌递归，我不能轻松地跟踪代码，但是对于树我别无选择。

这是我到目前为止所尝试的。

private int evaluate(Node n)
{
    if (n != null)
    {
        if (n.isLeaf())  // n is a node with a number
            return Integer.parseInt(n.element);
        else
        {
            int left = evaluate(n.left);
            int right = evaluate(n.right);
            return calculate(left, n.element, right);
        } //end else
    } //end if
} //end evaluate

Answer 1

你的意思是：

return calculate(left, n.element, right);

我假设您的节点是一个操作，即“+”、“-”等。

您的“计算”必须对 int “left”和“right”执行相应的操作，您就完成了！

Answer 2

该方法没有为每个路径提供有效的返回。所以你需要return ...在方法的最后添加。我认为零是合适的，因为在您的递归中实际上不应该访问此路径。

private int evaluate(Node n)
{
    if (n != null)
    {
        if (n.isLeaf())  // n is a node with a number
            return Integer.parseInt(n.element);
        else
        {
            int left = evaluate(n.left);
            int right = evaluate(n.right);
            return calculate(left, n.element, right);
        } //end else
    } //end if
    return 0;
} //end evaluate

除此之外，您的递归似乎状况良好。