2018-04-09

二叉树同构的判断

#include 
#include 

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