如果仅给出其预订或阶数或次级遍历，则可以唯一地识别“完整二叉树”的结构？

Question

如果只有在给出了以下3个遍历中的一个时，我无法理解一个完整的二叉树：预订，下令，按顺序。

以下是完整二叉树的定义：

一个完整的二进制树是一个二进制树，其中每个级别除了最近可能是完全填充的，并且所有节点都可以尽可能远。

上面的定义已从此链接中取出： https://web.cecs.pdx.edu/~Sheard / Camant / CS163 / Doc / FullVsComplete.html

如果有人可以证明或直观地解释为什么我们可以或不能唯一地构造一个完整的二叉树，那么如果只给出其3个遍历一个？

Answer 1

给定 $ n $ ，只有一个完整的二叉树（cbt）的形状，带 $ n $ 节点。

对于任何确定性遍历，在CBT中的节点在CBT的遍历期间的位置之间的对应关系是完全固定的。因此，如果给出了确定性遍历，我们可以唯一地重建CBT。这不仅适用于任何一个预订，秩序或级遍历中的任何一个，它也适用于呼吸首先遍历（与右侧儿童前面访问的左子），或者提到的任何其他确定性遍历通过Hendrik Jan在他的评论。

这是一个例子。上面的形状是具有12个节点的CBT的唯一形状，即1根（处于深度0），深度为1,4个节点的2个节点，深度为2和5个节点，深度为3.一个预定遍历CBT按以下顺序访问节点。

1. 根节点。
2. 深度1的第一个节点。
3. 深度的第一个节点。
4. 深度3的第一个节点。
5. 深度3的第二节点。
6. 深度2的第二节点。
7. 深度3的第三节点。
8. 深度3的第四节点。
9. 深度1.
的第二节点
10. 深度2的第三节点。
11. 深度3的第五节点。
12. 深度2的第四节点。

给出上面的列表，我们知道根节点是访问的1 ^{st node，深度1的第一节点是访问的2 nd node。 ..，深度3的第四节点是访问过的8 th -node，深度3的第五节点是访问的11 th node。}