Связанные списки, интегрированные в древовидную структуру

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

я делаю основную функцию печати для печати узлов дерева. Я также изменил прототип функций, чтобы облегчить жизнь:)

Надеюсь, это поможет.

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

Answer 2

Надеюсь, я правильно понял вашу проблему ...

Я бы посоветовал вам добавить еще один уровень косвенности в список ... вы можете создать структуру List, которая будет содержать голову, хвост и т. Д.списка и добавьте список (или указатель на него) вместо ListNode * в структуру TreeNode.Таким образом, вы могли бы иметь List* getList(TreeNode*) и иметь функции, которые работают непосредственно с возвращаемым списком (на мой взгляд, это чище).Это будет означать, что ваша реализация списка будет полностью отделена от вашего дерева, что означает, что вы можете легко использовать ее вне этого проекта.

Альтернатива состоит в том, чтобы полностью инкапсулировать список в структуре 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* в качестве параметра.Это то, что вы пытаетесь сделать?