data-structures - 二叉树到普通树

Question

我知道从一棵通用树中你可以构造一棵唯一的二叉树，但反过来是真的吗？即你能从二叉树中得到一个唯一的通用树吗？

Answer 1

是的。以下变换是可逆的：

给定一棵具有有序但没有索引的子节点的通用树，将第一个子节点编码为其父节点的左子节点，并将每个其他节点编码为其（前）兄弟节点的右子节点。

反过来是：给定一棵具有区分左右子节点的二叉树，将节点的左子节点读取为其第一个子节点，将右子节点读取为其下一个兄弟节点。

所以，下面的树

  a
 /|\
b c d

被编码为

  a
 /
b
 \
  c
   \
    d

而下面的树

   a
  / \
 b   c
 |
 d

被编码为

     a
    /
   b
  / \
 d   c

（阅读：d是 的第一个孩子b，c是 的兄弟姐妹a）。

请注意，您可以通过将同级分配给根来对任何有根森林（具有有序组件，否则表示不唯一）进行编码，因此

  a
 / \
b   c
 \   \
  d   e

将被读作

  a   c e
 / \
b   d

---

这是从二叉树中获取唯一通用（无向）树的另一种方法：

• 一个顶点二叉树可能有 0...3 个图邻居。
• 将 12 个节点附加到根
• 将 8 个节点附加到每个左孩子
• 将 4 个节点附加到每个右孩子

此操作是可逆的：

• 用至少 12 个邻居“根”标记节点。如果不是唯一的，则失败。
• 用 8..11 个“左”邻居标记每个节点。
• 用 4..7 个邻居“正确”标记每个节点。
• 去除所有叶子
• 使所有边远离根
• 如果任何节点有多个左孩子或多个右孩子，则失败。

所以，

• 有序有根树和二叉树（第一种和第二种算法）之间存在双射。
• 由于任何通用树都可以任意植根，因此存在从通用（有向或无向）树到二叉树的注入。
• 存在从二叉树到一般无向树的注入（第三种算法）
• 由于存在从二叉树到一般树并返回的注入，因此在一般（有向或无向）树和二叉树之间必须存在双射。

Answer 2

我觉得不太可能。通常，二叉树区分左孩子和右孩子。但是，一般的树不会。

我们应该如何从这两个二叉树中得到一个唯一的通用树。

  X      X
 / \    / \
 Y Z    Z Y

而这两个呢？

  X      X
 /        \
 Y        Y

另一方面，

如果您选择不区分二叉树的左右子树，或者选择尊重子树出现在一般树中的序列，只需将每个二叉树映射到自身即可。这将是每个二叉树的唯一通用树。