二进制搜索树内的二进制搜索树

Question

我有一个家庭作业，从我这里要求创建一个二叉搜索树的结构，其中二叉搜索树的节点是另一个二叉搜索树。第一个BST有学生的姓氏，另一个有姓氏和身份证。另外，如果某人与另一个学生姓氏相同，我不能创建另一个“姓氏”节点，但我必须在现有的“姓氏”节点内创建另一个“名字和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; 
    } 

对不起f或者我刚刚上传的庞大源代码，但如果没有这个，很难解释。

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

第一：我不得不为每个节点姓创建不同的名字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; 
}