N-ary 트리를 작성하십시오 (재귀 적으로?) 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

"폭 우선"당신이 (어떤 나무를 위해 구성 할 수있다) 보편적 이진 트리,보고 할 수 있습니다 곳 첫 아이 및 다음 - 형제 각 노드 링크. 당신은 이진 트리 (breath-first)를 만들고 n-ary로 변환 할 수 있습니다.

단일 문자열에서 한 생성을 생성하면 결과는 이웃 인에 의해 연결된 노드 목록에 저장됩니다. 차세대는 목록의 각 노드에서 한 세대를 구축하는 것입니다.

반복적으로 또는 반복적으로 반복을 사용하여 하나의 노드에 적용되는 일련의 호출을 조정합니다.

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"); 

그래서 몸를 들어, 다음 포인터를 다음하고 있고 (I 루프에서이 작업을 수행 할 것) 각 자녀에 대한 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); 
    } 
}