評估沒有堆棧的表達式樹

Question

是否可以在不使用堆棧的情況下評估表達式樹（前/後綴）？在學校的算法課上談論樹時，有這個問題。我的猜測是否定的。

Answer 1

是的，你可以。

做一棵樹的breadth first traversal（如搜索，但通過所有的樹）。你可以用vector/queue/list以迭代方式做到這一點。

完成後，您可以在上一步中生成的列表/向量/隊列後退。在每個點處計算列表中節點的值。既然你已經訪問了所有的孩子（你正在倒退），你所要做的就是查找它們的值並在節點中應用指令。