为什么只有四种树遍历算法？

Question

web上有很多内容指出有四种树遍历算法：

• 深度优先搜索-无序（左-根-右）
• 预购（根-左-右）
• 后序（左-右-根）
• 广度优先搜索-级别顺序遍历

这些树遍历是由于二叉搜索树的概念获得的吗？（即，左子树比右子树小，因此我们在右之前遍历左？）

那么其他树遍历的组合呢？例如：右根左，右根左，右根左，按级别顺序从右节点开始遍历？

如果上述树遍历组合有效，那么树遍历的时间复杂度相对于其左前对应项是否保持不变？

在实际应用程序中，它们是否使用正确的树遍历的第一个组合？举例说明。

Answer 1

有一种类型的遍历en.wikipedia也没有说明：

高度遍历。从高度0处的叶子/节点开始，通过高度向上爬树的高度。

实现的无用性和不利性被视为毫无意义的练习。

Answer 2

这些树遍历是由于二叉搜索树的概念而获得的吗？（即，左子树比右子树小，因此我们先左后右遍历？）

显然不是，因为这四次遍历，对于二叉搜索树来说唯一有意义的就是“按序”遍历。其他三个将按顺序读取元素。

相反，我认为二叉树的惯例（至少在英语国家）是将第一个孩子称为“左”，将第二个孩子称为“右”，并在绘制视觉表示时相应地绘制它们。该约定既适用于二进制搜索树（其中第一个子级包含父级之前的所有值，第二个子级包含父级之后的所有值），也适用于树遍历（其中我们遍历第二个子级之前的第一个子级）。

那么其他树遍历的组合呢？示例：右根左，右根左，右根左，按级别顺序从右节点遍历？

都完全有可能。您也可以以之字形顺序遍历，有时您在处理右子级之前处理左子级，有时相反。（或者，换句话说：有时你把第一个孩子描述为“左”，第二个孩子描述为“右”，有时相反。）

如果树遍历的上述组合是有效的，我猜树遍历的时间复杂度将保持相同，相对于它们的左优先对应？

如果您的树结构包含指向子级的显式指针等，并且遍历遵循这些指针，那么-是的：“left”和“right”只是名称，不会影响理论上的时间复杂性。但是如果您的树结构是隐式的（例如，通常使用二进制堆），那么它可能取决于细节。

在实际应用程序中，它们是否使用正确的树遍历的第一个组合？举例说明。

我确信现实世界中存在一些应用程序，它们涉及从最大元素到最小元素遍历二叉搜索树。在这样的应用程序中，术语“左”和“右”很可能是基于较小的值首先出现（在左边）的约定来分配的，因此从最大到最小的遍历将从树的“末端”开始，这意味着树的最右边的节点，并朝着树的“开始”，这意味着树的最左边。

然而，这种事情最明显的例子是查询带有ORDER BY的SQL表...DESC子句；我相信主要的SQL实现使用排序的B树，而不是特别的二进制搜索树，所以他们可能不使用术语“左”和“右”。