计算二进制表达式树的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 ...。我假设零是合适的，因为在递归中实际上不应该访问此路径

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

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

Answer 2

你是说：

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

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

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