Untitled

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// MurmurOAAT32 hash function
unsigned int MurmurOAAT32(char *key) {
    unsigned int h = 3323198485u;
    for (; *key; ++key) {
        h ^= *key;
        h *= 0x5bd1e995;
        h ^= h >> 15;
    }
    return h;
}

// Function to convert unsigned int to string
void unsigned_int_to_string(unsigned int num, char *str) {
    sprintf(str, "%u", num);
}

// Function to merge and hash two values in the binary tree
unsigned int merge_and_hash(unsigned int a, unsigned int b) {
    unsigned int sum = a + b;
    char buffer[11]; // enough to hold a 32-bit unsigned int
    unsigned_int_to_string(sum, buffer);
    return MurmurOAAT32(buffer);
}

// Definition of tree node
typedef struct Node {
    unsigned int data;
    struct Node *left;
    struct Node *right;
} Node;

// Function to create a new tree node
Node* create_tree_node(unsigned int data) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

// Recursive function to build the Merkle tree and collect hash values
Node* build_merkle_tree(Node** leaves, int n) {
    if (n == 1) {
        return leaves[0];
    }

    int new_n = (n + 1) / 2;
    Node** new_leaves = (Node**)malloc(new_n * sizeof(Node*));

    for (int i = 0; i < new_n; i++) {
        if (2 * i + 1 < n) {
            unsigned int combined_hash = merge_and_hash(leaves[2 * i]->data, leaves[2 * i + 1]->data);
            Node* parent = create_tree_node(combined_hash);
            parent->left = leaves[2 * i];
            parent->right = leaves[2 * i + 1];
            new_leaves[i] = parent;
        } else {
            unsigned int adjusted_hash = merge_and_hash(leaves[2 * i]->data, leaves[2 * i]->data);
            Node* parent = create_tree_node(adjusted_hash);
            parent->left = leaves[2 * i];
            new_leaves[i] = parent;
        }
    }

    Node* root = build_merkle_tree(new_leaves, new_n);
    free(new_leaves);

    return root;
}

// Definition of the correct tree node
typedef struct TreeNode {
    unsigned long long value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Function to create a new correct tree node
TreeNode* createTreeNode(unsigned long long value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to free the correct tree
void freeTree(TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// Function to compare two trees and find the wrong data string
void compareTrees(Node* root1, TreeNode* root2, char** data, int* dataIndex, int level) {
    if (root1 == NULL && root2 == NULL) {
        return;
    }

    if (root1 == NULL || root2 == NULL) {
        return;
    }

    if (root1->data != root2->value) {
        printf("%-15u != %llu\n", root1->data, root2->value);
        if (root1->left && root2->left) {
            compareTrees(root1->left, root2->left, data, dataIndex, level + 1);
        }
        if (root1->right && root2->right) {
            compareTrees(root1->right, root2->right, data, dataIndex, level + 1);
        }
    } else {
        printf("%-15u == %llu\n", root1->data, root2->value);
        if (level == 0) { // This is a leaf node
            printf("wrong data %s\n", data[*dataIndex]);
            (*dataIndex)++;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);

    char **strings = (char **)malloc(n * sizeof(char *));
    Node **leaves = (Node **)malloc(n * sizeof(Node *));
    unsigned int *hashes = (unsigned int *)malloc(n * sizeof(unsigned int));

    for (int i = 0; i < n; i++) {
        strings[i] = (char *)malloc(101 * sizeof(char)); // 100 chars + null terminator
        scanf("%s", strings[i]);
        hashes[i] = MurmurOAAT32(strings[i]);
        leaves[i] = create_tree_node(hashes[i]);
    }

    Node *root = build_merkle_tree(leaves, n);

    int m;
    scanf("%d", &m);

    TreeNode **currentLevel = (TreeNode**)malloc(sizeof(TreeNode*));
    TreeNode **nextLevel;
    int *levelSizes = (int*)malloc(m * sizeof(int));

    int k;
    scanf("%d", &k);
    if (k != 1) {
        fprintf(stderr, "根節點必須只有一個。\n");
        return 1;
    }
    unsigned long long value;
    scanf("%llu", &value);
    TreeNode* root2 = createTreeNode(value);
    currentLevel[0] = root2;
    levelSizes[0] = k;

    for (int i = 1; i < m; ++i) {
        scanf("%d", &k);
        levelSizes[i] = k;
        nextLevel = (TreeNode**)malloc(k * sizeof(TreeNode*));

        for (int j = 0; j < k; ++j) {
            scanf("%llu", &value);
            nextLevel[j] = createTreeNode(value);
        }

        int parentIndex = 0;
        for (int j = 0; j < levelSizes[i - 1]; ++j) {
            if (parentIndex >= k) break;
            currentLevel[j]->left = nextLevel[parentIndex++];
            if (parentIndex >= k) break;
            currentLevel[j]->right = nextLevel[parentIndex++];
        }

        free(currentLevel);
        currentLevel = nextLevel;
    }

    int dataIndex = 0;
    compareTrees(root, root2, strings, &dataIndex, 0);

    freeTree(root2);
    free(currentLevel);
    free(levelSizes);

    free(leaves);
    free(hashes);

    return 0;
}