我理解树遍历和实现背后的想法，但这是问题所在。为什么我们都需要它们？
现在我只知道解析数学表达式时使用了前序遍历。从维基百科我还读到：
- 中序遍历在二叉搜索树上使用中序遍历特别常见，因为根据设置二叉搜索树的比较器（因此得名），这将按顺序从底层集合返回值。前序遍历
- 在将值插入新树的同时按前序遍历树是制作二叉搜索树的完整副本的常用方法。还可以使用前序遍历从表达式树中获取前缀表达式（波兰表示法）：按顺序遍历表达式树。（我已经说过）
但这些例子相当模糊。任何人都可以更深入地描述这一点。尤其是例子。
问问题
4573 次
2 回答
6
考虑在目录树上做一些文件操作的问题。当操作是删除文件时，则需要在删除目录本身之前清空每个目录，因此需要进行后序遍历。相比之下，在复制层次结构时，需要先复制目录，因此需要进行前序遍历。
老实说，我看不出 BST 中序遍历有什么模糊之处。当您想在用户界面的屏幕上显示 BST 的内容时，您希望按键按顺序显示，不是吗？（如果你不这样做，那么使用 BST 可能不是一个好主意，因为哈希表通常更快。）
于 2012-09-30T19:54:08.630 回答
3
我能想到很多例子。以性能为例。
想象一下现实生活中的一棵树。它有一个茎，茎有3个分支。这些内部分支中的每一个都有 3 个外部分支。所以它有9个外部分支。
3 个内部分支之一死了，随后它的 3 个外部分支也死了。
现在你想剪掉所有的枯枝。这棵树有 13 个分支（1 个茎 3 个内部和 9 个外部）。您是否必须单独查看它们以确定是否要切割它们？不
现在想象有一个机器人想要砍掉所有枯死的树枝。在它的软件麸皮中，它看着茎..它死了吗？不，然后它会查看第一个内部分支是否已死？是的！然后它会切断那个分支，同时它的外部分支也将被切断。
而不是做出 13 个选择，它只需要做出 10 个。（茎、2 个健康的内部分支、它们的 6 个外部分支和生病的内部分支）
于 2012-10-02T12:02:12.290 回答