我试图直截了当地说明如何使用树遍历来唯一地识别树，并且它的关键似乎是树是否是香草二叉树（BT），或者它是否也有更严格的规定 . 是二进制搜索树（BST） . 这个article似乎表明对于BT来说，单个有序，前序和后序遍历不会唯一地标识树（在此上下文中唯一意味着键的结构和值） . 以下是文章的快速摘要：
BTs
1.我们可以按照预先订购顺序和后序排序对BT进行独特的重建 .
2.如果我们还规定遍历跟踪节点的空子节点，我们也可以使用预订后序 .
（一个开放的问题（对我来说）如果BT可以具有非独特元素，则上述情况仍然如此）
BSTs
3.我们不能使用唯一ID . 我们需要预先订购或订购后订购 .
现在，（最后）我的问题是，我们可以只使用预订或只是下订单来唯一识别BST吗？我认为我们可以，因为这个问题和answer似乎说是，我们可以使用预订，但任何输入都非常赞赏 .
2 回答
我可以在这里问这个问题 . 任何二叉树，无论是否有序，都可以通过写出重建树所需的一系列操作来序列化 . 想象一下只有两条指令的简单堆栈机器：
将空树（或
NULL指针，如果您愿意）推入堆栈分配一个新的内部节点N，将一个值填入N，从堆栈中弹出前两个树，并将它们作为N的左右子节点，最后将N推入堆栈 .
对于这样的机器，任何二叉树都可以序列化为"program" . 序列化算法使用后序遍历 .
好的，您只能使用预订来识别树 . 这是可能的，因为只有在前序遍历中，当前节点的id才会出现在子节点的id之前 . 所以你可以读取遍历输出root-to-leaves .
您可以查看http://en.wikipedia.org/wiki/Tree_traversal#Pre-order进行确认
因此，您可以将前序遍历视为插入树的列表 . 因为插入BST的树是确定性的，所以当您将值列表插入空树时，您始终会获得相同的树 .