在對象樹中找出最大重複子樹

Question

我正試圖解決在對象樹中查找最大重複子樹的問題。

通過對象樹我的意思是一棵樹，其中每個葉和節點都有一個名稱。每個葉子都有一個類型和與該葉子相關的那種類型的值。每個節點都有一組按特定順序的樹葉/節點。

給定一個對象樹 - 我們知道 - 它有一個重複的子樹。

通過重複，我的意思是2個或更多的子樹在所有事物（名稱/類型/子元素的順序）中都是相似的，但葉子的值是相似的。子樹之間不能共享節點/樹葉。

問題是確定最大高度的這些子樹。

我知道窮舉搜索可以做到這一點。我正在尋找更有效的方法。

Answer 1

你可以實現一個dfs遍歷爲每個節點生成一個散列值。將這些值與節點高度一起存儲在一個簡單的數組中。子樹候選項是重複值，只需檢查候選項是否正確，因爲兩個不同的子樹可以產生相同的散列值。
假設葉和內部節點都是類型節點和標準訪問和遍歷功能：

procedure dfs_update(node : Node, hashmap : Hashmap) 
begin 
    if is_leaf(node) then 
    hashstring = concat("LEAF",'|',get_name_str(node),'|',get_type_str(node)) 
    else // node is an internal node 
    hashstring = concat("NODE",'|',get_name_str(node)) 
    for each child in get_children_sorted(node) 
     dfs_update(child,hashmap) 
     hashstring = concat(hashstring,'|',get_hash_string(hashmap,child)) 
    end for 
    end if 
    // only a ref to node is added to the hashmap, we could also add 
    // the node's height, hashstring, whatever could be useful and inapropriate 
    // to keep in the Node ds 
    add(hashmap, hash(hashstring),node) 
end 

棘手的部分是dfs_update之後，我們必須得到在collinding節點列表hasmap通過降低高度並檢查兩個兩個，他們確實是重複性的。