将链表集成到树结构中

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结构体来保存List的头、尾等，并在TreeNode结构体中添加一个List(或指向List的指针)而不是ListNode*。这样，您就可以拥有一个List* getList(TreeNode*)，并拥有直接对返回的列表进行操作的函数(在我看来，这更简洁)。这将意味着你的列表实现将与你的树完全分离，这意味着你可以很容易地在这个项目之外使用它。

另一种选择是将List完全封装在TreeNode结构体中，这就是我认为您正在尝试做的。要添加到列表中，您可能需要一个函数addNumber(TreeNode*, char*)，其他列表操作函数也可以类似地完成。它们只需要一个指向TreeNode的引用或指针，TreeNode提供对列表的访问。

要做你想做的事情，如果你有TreeNode*，你已经可以访问ListNode*:

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("========================================================================= DONEnn");
    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========================================================================= DONEnn");
    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; 
}