C - 二叉搜索树

Question

我在存储宠物名称和种类的现有二叉树中实现功能时特别困惑，首先是我所做的:

声明[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;
}

(如果您需要更多代码，我会发布它，因为有更多功能)主要的困惑是我如何将所有具有相同名称(不同种类)的宠物添加到同一节点的列表中，然后通过在检索它们的种类时键入宠物名称来找到它们

原始任务:修改宠物俱乐部程序，使所有同名的宠物都存储在同一个节点的列表中。当用户选择寻找宠物时，程序应请求宠物名称，然后列出所有具有该名称的宠物(及其种类)。

书中的建议:*

For another possible variation, consider the Nerfville Pet Club. The example ordered the tree by both name and kind, so it could hold Sam the cat in one node, Sam the dog in another node, and Sam the goat in a third node. You couldn't have two cats called Sam, however. Another approach is to order the tree just by name. Making that change alone would allow for only one Sam, regardless of kind, but you could then define Item to be a list of structures instead of being a single structure. The first time a Sally shows up, the program would create a new node, then create a new list, and then add Sally and her kind to the list. The next Sally that shows up would be directed to the same node and added to the list.

*

Answer 1

您应该已经了解链表。将这些知识与你这里的树结合起来。将 Item 移动到链表中，让 Node 存储链表而不是直接存储 Item。

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;

您可以找出其余部分 - 每次遍历树时，您都会有额外的步骤遍历列表。添加项目时，将有两种可能性:添加带有一项的新节点或将项目添加到现有节点中。这正是你的书所说的:

(...) you could then define Item to be a list of structures instead of being a single structure. The first time a Sally shows up, the program would create a new node, then create a new list, and then add Sally and her kind to the list. The next Sally that shows up would be directed to the same node and added to the list.

首先:创建列表并使其发挥作用。先在一个单独的ItemlistElement*上练习(在树之外，你甚至可以在另一个程序中制作列表和列表遍历函数)。然后，修改您的程序以将 Item 存储在列表中，但始终使用单元素列表。这应该很容易。最后一步是将它们结合在一起。这是编码最少但最具挑战性的步骤。在打字之前做所有的思考。在两个项目仍在工作时复制它们(树和链表)，以便在您感到困惑和程序变得太困惑时作为引用。