c++ - 判断两棵树是否同构

Question

如果两棵树具有相似的结构，则它们可以称为同构的，它们之间的唯一区别可能是它们的子节点可以交换也可以不交换。例如:

     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;
}

它输出它们不是同构的。

Answer 1

根据您提供的定义，这些树不是同构的。还出现了特定于二叉树的类似定义 here :

Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.

问题是在一棵树中，2 有 child 1 和 3，但在另一棵树中，2 有 child 7 和 5。

通过“交换”两个子树，您实际上需要交换它们的整个子树，而不仅仅是单个节点，并将所有其他子树留在原处。

例如，这两个是同构的:

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

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

---

注意:一些同构的定义忽略了顶点标签(至少对于更一般的graph isomorphism，原则上同样的想法也适用于树)。根据这些定义，问题中给出的树将是同构的。我相信如果您忽略顶点标签，上面给出的定义仍然适用。对于图同构(与考虑根的树同构相反)，这将不起作用，因为一般图没 Root过的概念(通过上述技术生成的树仍然是图同构的，但并非所有图同构都可以使用这种技术生产)。