將鏈接列表集成到樹結構中

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