0

我已经完成了我的 SO 和 Google 研究，但还没有找到任何人以前解决过这个问题，或者至少没有找到任何写过它的人。

我的问题是，给定任意高度的“通用”树，每个节点都可以有任意数量的分支，有没有办法从“通用”树开始唯一（有效地）“指纹”任意子树根，这样给定通用树和树的指纹，我可以重建原始树吗？

例如，我有一个“通用”树（请原谅我糟糕的插图），代表我的可能性世界：

                根
        // / | \ \ ... \
       呜呜呜（1级）
      /|\/|\.......\（第 2 级）

等等

我也有树 A，我的宇宙的根子树

        根
      / /|\ \
     哦哦哦
    /

等等。

有没有办法给树“指纹”，这样给定指纹和通用树，我可以重建 A？

我在想一些类似于散列、压缩或函数/声明性构造的东西？Big-O 分析（在时间或空间上）是一个加分项。

例如，像这样的嵌套表达式：{{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...}表示存在于树中每一层的实际节点可能是有效的，但它可以更有效地完成吗？

4

1 回答 1

0

我会使用一个列表列表，列表中的每个元素都说明您有多少个孩子：

[[2][1,2][0,0,0]]

是一棵树，第一层有两个节点，左子节点有一个子节点，右子节点有自己的 2 个。

通过您选择的无损压缩算法运行该输出。

您还可以使用树的深度优先遍历，或任何其他类型的遍历。任何对你来说最容易重建的东西。

于 2010-04-12T18:59:48.327 回答