Клонирование n-арного дерева в C

Question

Моя структура поддерживает указатели родителя, потомка и родного брата вместе с другими переменными данных.

struct semNode {
    struct semNode *child;
    struct semNode *parent;
    struct semNode *sibling;
    int data;
    int tag;
};

Если мне нужно клонировать точное дерево того же типа данных, как мне go узнать об этом? рекурсивным или итеративным способом.

Я планировал использовать рекурсивный подход, в котором я перебираю дерево по порядку, а затем добавляю к указателям, но я не уверен, сработает ли этот подход. Пожалуйста, помогите мне.

Answer 1

Вы можете клонировать дерево с помощью простой рекурсивной функции:

struct semNode {
    struct semNode *child;
    struct semNode *parent;
    struct semNode *sibling;
    int data;
    int tag;
};

void free_semNode(struct semNode *node) {
    if (node) {
        free_semNode(node->sibling);
        free_semNode(node->child);
        free(node);
    }
}

struct semNode *clone_semNode(struct semNode *node, struct semNode *parent) {
    struct semNode *new_node = malloc(sizeof(*new_node));
    if (new_node != NULL) {
        new_node->data = node->data;
        new_node->tag = node->tag;
        new_node->parent = parent;
        new_node->child = NULL;
        new_node->sibling = NULL;
        if (node->child) {
            new_node->child = clone_semNode(node->child, new_node);
            if (new_node->child == NULL) {
                free_semNode(new_node);
                return NULL;
            }
        }
        if (node->sibling) {
            new_node->sibling = clone_semNode(node->sibling, parent);
            if (new_node->sibling == NULL) {
                free_semNode(new_node);
                return NULL;
            }
        }
    }
    return new_node;
}

Все дерево можно клонировать с помощью clone_semNode(tree, NULL);, а поддерево можно клонировать с помощью clone_semNode(node, node->parent);, но как исходное поддерево, так и клонированное поддерево будет указывать на того же родителя, что может вызвать трудности для правильного управления памятью.