c - C-二进制搜索树

我在现有的二叉树中实现函数的具体困惑是存储宠物的名字和种类，首先我做了什么：
声明[tree.h]：

typedef struct item
{
    char petname[20];
    char petkind[20];
} Item;

#define MAXITEMS 10

typedef struct node
{
    Item item;
    struct node * left;    /* pointer to right branch  */
    struct node * right;   /* pointer to left branch   */
} Node;

typedef struct tree
{
    Node * root;           /* pointer to root of tree  */
    int size;              /* number of items in tree  */
} Tree;


void InitializeTree(Tree *ptree);

bool TreeIsEmpty(const Tree * ptree);

bool TreeIsFull(const Tree * ptree);

int TreeItemCount(const Tree * ptree);

bool AddItem(const Item * pi, Tree * ptree);

bool InTree(const Item * pi, const Tree * ptree);

bool DeleteItem(const Item * pi, Tree * ptree);

void Traverse (const Tree * ptree, void (* pfun)(Item item));

void DeleteAll(Tree * ptree);

添加节点的功能：

typedef struct pair {
    Node * parent;
    Node * child;
} Pair;


bool AddItem(const Item * pi, Tree * ptree)
{
     Node * new_node;

     if(TreeIsFull(ptree))
     {
          fprintf(stderr,"Tree is full\n");
          return false;
     }


          if(SeekItem(pi,ptree).child!=NULL)
          {
               fprintf(stderr,"Attempted to add duplicate item\n");
               return false;
          }

     new_node=MakeNode(pi);

     if(new_node==NULL)
     {
          fprintf(stderr,"Couldn't create node\n");
          return false;
     }

     ptree->size++;

     if(ptree->root==NULL)
          ptree->root=new_node;
     else
          AddNode(new_node,ptree->root);

     return true;
}

static void AddNode(Node * new_node, Node * root)
{
     if((strcmp(new_node->item.petname, root->item.petname))==0)
     {
          if(root->same==NULL)
               root->same=new_node;
          else
               AddNode(new_node, root->same);
     }
     else
     {
          if(ToLeft(&new_node->item,&root->item))
          {
               if(root->left==NULL)
                    root->left=new_node;
               else
                    AddNode(new_node, root->left);
          }
          else if(ToRight(&new_node->item,&root->item))
          {
               if(root->right==NULL)
                    root->right=new_node;
               else
                    AddNode(new_node, root->right);
          }
          else
          {
               fprintf(stderr,"location error in AddNode()\n");
               exit(1);
          }
     }
}

static bool ToLeft(const Item * i1, const Item * i2)
{
     int comp;

     if((comp=strcmp(i1->petname,i2->petname))<0)
          return true;
     else if(comp==0)
          return true;
     else
          return false;
}

static bool ToRight(const Item * i1, const Item * i2)
{
     int comp;

     if((comp=strcmp(i1->petname,i2->petname))>0)
          return true;
     else if(comp==0)
          return true;
     else
          return false;
}

static Node * MakeNode(const Item * pi)
{
     Node * new_node;

     new_node=(Node *) malloc(sizeof Node);

     if(new_node!=NULL)
     {
          new_node->item=*pi;
          new_node->left=NULL;
          new_node->right=NULL;
          new_node->same=NULL;
     }
     return new_node;
}

（如果你需要更多的代码，我会发布它，因为有更多的函数）
主要的困惑是，我如何在同一个节点的列表中添加具有相同名称（不同种类）的所有宠物，然后在检索它们的种类时通过键入petname找到它们
原始任务：
修改宠物俱乐部程序，使所有同名宠物存储在同一节点的列表中。当用户选择寻找宠物时，程序应该请求宠物的名字，然后列出所有有这个名字的宠物（连同它们的种类）。
书中的建议：
*
对于另一个可能的变化，考虑Nerfville宠物俱乐部。这个
示例按名称和种类对树进行排序，以便它可以容纳Sam
猫在一个节点，狗在另一个节点，山羊在另一个节点
第三个节点。不过，你不可能有两只叫山姆的猫。另一个
方法是按名称对树排序。独自改变
不管怎样，只允许一个山姆，但你可以
将项定义为结构列表，而不是单个
结构。当Sally第一次出现时，程序会创建一个
新建节点，然后创建一个新列表，然后将Sally和她的同类添加到
名单。下一个出现的莎莉也会
节点并添加到列表中。
*

最佳答案

你应该已经知道链表了。把这些知识和你这里的树结合起来。将项目移动到链接列表，并使节点存储列表而不是直接存储项目。

typedef struct itemlistElement
{
    Item item;
    struct itemlistElement* nextItem;    /* pointer to next item on list */
} ItemlistElement;

typedef struct node
{
    ItemlistElement* listOfItems; /* pointer to first element of a linked list of Item */
    struct node * left;    /* pointer to right branch  */
    struct node * right;   /* pointer to left branch   */
} Node;

你可以算出剩下的——每次你遍历一棵树，你就会有额外的步骤遍历列表。添加一个项时，有2种可能：要么添加一个新的节点，要么将该项添加到现有节点中。
你的书就是这么说的：
（…）然后可以将项定义为结构列表，而不是
是一个单一的结构。当莎莉第一次出现的时候
会创建一个新节点，然后创建一个新列表，然后添加Sally
她对名单很好。下一个出现的莎莉是
指向同一节点并添加到列表中。
首先：创建列表并使其工作。首先在一个单独的ItemlistElement*上练习（在树之外，您甚至可以在另一个程序中创建list和list遍历函数）。
然后，修改程序以将Item存储在列表中，但始终使用一个元素列表。这应该很容易。
最后一步是把两者结合起来。这是编码最少的一步，但最具挑战性。打字前要先想清楚。在两个项目仍在工作时复制它们（树和链接列表），以便在您感到困惑和程序太混乱时作为参考。

关于c - C-二进制搜索树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10532775/