在二叉树中寻找同构性的算法

检查两个二叉树的算法会是同构的吗？我的代码 -在二叉树中寻找同构性的算法

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

在二叉树中寻找同构性的算法

回答

相关问题