何时使用inorder、preorder和postorder遍历

Question

我了解如何在二叉搜索树上执行inorder、preorder和postorder遍历的代码。但是，我对应用程序感到困惑。

你什么时候会用到每一个？举例说明每种遍历方法何时最有意义，这将非常有帮助。

谢谢!

Answer 1

Inorder遍历只是按定义的顺序处理项。例如，如果您有一个单词或名称列表的BST，则顺序遍历将按顺序打印它们。

前序和后序遍历最常应用于树，而不是二进制搜索树。例如，要计算像A + B * C这样的表达式，可以像这样创建一个树：

​

​

要计算表达式，您可以按后序遍历树，将每个运算符应用于其每个子树中的值。

如果您希望(例如)以Lisp之类的语言生成输出，那么可以使用预序遍历来实现大致相同的目的，因此表达式应该输出为(add A (mul B C))。