1

在存储宠物名称和种类的现有二叉树中实现函数时，我有特定的困惑，首先我做了什么：

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

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

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

书中的建议：*

对于另一种可能的变化，请考虑 Nerfville 宠物俱乐部。该示例按名称和种类对树进行了排序，因此它可以将猫山姆放在一个节点中，将狗山姆放在另一个节点中，将山羊山姆放在第三个节点中。然而，你不可能有两只叫山姆的猫。另一种方法是仅按名称对树进行排序。单独进行该更改将只允许一个 Sam，无论种类如何，但您可以将 Item 定义为结构列表，而不是单个结构。Sally 第一次出现时，程序会创建一个新节点，然后创建一个新列表，然后将 Sally 和她的种类添加到列表中。下一个出现的 Sally 将被定向到同一节点并添加到列表中。

*

4

1 回答 1

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;

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

(...) 然后您可以将 Item 定义为结构列表，而不是单个结构。Sally 第一次出现时，程序会创建一个新节点，然后创建一个新列表，然后将 Sally 和她的种类添加到列表中。下一个出现的 Sally 将被定向到同一节点并添加到列表中。

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

于 2012-05-10T11:29:16.040 回答