从“指纹”重建树木

Question

我已经完成了我的SO和Google的研究，并且还没有找到任何人解决过这个问题，或者至少有人写过关于它的文章。

我的问题是，给定一个任意高度的“通用”树，每个节点可以有任意数量的分支，有没有一种方法可以独特（有效地）“指纹”任意子树从“普遍”树的根，这样给予普遍的树和树的指纹，我可以重建原来的树？

举例来说，我有一个 “万能” 树（原谅我那可怜的插图），代表我的可能性的宇宙：

 
       Root 
     ///| \ \ ... \ 
     O O O O O O  O (Level 1) 
     /|\/|\...................\ (Level 2) 

等

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

 
     Root 
    //|\ \ 
    O O O O O 
    /

等等

有没有办法到“f ingerprint“这棵树，那么鉴于指纹和普遍树，我可以重建A？

我正在思考一个散列，压缩，或可能是一个功能/声明性构造？大O分析（时间或空间）是一个优点。

作为一个例子，嵌套表达式如：{{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...}表示树中每个级别上存在的实际节点可能是有效的，但是它可以更有效地完成吗？

Answer 1

我会用列表，在列表中的每个元素指定你有几个孩子的名单：

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

是与第一级两个节点和左子有一个树子节点，右子节点有2个。

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

您也可以使用树的深度优先遍历或任何其他类型的遍历。无论你最容易重建。