Дерево двоичного поиска внутри дерева двоичного поиска

Question

У меня есть домашнее задание, которое просит от меня создать структуру дерева двоичного поиска, где его узел дерева двоичного поиска является другим деревом двоичного поиска.Первый BST имеет фамилии студентов, а второй имеет имена и идентификатор.Также, если у кого-то есть такая же фамилия с другим студентом, я не должен создавать другой узел «фамилия», но я должен создать внутри существующего узла «фамилия» другой узел «имя и идентификатор».Чтобы быть более конкретным:

typedef struct nameANDid{ //name and id nodes
    char first[20];
    int ID;
    struct nameANDid *nleft;
    struct nameANDid *nright;
}yohoho;
typedef struct node{  //surname nodes
   char last[20];  
   struct nameANDid yohoho;  
   struct node *left;
   struct node *right;
}node;

Моя основная проблема заключается в том, как создать отдельный узел nameANDid для каждого имени, которое я нашел, потому что с помощью следующего кода я создаю 2 BST один для фамилий и другой для имен, но яхотелось бы, например, чтобы: если у меня есть эти студенты

 Stallone Sylvester 11111111
 Stallone Noah      22222222
 Norris   Chuck     33333333
 Hogan    Hulk      44444444
 Hogan    Daniel    55555555

, я хочу хранить их так: .........

 Stallone Sylvester 11111111
          Noah      22222222
 Norris   Chuck     33333333
 Hogan    Hulk      44444444
          Daniel    55555555

Вместоэто я беру что-то вроде: ...........

 Stallone  Sylvester 11111111.
           Noah      22222222 
           Chuck     33333333
           Hulk      44444444 
           Daniel    55555555

 Norris  Sylvester 11111111.
           Noah      22222222 
           Chuck     33333333
           Hulk      44444444 
           Daniel    55555555
 Hogan    Sylvester 11111111.
           Noah      22222222 
           Chuck     33333333
           Hulk      44444444 
           Daniel    55555555

Я приведу здесь некоторые функции, чтобы быть более конкретными

Функция загрузки загружает именаиз текстового документа.

void loadData(struct node *temp){      
int i;
FILE *fp;
fp=fopen(FILENAME,"r");
if (fp == NULL) printf("File does not exist\n");
for (i=0; i<5; i++){                
    fscanf(fp,"%s",&temp->last);
    fscanf(fp,"%s",&temp->yohoho.first);
    fscanf(fp,"%d",&temp->yohoho.ID);                 
    top=add_node(top,temp);  //this function create a surname node        
    }        
fclose(fp);     
    printf("\n\nFile loaded\n");  
}

, где

        struct node temp;//just  a node pointer
        struct node *top=NULL; //shows the top of the tree

Функция addnode: ...

      struct node * add_node (struct node *top, struct node *temp){  
           struct node *newNode;  
           if (top == NULL){    
           newNode=(struct node *)malloc(sizeof(struct node));
           temp->left=NULL;
           temp->right=NULL;     
           if (memcpy(newNode,temp,sizeof(struct node)) == NULL){
               printf("Node addition failed\n");
               return NULL;}
           else {             
               topname=add_node_nameANDid(topname,&temp->yohoho); //Call the add_node_nameANDid to create a new name node in the other tree                           
               return newNode;}
            }
           else {   
               if (stricmp(temp->last,top->last) < 0){ //Insert node surname left
                     top->left=add_node(top->left,temp);}
               else if (stricmp(temp->last,top->last) == 0){         
                     topname=add_node_nameANDid(topname,&temp->yohoho);  //Call the add_node_nameANDid to create a new name node in the other tree   if i have the same surname        
               }
               else {
                     top->right=add_node(top->right,temp);           
               }
               return top;
             } 
             return NULL;
         }

А функция add_node_nameANDid () похожа напредыдущая функция изменена, но некоторые переменные изменены:

      struct nameANDid * add_node_nameANDid (struct nameANDid *topname, struct nameANDid *temp2){
        struct nameANDid *newNode_nameANDid;     
        if (topname == NULL){ 
            newNode_nameANDid=(struct nameANDid *)malloc(sizeof(struct nameANDid));
            temp2->nleft=NULL;
            temp2->nright=NULL;
            if (memcpy(newNode_nameANDid,temp2,sizeof(struct nameANDid)) == NULL){
                   printf("Node addition failed\n");
                   return NULL;}
            else {                 
                   return newNode_nameANDid;}
            }
        else {   
             if (stricmp(temp2->first,topname->first) <= 0){       
                  topname->nleft=add_node_nameANDid(topname->nleft,temp2);}
        else {         
                  topname->nright=add_node_nameANDid(topname->nright,temp2);}  
        return topname;
        } 
     return NULL;
    }

