트리 구조로 통합 된 링크 된 목록

Question

저는 트리 구조를 만들고 있습니다.이 트리 구조의 각 노드는 데이터 (숫자)의 링크 된 목록을 포함합니다. 이제, 내 머리 속에는 링크 된 링크들 각각이 연관되어있는 머리를 가져야한다는 것을 의미합니다. 그래서 그 안에있는 데이터에 액세스하고 반복하여 해당 TreeNode의 모든 숫자를 표시 할 수 있습니다. 문제는, 벽돌 벽에 부딪 쳤고, 내가 지금있는 곳에서 어떤 단계를 취해야하는지 정말로 알지 못합니다 (아래 참조). 각각의 연결된 목록에 대해 머리를 반환해야합니다. 각 TreeNode에 대해서는 확실하지 않습니다.

다음은 지금까지 가지고있는 코드입니다. 현재 노드에 이름을 추가하고 목록에 숫자를 추가하지만 목록에 여러 숫자를 추가하면 어떤 단계로 나아갈 지 확신 할 수 없습니다. 다음 테이크를 수행 한 다음 항목을 반환하여 내 (시간대에) 인쇄 기능이 반복되도록합니다. 난 당신이 목록에 간접의 또 다른 레벨을 추가하는 것이 제안

이 ... 당신이 머리를 개최 목록 구조체를 만들 수

내가 제대로 문제를 이해 한 희망

typedef struct ListNode { 
char   *number; 
struct ListNode *next; 
}ListNode; 

typedef struct TreeNode { 
char   *name; 
ListNode  *numbers; 
struct TreeNode *left; 
struct TreeNode *right; 
}TreeNode; 

TreeNode* AddNode(TreeNode *, char *, char *); 
TreeNode* SearchTree(TreeNode *root, char *search); 
void N_Print(TreeNode *root); 

int main(void) { 
char my_string[50], name[25], number[25]; 
TreeNode *root = NULL; 
while ((fgets(my_string, 50, stdin)) != NULL) { 
    if (my_string[0] == '.') 
     break;  
sscanf(my_string, "%s %s", name, number); 
root = AddNode(root, name, number); 
} 
return 0; 
} 

TreeNode* AddNode(TreeNode *root, char *name, char *number) { 
int comparison; 
if (root == NULL) { 
    root = (TreeNode *)malloc(sizeof(TreeNode)); 
    root->numbers = (ListNode *)malloc(sizeof(ListNode)); 
    root->name = strdup(name); root->numbers->number = strdup(number); 
    root->left = root->right = NULL; 
    root->numbers->next = NULL; 
}else if ((comparison = strcmp(name, root->name)) < 0) 
    root->left = AddNode(root->left, name, number); 
else if (comparison > 0) { 
    root->right = AddNode(root->right, name, number); 
} else if (comparison == 0) { 
    root->numbers->number = strdup(number); 
    root->numbers->next = NULL; 
} 
return root; 
} 

Answer 1

..., 꼬리 ListNode * 대신 List (또는 하나에 대한 포인터)를 추가하여 TreeNode 구조체에 추가하십시오. 그런 식으로 List* getList(TreeNode*)을 가질 수 있으며 반환 된 목록에서 직접 작동하는 함수를 가질 수 있습니다 (제 의견으로는 더 깨끗합니다). 이렇게하면 목록 구현이 트리와 완전히 분리되므로이 프로젝트 외부에서 쉽게 사용할 수 있습니다.

다른 방법은 TreeNode 구조체에 List를 전체적으로 캡슐화하는 것입니다. 이것이 내가하려는 것입니다. 목록에 추가하려면 함수 addNumber(TreeNode*, char*)이 필요하며 다른 목록 조작 함수도 비슷하게 수행됩니다. 목록에 대한 액세스를 제공하는 TreeNode에 대한 참조 또는 포인터가 필요합니다.

TreeNode* tn = something; 
for(ListNode* ln = tn->numbers; ln != NULL; ln = ln->next) { 
    // do something here (print, etc.) with ln->number 
} 

쉽게 매개 변수로 TreeNode*을 복용하는 기능으로이 팝업 수 : 당신이 TreeNode*가있는 경우에 당신이하려는 일을하려면

, 당신은 이미 ListNode*에 액세스 할 수 있습니다. 이게 너가하려는거야?

Answer 2

