何时使用inorder,preorder和postorder遍历

Question

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

你什么时候用？说明每种遍历方法最有意义的情况将非常有用.

谢谢!

Answer 1

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

预订和后序遍历最常用于二叉搜索树以外的树.例如,要评估表达式A + B * C,您可以创建如下树:

要计算表达式,请按顺序遍历树,将每个运算符应用于每个子树的值.

如果您希望(例如)使用类似Lisp的语言生成输出,则预序遍历可以用于大致相同的目的,因此表达式应该如下所示(add A (mul B C)).