c++ - 不是表达式转换，而是从前序到中序的转换（不是表达式）

Question

我不是要求表达式转换

中缀到前缀的转换

我只是问一个BST，如果输入以前缀表示法的形式给出，即BST的前序遍历，那么我如何将值序列转换为中缀表示法，即BST的中序遍历。

                 8
               /  \
              1    12
              \     /
               5   9
             /   \
            4     7
                 /
                6

例如，前序遍历将给出 8 1 5 4 7 6 12 9

我如何将这些值（输入）序列转换为中序遍历表达式 1 4 5 6 7 8 9 12。

AS 在某些情况下，中序表达式更容易处理......

Answer 1

使用 BST：
前缀：左子树、节点、右子树。
中缀：节点、左子树、右子树。
后缀：右子树、左子树、节点。

转换取决于您如何遍历树。

Answer 2

让

V = 顶点

L = 左子树

R = 右子树

预购 = VLR

有序 = LVR

后订单 = LRV

（只需切换顺序即可修复，它是相同的）

将它们放回去以使前缀值成为中缀值的一种方法是再次使用前缀值创建二叉搜索树并进行中序遍历。

或者！

只是排序老兄......（如果你将它们挤压成一条线（从上到下挤压），BST 总是排序）