在二叉樹中尋找同構性的算法

檢查兩個二叉樹的算法會是同構的嗎？我的代碼 -在二叉樹中尋找同構性的算法

boolean isIsomorphic(Root t1 , Root t2){ 
    if(t1==null || t2==null){ 
     return false; 
    } 

    if((t1.value == t2.value) && (isIsomorphic(t1.left,t2.right) && isIsomorphic(t1.right,t2.left))) { 
     return true 
    } 

    return false; 
}

來源

2012-04-27 Abhishek Choudhary

請正確定義樹的同構，或者引用一個定義。 – amit 2012-04-27 15:43:23

的wikipedia article for 'isomorphism'說：「如果兩個對象是同構的，則是由同構的保存，這是其中一個對象的真實任何財產，也是其他的真實。」

所以你的問題需要說明你是否在乎外形，數據，性能等

如果你關心的二叉樹的搜索行爲，你的算法是不正確的。請參閱What does it mean for two binary trees to be isomorphic?

檢查同構的最簡單方法是對兩棵樹進行按順序遍歷，在每一步之後檢查值。另一方面，如果您關心的是形狀和數據，@amits修復將爲您解決這個問題。但請注意，您可能稱之爲完全匹配。

最後，如果你只關心形狀，那麼你需要放下你的支票t1.value == t2.value

來源

2012-04-27 15:19:58

我認爲這不符合[圖同構]（http://en.wikipedia.org/wiki/Graph_isomorphism）的定義 – amit 2012-04-27 15:42:48

@amit我越查看，我越同意你關於這個問題沒有被足夠具體。請參閱http://tech-queries.blogspot.com/2010/04/isomorphic-trees.html，其中指出：「如果兩個二叉樹的形狀相同，則它們是同構的;存儲在節點中的值不影響是否兩棵樹是同構的「。我將更新我的帖子以區分同構的兩個衝突定義。 – 2012-04-27 15:47:10

從here：兩個棵樹S和T是準同構如果s可以通過交換左右的孩子被轉化入T s的一些節點。節點中的值對於確定準同構並不重要，只有形狀很重要。

該鏈接還提供了這種同構定義的代碼。

如果值是重要的，這種方法可能如下：

使用兩個隊列
執行每個樹的級別由級遍歷已完成在兩棵樹上添加一個級別之後，檢查隊列大小。如果不同，則報告'NOT ISOMORPHIC'
否則，對於第一個第一棵樹，將該級別中的所有節點出列爲一個集合。
對於第二棵樹，將每個節點出列並檢查它是否存在於集合中。
如果設置成員資格測試失敗，請報告「NOT ISOMORPHIC」。
如果我們完成所有級別，請報告ISOMORPHIC。

來源

2013-03-27 23:50:35 curryage

在二叉樹中尋找同構性的算法

回答

相關問題