将二叉树转换为后缀数学表达式的算法？

Question

我有一个二叉树，用于表示一个数学表达式（中缀），我想直接将这个树转换为后缀表达式（堆栈）。 请问有人能提供算法建议吗？

- Ashish Agarwal

Answer 1

您要查找的是后序遍历二叉树。相关信息可以参考维基百科。

postorder(node)
  if node.left  ≠ null then postorder(node.left)
  if node.right ≠ null then postorder(node.right)
  print node.value

- Konrad Rudolph

Answer 2

很简单，每个节点都是（左，右，数据）。

从第一个节点开始。如果有左子树，则执行左子树的算法，然后执行右子树的算法，最后打印数据。

TreeNode = ([TreeNode], Data, [TreeNode])

TreeToPostfix: [TreeNode] -> Data*
TreeToPostfix(nil) = []
TreeToPostfix((left, data, right)) ==
  TreeToPostfix(left) ++ TreeToPostfix(right) ++ Data

例如：

              +
            /   \
           *     -
          / \   / \
         2   3 4   5

输出结果：2 3 * 4 5 - +

- Toon Krijthe

---

请解释一下这种方法，因为数据始终会在树的最低层。 - Ashish Agarwal

数据在这种情况下既是值又是运算符。我的算法产生了前缀，但现在已经固定为后缀。 - Toon Krijthe