給定一組二叉樹，選擇一個覆蓋所有樹的子集

Question

我有一組二叉樹。我需要找到它們的最小子集，使它覆蓋所有的樹。我的意思是，如果有一棵樹A和一棵樹B使得B是A的一棵子樹，那麼A覆蓋B.通過最小子集，我的意思是，在可以覆蓋所有樹的所有子集中，我們需要一個具有最小尺寸（大小=該組中樹的數量）。

Answer 1

如何：

1）按樹節點數排序樹。從節點最少的節點開始。

2）構建一個樹形比較器，該樹形比較器獲取兩個數據結構圖。這個比較器應該首先迭代兩棵樹中較大的一棵（遞歸地）尋找較小樹中的頂層節點。如果找到：並排迭代，直到找到差異（無匹配）或到較小樹的末尾（MATCH）

3）比較小棵樹與其他樹，直到第一次MATCH或直到所有其他樹已經相比。 （開始比較你認爲最匹配的樹）。如果不匹配：該樹必須位於您的子集中。如果匹配：放棄當前樹，因爲它在另一棵樹中表示。

4）比較第二棵小樹和所有更大的圖等。