java - 计算表示算术表达式的二叉树的非递归方法

Question

正如主题所述，我需要描述一种在不使用递归的情况下评估二元算术表达式树的方法。没有向我提供其他详细信息或说明。

就我对这些事情的理解而言，我需要模拟树的中序遍历。假设我的教科书中概述的 ADT 方法可用，我有 hasLeft()、hasRight()、left()、right()、isInternal() 和 isExternal() 方法。我需要问我的教授是否可以自己制作这样的方法，但是没有可用的 parent() 方法，所以我可以遍历树。不过，我确实有一个 root() 方法。

有人可以指出正确的方向来弄清楚如何做到这一点吗？我想不出没有递归的方法来做到这一点，因为我没有立即跳回到树上的方法。

Answer 1

你可以保留一个已经访问过的节点栈。然后通过将新节点插入堆栈来替换递归调用，并从递归函数将返回的堆栈中弹出一个节点。

请记住，在执行递归函数时，总会有一个隐式堆栈记住在每个函数调用中传递的参数。