從「指紋」重建樹木

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個。

通過您選擇的無損壓縮算法運行該輸出。

您也可以使用樹的深度優先遍歷或任何其他類型的遍歷。無論你最容易重建。