c++ - 仅给定一次遍历时找到二叉树的其他两次遍历

Question

我知道当给定二叉树的中序和前序遍历作为字符串时，您可以重建二叉树，但是仅在给定中序遍历的情况下，是否可以找到后序和/或前序遍历？

Answer 1

不，仅从中序遍历中检索后序/预序是不可能的。如果是这样，则可以仅使用中序遍历来重构二叉树，这是不可能的，因为一次中序遍历可以为您提供几种可能的重构二叉树。

Answer 2

您的输入看起来如何，树的目的是什么？

如果你有一个完全括号内的有序表达式，那么你就有一个唯一的树，你可以通过构造树然后从树中构造前序项和后序项来获得前序和后序项。

如果您的表达式没有完全括起来，那么这表明与您的顺序匹配的不同树之间没有区别。例如，如果它是表示算术表达式的树，则 与andx+y+z相同。然而，这意味着，您使用哪个预购或后购都没有关系，而且是相同的。(x+y)+zx+(y+z)++xyz+x+yz

现在，如果这无关紧要，您无需担心您的有序的几种可能的表示。只需选择其中一种表示，然后计算这棵树引起的前序和后序。