查找兩棵樹是否同構

如果兩棵樹具有相似的結構，並且它們之間唯一的區別可能是，那麼它們的子節點可能會或可能不會被交換，因此可以稱它們爲同構。例如：查找兩棵樹是否同構

 4     4 
/ \   / \ 
    2  6 and 6  2 
/\ /\  /\ /\ 
1 3 5 7  1 3 7 5

下面的代碼應該是我在網上找到的正確的實現，但由於某種原因，它不適用於上述樹。我做錯了什麼？

#include <iostream> 
using namespace std; 

class Node{ 

public: 

    Node * left; 
    Node * right; 
    int val; 

    Node(int v){ 
     left = NULL; 
     right = NULL; 
     val = v;  
    } 
}; 

bool isIsomorphic(Node* n1, Node *n2) 
{ 
// Both roots are NULL, trees isomorphic by definition 
if (n1 == NULL && n2 == NULL) 
    return true; 

// Exactly one of the n1 and n2 is NULL, trees not isomorphic 
if (n1 == NULL || n2 == NULL) 
    return false; 

if (n1->val != n2->val) 
    return false; 

// There are two possible cases for n1 and n2 to be isomorphic 
// Case 1: The subtrees rooted at these nodes have NOT been "Flipped". 
// Both of these subtrees have to be isomorphic, hence the && 
// Case 2: The subtrees rooted at these nodes have been "Flipped" 
return 
(isIsomorphic(n1->left,n2->left) && isIsomorphic(n1->right,n2->right))|| 
(isIsomorphic(n1->left,n2->right) && isIsomorphic(n1->right,n2->left)); 
} 

int main() 
{ 
Node * na_4 = new Node(4); 
Node * na_2 = new Node(2); 
Node * na_6 = new Node(6); 
Node * na_1 = new Node(1); 
Node * na_3 = new Node(3); 
Node * na_5 = new Node(5); 
Node * na_7 = new Node(7); 

na_4->left = na_2; 
na_4->right = na_6; 

na_2->left = na_1; 
na_2->right = na_3; 

na_6->left = na_5; 
na_6->right = na_7; 


Node * nb_4 = new Node(4); 
Node * nb_6 = new Node(6); 
Node * nb_2 = new Node(2); 
Node * nb_1 = new Node(1); 
Node * nb_3 = new Node(3); 
Node * nb_7 = new Node(7); 
Node * nb_5 = new Node(5); 

nb_4->left = nb_6; 
nb_4->right = nb_2; 

nb_6->left = nb_1; 
nb_6->right = nb_3; 

nb_2->left = nb_7; 
nb_2->right = nb_5; 


if(isIsomorphic(na_4, nb_4)){ 
    cout << "Yes they are isomorphic" << endl; 
} 
else 
{ 
    cout << "No there are not isomorphic" << endl; 
} 

return 0; 
}

它輸出它們不是同構的。

來源

2014-01-31 user3256520

這些樹不是同構的，由提供here的定義：

兩棵樹被稱爲同構，如果他們中的一個可以從其他一系列翻轉來獲得，通過交換左，右，即兒童的多個節點。任何級別的任意數量的節點都可以讓他們的孩子交換。兩棵空樹是同構的。

如，在一棵樹，2有子1和3，但在其他的樹，2有兒童7和5

通過交換兩個孩子，你實際上交換他們的整個子樹，而不僅僅是那些節點，將所有其他的地方留下。

這兩個，例如，將是同構：

來源

2014-01-31 14:37:26 Dukeling

這些樹給出不同構。兩棵樹被稱爲同構當且僅當它們中的一個可以通過一系列翻轉而從其他中獲得，即通過交換許多節點的左右兒童。此外，任何級別的任意數量的節點都可以讓其子節點交換。

來源

2014-02-01 19:28:27

查找兩棵樹是否同構

回答

相關問題