나는 트리 노드를 인쇄하는 기본적인 인쇄 기능을 만든다. 나는 또한 삶을 더 쉽게하기 위해 함수 프로토 타입을 수정했다 :)

나는 이것이 도움이되기를 희망한다.

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



typedef struct ListNode ListNode; 
typedef struct TreeNode TreeNode; 


struct ListNode { 
    char   *number; 
    ListNode  *next; 
}; 

struct TreeNode { 
    char   *name; 
    ListNode  *numbers; 
    TreeNode  *left; 
    TreeNode  *right; 
}; 

TreeNode *new_tree_node(char *name); 
ListNode *new_list_node(char *number); 

void ListNode_AddNode(ListNode **plist, char *number); 
void TreeNode_AddNode(TreeNode **proot, char *name, char *number); 

void ListNode_Print(ListNode *list); 
void TreeNode_Print(TreeNode *root); 
TreeNode * TreeNode_FindNode(TreeNode * root,char *name); 

/*________________________________________________________________________________________________ 
*/ 
int main(void) { 
    char my_string[50], name[25], number[25]; 
    TreeNode *root = NULL; 
    while ((fgets(my_string, 50, stdin)) != NULL) { 
     if (my_string[0] == '.') 
      break;  
     sscanf(my_string, "%s %s", name, number); 
     TreeNode_AddNode(&root, name, number); 
    } 

    printf("PRINTING TREENODE:\n"); 
    TreeNode_Print(root); 
    printf("========================================================================= DONE\n\n"); 

    printf("PRINTING (jaguar's numbers) :\n"); 

    TreeNode *jaguar = TreeNode_FindNode(root,"jaguar"); 
    if(jaguar) 
     ListNode_Print(jaguar->numbers); 
    else 
     printf("jaguar node not found"); 

    printf("\n========================================================================= DONE\n\n"); 
    return 0; 
} 
/*________________________________________________________________________________________________ 
*/ 
TreeNode *new_tree_node(char *name){ 
    TreeNode *tree = calloc(1,sizeof(TreeNode)); 

    if (tree) { 
     tree->name=strdup(name); 
    } 
    return tree; 
} 

ListNode * new_list_node(char *number){ 
    ListNode *list = calloc(1,sizeof(ListNode)); 
    if (list) { 
     list->number=strdup(number); 
    } 
    return list; 
} 

void ListNode_AddNode(ListNode **plist, char *number){ 
    ListNode *list = *plist; 
    if(!list) { 
     list = new_list_node (number); 
     *plist = list; 
    } 
    else{ 
     ListNode_AddNode(&list->next,number); 
    } 
    return ; 
} 

void TreeNode_AddNode(TreeNode **proot, char *name, char *number) { 

    TreeNode *root = *proot; 

    if (!root) { 
     root = new_tree_node(name); 
     *proot = root; 
    }else { 
     int comparison = strcmp(name, root->name); 

     if (comparison < 0){ 
      TreeNode_AddNode(&root->left, name, number); 
      return; 
     } 
     if (comparison > 0) { 
      TreeNode_AddNode(&root->right, name, number); 
      return; 
     } 
    } 

    ListNode_AddNode (&root->numbers,number); 
    return ; 
} 

void ListNode_Print(ListNode *list){ 
    if(!list) return; 
    printf("%s ",list->number); 
    ListNode_Print (list->next); 
} 

void print_tatbs(int n){ 
    while(n){ 
     n--; 
     putchar('\t'); 
    } 
} 
void TreeNode_Print(TreeNode *root){ 
    static int tree_deep = 0; 
    if(!root) 
     return; 
    print_tatbs(tree_deep); 
    printf("Node: %s, Numbers: ",root->name); 
    ListNode_Print(root->numbers); 
    printf("\n"); 


    if(root->left){ 
     tree_deep++; 
     print_tatbs(tree_deep); 
     printf("Left:\n"); 
     TreeNode_Print(root->left); 
     tree_deep--; 
    } 
    if(root->right){ 
     tree_deep++; 
     print_tatbs(tree_deep); 
     printf("Right:\n"); 
     TreeNode_Print(root->right); 
     tree_deep--; 
    } 
} 


TreeNode * TreeNode_FindNode(TreeNode * root,char *name){ 

    if(!root) return root; 

    int comparison = strcmp(name, root->name); 

    if (comparison < 0) 
     return TreeNode_FindNode(root->left, name); 

    if (comparison > 0) 
     return TreeNode_FindNode(root->right, name); 

    return root; 
}