将链接列表集成到树结构中

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

希望我理解正确的话您的问题...

我建议你增加一个间接的另一个层次的列表...您可以创建举行的头一个列表结构，尾等等，并将List（或指向一个的）指针添加到TreeNode结构中，而不是ListNode *。这样你就可以拥有一个List* getList(TreeNode*)并且具有直接在返回列表上运行的函数（在我看来这更清洁）。这意味着您的列表实现将与您的树完全分离，这意味着您可以在此项目之外轻松使用它。

另一种方法是将List完全封装在TreeNode结构体中，这正是我认为你想要做的。要添加到列表中，您可能需要一个功能addNumber(TreeNode*, char*)，其他列表操作功能将以类似方式完成。他们只需要一个引用或指向提供对列表访问权的TreeNode的指针。

做你想做什么，你已经可以访问ListNode*如果你有一个TreeNode*：

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

你可以很容易地跳进采取TreeNode*作为参数的函数这一点。这是你想要做的吗？

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; 
}