c - 二分搜索树内的二分搜索树

Question

我有一个作业要求我创建一个二叉搜索树的结构，其中二叉搜索树的节点是另一个二叉搜索树。第一个 BST 包含学生的姓氏，另一个包含名字和 ID。此外，如果某人与另一个学生具有相同的姓氏，我不得创建另一个“姓氏”节点，但我必须在现有的“姓氏”节点内创建另一个“名字和 ID”节点。更具体地说:

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

为了更具体，我将在这里放置一些函数

加载函数从 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");  
}

哪里

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

抱歉，我刚刚上传了巨大的源代码，但如果没有这个，将很难解释。

我认为我有两个问题，但我没有解决它们的知识。

首先:我必须为每个姓氏节点创建不同的名字 BST，我认为我不这样做，但我不知道该怎么做......

有什么建议吗？

Answer 1

我在下面给出了一个示例实现，并进行了评论以解释我是如何实现这一点的。您应该能够使用我的想法来修改代码的工作方式。请注意，它不是一个完美的实现，我立即就看到了以下问题。

1. 它是递归的，这意味着它可以处理的树深度受到目标机器上堆栈大小的限制。有两种方法可以解决这个问题:
   1. 使其迭代。也就是说，使用 for/while 循环而不是调用自身的函数 - 这将允许您的机器内存可以处理尽可能多的节点(解决问题)。
   2. 更新 add_name_to_tree 以处理 balanced binary tree 的插入操作(但这只是解决了问题，堆栈限制仍然存在)。
2. 它无法处理名称完全相同但 ID 不同的两个人 - 将第一个人添加到树后，所有后续同名的人都会被忽略。

我将把它作为练习留给您来处理这些情况。

<小时/>

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