Извините за огромный исходный код, который я только что загрузил, но без этого было бы очень трудно объяснить.

Я думаю, что у меня естьдве проблемы, но у меня нет знаний, чтобы решить их.

ПЕРВЫЙ: у меня естьe создать разные имена BST для каждого узла фамилии, и я думаю, что я не делаю этого, но я не знаю, как это сделать ...

Есть предложения?

Answer 1

Ниже я привел пример реализации этого, прокомментировал, чтобы объяснить, как я подошел к этому.Вы должны быть в состоянии использовать мои идеи, чтобы изменить способ работы вашего кода.Обратите внимание, что это не идеальная реализация, изо всех сил я вижу следующие проблемы:

1. Его рекурсив , что означает, что глубина дерева, с которым он может справиться,ограничен размером стека на целевой машине.Есть два способа атаковать это:
   1. Сделать это итеративным .То есть, используйте циклы for / while вместо вызова функций - это позволит использовать столько узлов, сколько может обработать память вашей машины (исправит проблему).
   2. Обновление add_name_to_tree для обработки вставокдля сбалансированного двоичного дерева (но это только помогает решить проблему, ограничение стека все еще там).
2. Он не может работать с двумя людьми с одинаковымимя, но разные идентификаторы - после добавления первого человека в дерево все последующие люди с таким же именем игнорируются.

Я оставлю это в качестве упражнения для вас, чтобы справиться с этими ситуациями.

---

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

/* a single struct type for storing all tree elements */
typedef struct _node
{
    char name[50];
    int id;
    struct _node *subname;
    struct _node *left;
    struct _node *right;
} node;

/* creates a new node structure for the specified name and id */
node *create_node(const char *name, int id)
{
    node *newNode = (node*)malloc(sizeof(node));
    memset(newNode, 0, sizeof(*newNode));

    newNode->id = id;
    strncpy(newNode->name, name, sizeof(newNode->name));

    return newNode;
}

/* inserts the name/id pair into the tree specified by root.
   note that root is passed as a pointer to a pointer, so that
   it can accept NULL if no tree exists yet, and return to the 
   caller the node the node that contains the name.  Note that
   id is ignored if "name" already exists, i'll leave it as an
   excersice for you to handle situations with the same name
   with multiple id's */
node *add_name_to_tree(node **root, const char *name, int id)
{
    if (*root == NULL)
    {
        *root = create_node(name, id);
        return *root;
    }

    const int cmp = strcmp(name, (*root)->name);

    if (cmp < 0)
    {
        return add_name_to_tree(&(*root)->left, name, id);
    }
    else if (cmp > 0)
    {
        return add_name_to_tree(&(*root)->right, name, id);
    }
    else
    {
        return *root;
    }
}

/* adds the specified first/last name and id combo to the tree
   specified by root */
node *add_name(node *root, const char *first, const char *last, int id)
{
    /* this call will return the node that holds the last name,
       we can then use its "subname" tree root to insert the first name */
    node *last_node = add_name_to_tree(&root, last, 0);

    /* use the "subname" of the node that stores the last name as the 
       root of the tree that stores first names */
    add_name_to_tree(&last_node->subname, first, id);
    return root;
}

/* just to demonstrate why I use the same node type for first/last names,
   its because it allows you to support any number of names, see
   below - an add function that adds people with a middle name to the tree
   */
node *add_with_middle_name(node *root, const char *first, 
                           const char *middle, const char *last, int id)
{
    node *last_node = add_name_to_tree(&root, last, 0);
    node *mid_node = add_name_to_tree(&last_node->subname, middle, 0);
    add_name_to_tree(&mid_node->subname, first, id);
    return root;
}

/* recursively traverse the name tree, printing out the names */
void print_names(node *names, int level)
{
    const int indent = 10;

    if (names == NULL)
    {
        printf("\n");
    }

    if (names->left)
    {
        print_names(names->left, level);
    }

    if (names->subname)
    {
        printf("%*c %s \n", (indent * level), ' ', names->name);
        print_names(names->subname, level + 1);
        printf("\n");
    }
    else
    {
        printf("%*c %-*s %d\n", 
               (indent * level), ' ', 
               indent, names->name, names->id);
    }

    if (names->right)
    {
        print_names(names->right, level);
    }
}

int main()
{
    node *names = NULL;

    names = add_name(names, "Sylvester", "Stallone", 11111111);
    names = add_name(names, "Noah", "Stallone", 22222222);
    names = add_name(names, "Chuck", "Norris", 33333333);
    names = add_name(names, "Hulk", "Hogan", 44444444);
    names = add_name(names, "Daniel", "Hogan", 55555555);

    names = add_with_middle_name(names, "Peter", "Michael", 
                                 "Zachson", 66666666);

    print_names(names, 0);

    return 0;
}