graph-theory - 前序遍历是否可能与后序遍历的顺序相同？

Question

如果 T 是具有多个节点的有序树。T 的前序遍历是否可能与 T 的后序遍历以相同的顺序访问节点？如果“是”，请您举个例子。如果“否”，您能否解释为什么它不会发生？

Answer 1

除非我遗漏了一些非常明显的东西，否则答案是否定的。具有 > 1 个节点（例如，2 个节点）的有序树将如下所示。

    A    
 B                     

或者

    A
        C

后序遍历按照左-右-根的顺序访问节点，前序遍历按照根-左-右的顺序访问节点。为了让它们产生相同的输出，“left”必须等于“root”，这没有任何意义。在上面的例子中，pre-order 将分别产生 AB 或 AC，post-order 将产生 BA 和 CA。

Answer 2

在一般情况下，树的叶子是唯一的，因此，如果您正在执行前序或后序遍历，则应该以相反的方式出现。

但是，我可以看到前序遍历和后序遍历相同的两种情况：单例元素和重复元素。

对于单例，您只有一个节点，因此无论您在寻找零叶之前还是之后访问它都没有关系。

如果你有一棵树，里面有重复的元素怎么办？如果插入策略是接受任何大于或等于根节点的元素，那么它们将显示为右侧的退化树：

 A
  \
   A
    \
     A
      \
       A

如果它小于或等于根节点，您仍然会有一棵退化树，但在左侧。

现在，如果您的插入策略是丢弃重复元素，那么您将剩下单例情况，它仍然具有导致相同元素的前序和后序遍历。