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

Question

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

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

谢谢!

Answer 1

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

前序和后序遍历最常应用于二叉搜索树以外的树。例如，要评估像 A + B * C 这样的表达式，你可以像这样创建一棵树:



要对表达式求值，请按后序遍历树，将每个运算符应用于其每个子树中的值。

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