我有一个作业，要求我创建一个二进制搜索树的结构，其中二进制搜索树的节点是另一个二进制搜索树。第一个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，我认为我没有这样做，但是我不知道该怎么做...
有什么建议么？
最佳答案
我在下面给出了一个示例实现，并在评论中解释了我是如何实现的。您应该能够使用我的想法来修改代码的工作方式。请注意，这不是一个完美的实现，我脑海中浮现出以下问题。
它是递归的，这意味着它可以处理的树的深度受目标计算机上堆栈大小的限制。您可以通过两种方式进行攻击：
进行迭代。也就是说，使用for / while循环而不是调用自身的函数-这将允许您的计算机内存处理尽可能多的节点（解决了问题）。
更新add_name_to_tree以处理balanced binary tree的插入（但这只是解决了问题，堆栈限制仍然存在）。
它无法处理名称完全相同但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;
}
关于c - 二进制搜索树内的二进制搜索树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6167466/