data-structures - 是否可以使用前序和后序序列创建二叉非唯一树？

Question

是否可以使用前序和后序序列创建二叉非唯一树？
如果可以，如何做到这一点？例如，我如何制作一棵非唯一的树:

预购:

B C I J K H D E F G

邮购:

I H K J C G F E D B

有多少个？

Answer 1

预购伪代码:

preorder (tree)
{
    if tree isn't empty then
    {
        print key[tree]
        preorder left[tree]
        preorder right[tree]
    }
}

邮政订单是:

postorder (tree)
{
    if tree isn't empty then
    {
        preorder left[tree]
        preorder right[tree]
        print key[tree]
    }
}

所以从有序的顺序我们可以得出结论:

• “B”必须是根
• “C”必须是“B”的 child
• “G”必须是最大值(树中最右边的节点)或左子树中的最小值(左子树中最左边的节点) - 在这种情况下“G”必须是叶子，“F”必须是“G”的父级

从后订单中我们可以得出结论:

• “I”必须是叶子和最小值(树中最右边的节点)。
• 如果我没有子节点，“H”必须是“I”的父节点(“I”是“H”的左子节点)，否则“H”是树中下一个最左边的子节点。

从这里开始，它就像数独:

是的:通过使用前序和后序输出，您只能以一种方式构建树。