Arbre de recherche binaire dans l'arbre de recherche binaire

Question

J'ai un devoir qui demande à moi de créer une structure d'arbre de recherche binaire où son nœud de l'arbre de recherche binaire est un autre arbre de recherche binaire. Le premier BST a les noms de famille des étudiants et l'autre a les prénoms et l'id. Aussi, si quelqu'un a le même nom de famille avec un autre étudiant, je ne dois pas créer un autre noeud "nom de famille" mais je dois créer à l'intérieur du noeud "nom de famille" existant un autre noeud "prénom et identifiant". Pour être plus précis:

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; 

Mon principal problème est de savoir comment créer un noeud nameANDid différent pour chaque prenom j'ai trouvé car avec le code suivant je crée 2 BST un pour les noms de famille et un autre pour les noms mais je voudrais être comme par exemple: Si j'ai ces étudiants

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

Je veux les stocker comme ceci: .........

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

au lieu de cela, je ta ke quelque chose comme: ...........

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 

Je mettrai ici quelques fonctions afin d'être plus précis

La fonction de charge charge les noms d'un document txt.

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

où

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

La fonction addnode est: ...

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

Et la fonction add_node_nameANDid() est comme la fonction précédente, mais il a changé certaines variables:

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

Désolé f ou l'énorme code source que je viens de télécharger mais il serait très difficile d'expliquer sans cela.

Je pense que j'ai deux problèmes mais je n'ai pas les connaissances pour les résoudre.

PREMIER: Je dois créer différentes prenom BST pour chaque noeud de nom et je pense que je ne fais pas ça, mais je ne sais pas comment faire ...

Toutes les suggestions?

Answer 1

J'ai donné un exemple de mise en œuvre de ce qui suit, commenté pour expliquer comment je l'ai abordé. Vous devriez pouvoir utiliser mes idées pour modifier le fonctionnement de votre code. Notez que ce n'est pas une mise en œuvre parfaite, du haut de ma tête, je peux voir les problèmes suivants.

1. Son récursif, ce qui signifie la profondeur de l'arbre, il peut gérer est limité par la taille de la pile sur la machine cible. Vous pouvez l'attaquer de deux façons:
   1. Rendez-le itératif. Autrement dit, utilisez les boucles for/while à la place des fonctions s'appelant elles-mêmes - cela permettrait de gérer autant de nœuds que la mémoire de votre machine (corrige le problème).
   2. Mise à jour add_name_to_tree pour gérer les insertions pour un balanced binary tree (mais cela aide simplement le problème, la limite de la pile est toujours là).
2. Il ne peut pas gérer deux personnes ayant exactement le même nom, mais des ID différents: après l'ajout de la première personne à l'arborescence, toutes les personnes suivantes du même nom sont ignorées.

Je vais le laisser comme un exercice pour vous de gérer ces situations.

---

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