一千萬個為什麽

搜索

如何檢查一個非二叉樹是否是另一個的子樹

我正在處理樹,我需要知道如何檢查一個非二叉樹是否是另一個子樹。

這些樹可以有n個節點和n個層次,而孩子們的順序並不重要。我只是想知道樹是否是另一棵樹的子樹

對我來說,問題是如何做一個遞歸,並將兩個樹同時與遞歸進行比較。

為此我創建了一個示例來演示我想要做什麽。

我知道樹和我的根;我試圖在rails上做ruby,但是知道我只是想知道一個偽代碼或邏輯。

enter image description here enter image description here

有人可以幫助我嗎?

謝謝

最佳答案

我會嘗試使用散列樹或 Merkle Tree 的想法:

散列樹或Merkle樹是每個非葉節點所在的樹   用其子節點的標簽的散列標記。哈希樹   是有用的,因為它們允許有效和安全地驗證   大數據結構的內容。

See also Hashing a Tree Structure

轉載註明原文: 如何檢查一個非二叉樹是否是另一個的子樹