C - Binary Search Tree

Question

I have specific confusion in implementing function within the existing binary tree that stores pets' names and kinds, first what I've done:

Declarations[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);

Functions for adding nodes:

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;
}

(If you need more code I'll post it since there are more functions) The main confusion is how would I add all the pets with same names (different kinds) in the list within the same node and then find them just through typing the petname while retrieving their kind

Original task: Modify the Pet Club program so that all pets with the same name are stored in a list in the same node. When the user chooses to find a pet, the program should request the pet name and then list all pets (along with their kinds) having that name.

Suggestion from the book: *

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

You should already know about linked lists. Combine that knowledge with the tree you have here. Move the Item to a linked list and make Node store the list instead of Item directly.

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 can figure out the rest - every time you traverse a tree, you'll have extra step traversing the list. When adding an item, there will be 2 possibilities: either add new node with one item OR to add the item into existing node. That's exactly what your book said:

(...) 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.

First: create the list and make it work. Practice first on a separate ItemlistElement* (outside of the tree, you can even make the list and list traversal functions in another program). Then, modify your program to store Item in the lists, but using one-element list always. This should be very easy. Last move is to combine them both together. It's the step with least coding, but is most challenging. Do all the thinking before typing. Make copies of both projects while they still work (tree and linked list) to keep as reference if you get confused and program gets too messy.