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

Question

网络上有很多内容说明有四种树遍历算法:

深度优先搜索 - InOrder(左-根-右)

预购(根-左-右)

后序(左-右-根)

广度优先搜索——层序遍历

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

树遍历的其他组合呢？例如:Right-Root-Left、Right-Left-Root、Root-Right-Left，以及我们从 Right 节点按 Level-order 遍历？

如果上述树遍历的组合有效，那么树遍历的时间复杂度是否与左优先对应物相同？

在实际应用中，他们是否使用树遍历的右优先组合？举例说明。

Answer 1

Are these tree traversals obtained due to the concept of Binary Search Tree? (i.e., where left subtree is smaller than right subtree and hence we traverse left before right?)

显然不是，因为这四次遍历，唯一对二叉搜索树有意义的遍历是“中序”遍历。其他三个会乱序读取元素。

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

What about other combinations of tree traversals? Example: Right-Root-Left, Right-Left-Root, Root-Right-Left, and in Level-order we traverse from Right node?

一切皆有可能。您也可以按锯齿形顺序遍历，有时在处理右 child 之前处理左 child ，有时则相反。 (或者，换句话说:有时您将第一个 child 描述为“左”，第二个 child 描述为“右”，有时则相反。)

If the above combinations of tree traversals are valid, I guess the time-complexity of tree-travels will remain the same with respect to their left-first counterparts?

如果您的树结构涉及指向子项等的显式指针，并且您的遍历遵循这些指针，那么 - 是的:“左”和“右”只是名称，不会影响理论上的时间复杂度。但是，如果您的树结构是隐式的(例如，通常使用二叉堆完成)，那么它可能取决于细节。

In real-world applications, do they use the right-first combinations of tree-traversals? Give examples.

我确信存在涉及从最大元素到最小元素遍历二叉搜索树的实际应用程序。在这样的应用程序中，术语“左”和“右”很可能是根据较小值先出现(在左侧)的约定分配的，因此从最大到最小的遍历将从“结束”开始树的最右边的节点，然后朝着它的“起点”前进，即最左边的节点。

然而，这种事情最明显的例子是使用 ORDER BY ... DESC 查询 SQL 表。条款;我相信主要的 SQL 实现使用排序的 B 树，而不是专门的二叉搜索树，所以他们可能不使用术语“左”和“右”。