查找樹是否是其他樹的子樹

Question

有兩個二叉樹T1和T2存儲字符數據，允許重複。
我怎樣才能找到T2是否是T1的子樹？ 。
T1擁有數百萬個節點，T2擁有數百個節點。

Answer 1

遍歷T1。如果當前節點等於T2的根節點，則同時遍歷樹（T2和T1的當前子樹）。比較當前節點。如果它們總是相等，則T2是T1的子樹。

Answer 2

如果樹木不以任何方式排序，我沒有看到任何其他辦法，而不是做一個蠻力搜索：通過樹T1走路和檢查，看看是否達到其匹配的第一個節點樹的節點T2。如果不是，繼續遍歷T1。如果是這樣，檢查下一個節點是否匹配，直到找到T2的結尾，在這種情況下，您有一個命中：您的樹T2確實是T1的子樹。

如果您知道T1（從葉到節點）的每個單個節點的深度，則可以跳過任何不如所尋找子樹深的節點。這可以幫助您消除大量不必要的比較。假設T1和T2平衡良好，那麼樹T1將具有20的總深度（2**20>1,000,000）並且樹T2將具有7的深度（2**7>100）。你只需要步行13第一層T1（8192個節點 - ？或者是14層和16384個節點），並可以跳過的T1約90％......

然而，如果通過子樹表示T2的葉節點也是T1的葉節點，則可以首先遍歷T1並計算每個節點的深度（從葉到節點的距離），然後僅檢查具有深度與T2相同。

Answer 3

我建議的算法，使用預處理：

1）預先處理T1樹，保持所有可能的子樹的根的列表（緩存列表將有上百萬個條目的）;

2）按保存在根目錄中的數據降序排列緩存的根的列表。您可以選擇更優雅的排序功能，例如，將字符樹解析爲字符串。

3）使用二進制搜索來定位必要的子樹。您可以快速拒絕具有節點數目的子樹，不等於T2節點數（或不同深度）。

請注意，步驟1）和2）必須只進行一次，然後您可以使用相同的預處理結果測試多個子樹候選項。

Answer 4

我不確定，我的想法是否正確。儘管如此，爲了你的持久。

1. 在Tree 1中進行後續步行1 & Tree 2，稱之爲P1和P2。
2. 比較P1 & P2。如果它們不同。樹不是子樹。出口。
3. 如果它們相同，或P1包含在P2中。你可以決定哪一個是子樹。

Answer 5

如果你是內存/存儲綁定（即不能預處理和存儲樹的替代形式），你可能無法做任何事情比其他一些其他建議的蠻力搜索更好答案（遍歷P1尋找P2的匹配根，遍歷兩者以確定節點是否實際上是匹配子樹的根，如果不匹配則繼續原始遍歷）。此搜索以O（n * m）運行，其中n是P1的大小，m是P2的大小。隨着深度檢查和其他潛在的優化取決於你可用的樹木數據，這個人會被優化一點，但它通常仍然是O（n * m）。根據您的具體情況，這可能是唯一合理的方法。

如果你不是內存/存儲綁定，不介意有點複雜，我相信這可以通過在generalized suffix tree的幫助下減少到longest common substring問題來改進爲O（n + m）。關於這個類似問題的一些討論可以在here找到。也許當我有更多的時間時，我會回來編輯一個實現的更多細節。

Answer 6

如果給定兩棵樹的根，並且假設節點屬於同一類型，那麼爲什麼只是確定T2的根在T1中是不夠的？

我假設「給定樹T」意味着給定一個指向T根的指針和該節點的數據類型。

問候。

Answer 7

我認爲我們需要蠻力，但爲什麼在T1中找到T2的根後需要匹配樹。 它與當我們不應該找到樹是否相同時（不過，我們只需要比較整棵樹）

您給樹T1和T2，指針，而不是值。

如果節點T2（它是一個指針）出現在T1樹中。

然後Tree T2是T1的子樹。

---

編輯：

只有當它說，T2實際上是一個不同的樹的對象明智的，我們需要發現，如果在T1子樹，它等同於T2。

然後這不會工作。

我們別無選擇，只能去討論這裏已經討論過的解決方案。

Answer 8

讓我們說我們有T1作爲父樹，T2作爲一棵樹，它可能是T1的一個子樹。請執行下列操作。做出的假設是T1和T2是沒有任何平衡因子的二叉樹。

1）在T1中搜索T2的根。如果未找到，T2不是子樹。在BT中搜索元素將花費O（n）時間。

2）如果找到該元素，則從T2的節點根元素中找到對T1的預先遍歷。這將花費o（n）時間。做預先遍歷的T2以及。將花費O（n）時間。預訂遍歷的結果可以存儲到堆棧中。插入堆棧只需要O（1）。

3）如果兩個堆棧的大小不相等，則T2不是子樹。

4）從每個堆棧中彈出一個元素並檢查是否相等。如果發生不匹配，則T2不是子樹。

5）如果匹配的所有元素T2都是子樹。

Answer 9

我假設你的樹是不可變的樹木，所以你永遠不會改變任何樹（你不這樣做方案的說法set-car!），只是你是從葉子或從現有的樹木建造新的樹木。

