Построить дерево N-arry (рекурсивно?) В C

Question

Мне нужно построить дерево, которое, начиная с строки, продолжает создавать новые узлы в соответствии с некоторыми правилами трансформации.

Например:

Получая строку aab И следующие два правила преобразования:

ab --> bba 
b --> ba 

Следующая дерево должны быть построены:

Обратите внимание, что сборка выполняется в широтном режиме. На каждом шаге я применяю все правила преобразования для каждой подстроки текущего узла, и это будут дети.

Вот то, что я до сих пор:

//Representing the n_ary tree 
typedef struct { 
    char *value; 
    struct t_children_list *children; 
} tree; 

typedef struct t_children_list { 
    tree *child; 
    struct t_children_list *next; 
} children_list; 

void initializeNode(tree **node, char *input) 
{ 
    if((*node = malloc(sizeof(tree))) == NULL) { abort(); } 
    (*node)->value = input; 
    (*node)->children = NULL; 
} 

void createChildrenList(children_list **children, tree *transformation) 
{ 
    if((*children = malloc(sizeof(children_list))) == NULL) { abort(); } 
    (*children)->child = transformation; 
    (*children)->next = NULL; 
} 

//Given a node, and a needle with a replacement. It will add the childrens to that node. 
void addTransformationsToNode(tree **origin, char *needle, char *replacement) 
{ 
    char *str = (*origin)->value; 
    for (char *p = str; *p != '\0'; p++) { 
     //Logic to find the value of str_... Not relevant 
      tree *transformation = NULL; 
      initializeNode(&transformation, str_); 
      //Add node to origin children list 
      // If node doesn't have children yet, create a new list 
      // Otherwise, add to end of children list 
      children_list *children = NULL; 
      createChildrenList(&children, transformation); 
      if ((*origin)->children == NULL) { 
       (*origin)->children = children; 
      } else { 
       children_list *current = (*origin)->children; 
       while (current->next != NULL) { 
        current = current->next; 
       } 
       current->next = children; 
      } 
     } 
    } 

    } 

void main() 
{ 
    // Create the tree 
    char *input = "aab"; 
    char *target = "bababab"; 
    tree *my_tree = NULL; 
    initializeNode(&my_tree, input); 

    addTransformationsToNode(&my_tree, "ab", "bba"); 
    addTransformationsToNode(&my_tree, "b", "ba"); 

} 

Это работает правильно для первого уровня. Но я ищу способ, которым я мог бы сделать то же самое для каждого узла и дочерних узлов этого узла. Итак, я начинаю с начала, нахожу все преобразования, а затем для трансформаций достижений делают то же самое. Я не вижу, как я мог бы сделать это рекурсивно ...

Спасибо!

Answer 1

Для «широта-первых», вы можете захотеть взглянуть на универсальном бинарном дереве (который может быть построен для любого дерева), где каждый узел ссылки на первого ребенка и следующего собрата. Вы можете построить двоичное дерево (сначала вдох), а затем преобразовать в n-ary.

Создание одного поколения из одной строки, вы помещаете результаты в список узлов, связанных next-sibling. Следующее поколение должно построить одно поколение из каждого узла в списке.

Итеративно или рекурсивно вы используете повторение для координации последовательности вызовов, которые применяются к одному узлу.

addTransformationsToNode(&my_tree, "ab", "bba"); 

addTransformationsToNode(&my_tree->children->child, "ab", "bba"); 
addTransformationsToNode(&my_tree->children->next->child, "ab", "bba"); 
addTransformationsToNode(&my_tree->children->next->next->child, "ab", "bba"); 

addTransformationsToNode(&my_tree->children->child->children->child, "ab", "bba"); 
addTransformationsToNode(&my_tree->children->child->children->next->child, "ab", "bba"); 

Так что для тела, вы следуете следующие указатели и вызов addTransformationsToNode для каждого ребенка (я хотел бы сделать это в цикле). Затем вы можете повторять и делать то же самое для детей каждого ребенка.

Вам понадобится дополнительный параметр для управления глубиной рекурсии: каким-то образом закончить древовидную конструкцию.

---

Я попытался написать функцию и все запутался. Я думаю, что ваша структура children_list излишне сложна. Я бы начал с чего-то гораздо более простого.

typedef struct tree { 
    char *val; 
    struct tree *first_child; 
    struct tree *next_sibling; 
} tree; 

tree *newnode(char *val){ 
    tree *node; 
    node = malloc(sizeof(*node)); 
    if (node) { 
     node->val = val; 
     node->first_child = NULL; 
     node->next_sibling = NULL; 
    } 
    return node; 
} 

void printtree(tree *node) { 
    if (node) { 
     if (node->val) 
      printf("%s, ", node->val); 
     printtree(node->next_sibling); 
     puts(""); 
     printtree(node->first_child); 
    } 
}