binary-search-tree - 何时使用中序、前序和后序遍历

Question

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

你什么时候使用每个？说明每种遍历方法何时最有意义的情况将非常有帮助。

谢谢！

Answer 1

中序遍历只是按定义的顺序处理项目。例如，如果你有一个单词或名称列表的 BST，inorder traversal 会按顺序打印出来。

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

为了评估表达式，您以后序遍历树，将每个运算符应用于其每个子树的值。

如果您想（例如）以 Lisp 之类的语言生成输出，则可以将前序遍历用于大致相同的目的，因此表达式应该输出为(add A (mul B C)).