树遍历问题-教科书问题

Question

这是教科书中关于二叉树的问题，并提供了答案。

如果后序遍历按照U、G、T、R、A、I的顺序访问存储字符值的二叉树的节点，那么同一个二叉树的中序遍历的访问顺序是什么？

a) 我、G、U、A、T、R

b) R, G, U, I, T, A

c) G, U, I, T, A, R

d) 无法确定

答案：c

现在的问题是C的答案是怎样的。我意识到单独的后序遍历不足以唯一标识一棵树，并且可以为任何类型的树（非有序）定义前序和后序遍历，但不能唯一标识一棵树。可以进行中序和后序遍历。该问题没有指定 BST，因此可以有所作为。所以我想我需要澄清答案是 C 而不是我认为的 D。

Answer 1

我同意你的评价。

尽管选项 C 确实与给定的 post-order 遍历兼容 - 当我们采用这棵树时：

   I                Inorder: G U I T A R
 /   \              Postorder: U G T R A I
G     A
 \   / \
  U T   R

...选项 A 也与给定的 post 顺序兼容，如果我们采用这棵树：

    I               Inorder: I G U A T R
     \              Postorder: U G T R A I
      A
    /   \
   G     R
    \   /
     U T

正如您正确指出的那样，单独的 post 顺序遍历并不能唯一地定义二叉树，唯一正确的答案是无法确定 in-order 遍历（选项 D）。

除非原题有额外的信息，否则这是一个糟糕的问题。

Tree Traversal question- A textbook question