树的同构

szz123 / 2024-10-22 / 原文

建树

数组模拟链表(静态链表)

程序框架

1.题意及建树
2.建树及同构判别

#include <iostream>
#include <cstring> // for memset
using namespace std;

const int N = 10;

struct TreeNode {
    char data;
    int left;
    int right;
} T1[N], T2[N];

typedef struct TreeNode BiTree;

int BuildTree(BiTree T[]) {
    int root = -1;
    int check[N] = {0}; // 初始化check数组为0
    int n;
    cin >> n;

    if (n > 0) {
        for (int i = 0; i < n; i++) {
            char cl, cr;
            cin >> T[i].data >> cl >> cr; // 直接读入字符

            // 处理左孩子
            if (cl != '-') {
                T[i].left = cl - '0';
                check[T[i].left] = 1; // 标记此节点为子节点
            } else {
                T[i].left = -1; // 没有左孩子
            }

            // 处理右孩子
            if (cr != '-') {
                T[i].right = cr - '0';
                check[T[i].right] = 1; // 标记此节点为子节点
            } else {
                T[i].right = -1; // 没有右孩子
            }
        }

        // 找到根节点
        for (int i = 0; i < n; i++) {
            if (!check[i]) {
                root = i; // 第一个未标记为子节点的就是根节点
                break;
            }
        }
    }
    return root;
}

bool Isomorphic(int r1, int r2) { // 参数是两个根
    if (r1 == -1 && r2 == -1) return true; // 两个都为空
    if ((r1 == -1 && r2 != -1) || (r1 != -1 && r2 == -1)) return false; // 一个为空一个不为空
    if (T1[r1].data != T2[r2].data) return false; // 数据不相同

    // 递归检查同构性
    if (T1[r1].left == -1 && T2[r2].left == -1) {
        return Isomorphic(T1[r1].right, T2[r2].right); // 仅有右孩子
    }

    if (T1[r1].left != -1 && T2[r2].left != -1 && T1[T1[r1].left].data == T2[T2[r2].left].data) {
        // 左孩子相同
        return Isomorphic(T1[r1].left, T2[r2].left) && Isomorphic(T1[r1].right, T2[r2].right);
    } else {
        // 左右孩子互换情况
        return Isomorphic(T1[r1].left, T2[r2].right) && Isomorphic(T1[r1].right, T2[r2].left);
    }
}

int main() {
    int root1 = BuildTree(T1);
    int root2 = BuildTree(T2);

    if (Isomorphic(root1, root2)) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}