后序遍历

Question

15

按顺序遍历二叉树（in-order tree traversal）显然有一个应用：按顺序获取内容。

前序遍历（preorder traversal）似乎非常适合创建二叉树的副本。

后序遍历（postorder traversal）对于二叉树有一个共同的用途吗？

- Dean J

要按不同的顺序获取它，例如后缀表达式：http://en.wikipedia.org/wiki/Reverse_Polish_notation - Steven Sudit

想到了HP计算器的语法。+1 - Dean J

是的，后缀表达式非常适合在堆栈上评估表达式。与中缀表达式不同，它对操作顺序也没有歧义。 - Steven Sudit

4个回答

4

如果这棵树代表一个数学表达式，那么要计算这个表达式，就需要进行后序遍历。

- madcoder

3

是的。后序遍历有时用于在不同表示法之间翻译数学表达式。

- Sushisource

0

它还可以生成二叉树的后缀表示。

- aerin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 1337c0d3r · Accepted Answer

让我再补充一个：

后序遍历在删除树时也非常有用。为了释放树中所有节点的内存，必须按照只有当其左右子树都被删除时才能删除当前节点的顺序删除节点。

后序遍历恰好可以做到这一点。它先处理左右子树，再处理当前节点。