然後我會建議保持在每個節點（或子樹）的散列碼節點的。在C語言中的說法，聲明樹-S是

struct tree_st { 
    const unsigned hash; 
    const bool isleaf; 
    union { 
    const char*leafstring; // when isleaf is true 
    struct { // when isleaf is false 
     const struct tree_st* left; 
     const struct tree_st* right; 
    }; 
    }; 
}; 

然後計算在施工時間的哈希，以及比較平等節點時，先比較他們的哈希值是否相等;大多數時候哈希代碼會有所不同（並且您不會比較內容）。

這裏是一個可能的葉結構功能：

struct tree_st* make_leaf (const char*string) { 
    assert (string != NULL); 
    struct tree_st* t = malloc(sizeof(struct tree_st)); 
    if (!t) { perror("malloc"); exit(EXIT_FAILURE); }; 
    t->hash = hash_of_string(string); 
    t->isleaf = true; 
    t->leafstring = string; 
    return t; 
} 

來計算散列碼是

unsigned tree_hash(const struct tree_st *t) { 
    return (t==NULL)?0:t->hash; 
} 

的函數來從兩個子樹sleft & sright構造一個節點的功能是

struct tree_st*make_node (const struct tree_st* sleft, 
          const struct tree_st* sright) { 
    struct tree_st* t = malloc(sizeof(struct tree_st)); 
    if (!t) { perror("malloc"); exit(EXIT_FAILURE); }; 
    /// some hashing composition, e.g. 
    unsigned h = (tree_hash(sleft)*313)^(tree_hash(sright)*617); 
    t->hash = h; 
    t->left = sleft; 
    t->right = sright; 
    return t; 
} 

com削減充分利用，如果哈希碼是不同的comparands是（兩棵樹tx & ty）的功能不同

bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) { 
    if (tx==ty) return true; 
    if (tree_hash(tx) != tree_hash(ty)) return false; 
    if (!tx || !ty) return false; 
    if (tx->isleaf != ty->isleaf) return false; 
    if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring); 
    else return equal_tree(tx->left, ty->left) 
       && equal_tree(tx->right, ty->right); 

}

大部分的時間tree_hash(tx) != tree_hash(ty)測試會成功，你將不必遞歸。

閱讀關於hash consing。

一旦你有這樣一個高效的基於散列的equal_tree函數，你可以使用其他答案（或手冊）中提到的技術。

Answer 10

之一平原方法是寫爲樹is_equal（）方法，做以下，

bool contains_subtree(TNode*other) { 
    // optimization 
    if(nchildren < other->nchildren) return false; 
    if(height < other->height) return false; 

    // go for real check 
    return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other)); 
} 

注意is_equal（）能夠通過使用哈希碼樹被優化。它可以通過樹的高度或孩子的數量或值的範圍作爲散列碼以簡單的方式完成。

bool is_equal(TNode*other) { 
    if(x != other->x) return false; 
    if(height != other->height) return false; 
    if(nchildren != other->nchildren) return false; 
    if(hashcode() != other->hashcode()) return false; 
    // do other checking for example check if the children are equal .. 
} 

當樹類似於一個鏈表，這將需要O（n）的時間。我們也可以在選擇孩子進行比較時使用一些啓發式方法。

bool contains_subtree(TNode*other) { 
    // optimization 
    if(nchildren < other->nchildren) return false; 
    if(height < other->height) return false; 

    // go for real check 
    if(is_equal(other)) return true; 
    if(left == NULL || right == NULL) { 
      return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other)); 
    } 
    if(left->nchildren < right->nchildren) { // find in smaller child tree first 
      return (left->contains_subtree(other)) || right->contains_subtree(other); 
    } else { 
      return (right->contains_subtree(other)) || left->contains_subtree(other); 
    } 
} 

另一種方法是既序列樹作爲串並發現如果所述第二串（從T2序列）是第一字符串的子串（從T1序列）。

以下代碼按預訂序列化。

void serialize(ostream&strm) { 
      strm << x << '('; 
      if(left) 
        left->serialize(strm); 
      strm << ','; 
      if(right) 
        right->serialize(strm); 
      strm << ')'; 
    } 

而且我們可以使用一些優化的算法，例如，Knuth–Morris–Pratt algorithm找到（可能在O（n）的時間）的子串的存在，並最終找到，如果一棵樹的其他子樹。

再次使用Burrows-Wheeler_transform可以壓縮字符串。並且有可能bzgrep在壓縮數據中搜索子字符串。

另一種方法是按樹的高度和數量排序樹中的子樹。

bool compare(TNode*other) { 
    if(height != other->height) 
     return height < other->height; 

    return nchildren < other->nchildren; 
} 

請注意，將會有O（n^2）個子樹。爲了減少數量，我們可以使用一些基於高度的範圍。例如，我們只能對高度爲1000到1500的子樹感興趣。

當生成排序後的數據時，可以在其中進行二進制搜索並查找它是否爲O（lg n）中的子集，時間（考慮到排序數據中沒有重複）。