二叉树同构的判断

#include <iostream>
#include <cstdio>
using namespace std;

class Node{
public:
    char name;
    char left;
    char right;
};

Node* buildTree(int& root){
    int n;
    scanf("%d",&n);
    getchar();

    Node* Tree=new Node[n];
    bool check[n];
    for (int i=0; i<n; i++){
        check[i]= false;
    }
    if (n>0){
        for (int i=0; i<n; i++){
            scanf("%c %c %c\n",&Tree[i].name,&Tree[i].left,&Tree[i].right);
            if (Tree[i].left!='-'){
                Tree[i].left=Tree[i].left-'0';
                check[Tree[i].left]= true;
            } else {
                Tree[i].left=-1;
            }
            if (Tree[i].right!='-'){
                Tree[i].right=Tree[i].right-'0';
                check[Tree[i].right]= true;
            } else {
                Tree[i].right=-1;
            }
        }
        int j;
        for (j=0; j<n; j++){
            if (check[j]== false){
                break;
            }
        }
        root=j;
    } else {
        root=-1;
    }
    return Tree;
}

bool Isomorphic(Node* Tree1, Node* Tree2, int Tree1_Root, int Tree2_Root){
    if ((Tree1_Root==-1)&&(Tree2_Root==-1)){
        return true;
    }
    if (((Tree1_Root==-1)&&(Tree2_Root!=-1))||(Tree2_Root==-1)&&(Tree1_Root!=-1)){
        return false;
    }
    if (Tree1[Tree1_Root].name!=Tree2[Tree2_Root].name){
        return false;
    }
    if ((Tree1[Tree1_Root].left==-1)&&(Tree2[Tree2_Root].left==-1)){
        return Isomorphic(Tree1,Tree2,Tree1[Tree1_Root].right,Tree2[Tree2_Root].right);
    }
    if (((Tree1[Tree1_Root].left!=-1)&&(Tree2[Tree2_Root].left!=-1)) && Tree1[Tree1[Tree1_Root].left].name==Tree2[Tree2[Tree2_Root].left].name){
        return (Isomorphic(Tree1,Tree2,Tree1[Tree1_Root].left,Tree2[Tree2_Root].left) && Isomorphic(Tree1,Tree2,Tree1[Tree1_Root].right,Tree2[Tree2_Root].right));
    } else {
        return (Isomorphic(Tree1,Tree2,Tree1[Tree1_Root].left,Tree2[Tree2_Root].right) && Isomorphic(Tree1,Tree2,Tree1[Tree1_Root].right,Tree2[Tree2_Root].left));
    }

}

int main(){
    int Tree1_Root,Tree2_Root;
    Node* Tree1=buildTree(Tree1_Root);
    Node* Tree2=buildTree(Tree2_Root);

    if (Isomorphic(Tree1,Tree2,Tree1_Root,Tree2_Root)){
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}
分享