Question

Read a list of names from a file. Insert the names into a binary search tree that is a little different from what we discussed in class. For this tree, the left side will contain the larger values and the right side will contain the smaller values. In essence, it is the exact opposite of a normal binary search tree. Our tree will also be able to store duplicate names. Aside from a left and a right pointer for each node, we will have another pointer variable that will point to a linked list. Each node in the linked list will contain the additional duplicate name. Once the nodes have been inserted, give the user a chance to search for a name. Display your search path as you are searching through the tree and indicate if the name was found. If the name is found and there are duplicates, indicate how many duplicates of the name exist in the tree. Here is an example: Given the following names in the file: Dan, Phil, Angela, Ayesha, Kai, Zia, Troy, Troy, Troy. Dan Your tree would look like the following: 1. Ayesha The Names in blue are in the linked list. For the search, if the user is looking for Troy, you would display the search path as such: Dan, Phil, Zia, Troy. You would also indicate that there are 3 iterations of Troy Hints: When comparing strings, you would use the strcmp function which does a case sensitive compare. You can also do strcmpi which doesn't care about the case. You can assume that we don't care about the case, which means that Dan and dan are both the same names. Also, the names will have to go into a char array, such as char name[30]. You can assume that names will not exceed 30 characters.

Answer 1

The C code for the given question is as follows:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node //node to store the linked list details
{
    char name[30];
    struct node *next;
};

struct BinaryTree //BinaryTree to store the details of each node in the binary tree
{
    char name[30];
    struct node *names;
    struct BinaryTree *left;
    struct BinaryTree *right;
};

struct node *createTreeNode(char *n) //function to create new Tree node
{
    struct BinaryTree* temp = (struct BinaryTree *)malloc(sizeof(struct BinaryTree)); // allocate space for the node using malloc function
    strcpy(temp->name,n); //copy the name sent as parameter to the name variable in the Tree node
    temp->names = NULL; //assign names as null since Tree node will be created only for first occurrence of a name
    temp->left = NULL; //left pointer is assigned NULL
    temp->right = NULL; //right pointer is assigned NULL
    return temp;//return the created node
}

struct BinaryTree* insert(struct BinaryTree* root, char * name)
{
    if (root == NULL) //if the root is null it means that the tree is empty
        return createTreeNode(name); //therefore create a new node

    if(strcmpi(name,root->name)>0) //if the given name value is higher in order than root name value, we need to put it to the left side
        root->left = insert(root->left, name);// hence call the insert function recursively to insert node to the left side of root node
    else if(strcmpi(name,root->name)<0) //if the given name value is lower in order than root name value, we need to put it to the right side
        root->right = insert(root->right, name);// hence call the insert function recursively to insert node to the right side of root node
    else //otherwise it means that the name value is already present in the tree. Hence linked list associated with the tree node has to be updated
    {
        struct node* temp = (struct node *)malloc(sizeof(struct node)); //allocate memory for a node using malloc() function
        strcpy(temp->name,name); //copy the name sent as parameter to the name variable in the node
        temp->next = NULL; //make next pointer NULL
        struct node *t = root->names; // we need to attach it to the node with same name value as input given
        //Hence consider the names list of the node
        if(t==NULL)//if it is null
        {
            root->names = temp; //attach the newly created list node to the tree node
        }
        else
        {
            while(t->next!=NULL) // parse the list until we get the last list node
            {
                t = t->next;
            }
            t->next = temp; //attach the newly created list node to the end of the list
        }
    }
    return root; // return the root node
}

void searchPath(struct BinaryTree *root,char *name) //function to search for a name in the tree
{
    int count;
    if(root==NULL)
        printf("Name not found\n");
    else
    {
        printf("%s",root->name); // print the root node value everytime to generate the search path
        if(strcmpi(name,root->name)>0) // if name to be searched is larger than the root name
        {
            printf("-->"); // followed by --->
            searchPath(root->left, name); //search to the left
        }
        else if(strcmpi(name,root->name)<0) // if name to be searched is smaller than the root name
        {
            printf("-->"); //followed by --->
            searchPath(root->right, name); //search to the right
        }
        else // else it means it is found
        {
            count = 1; // 1 corresponds to value present in the node key
            struct node *t = root->names; //extract the root->names list
            while(t!=NULL) //parse the list to count the number of occurrences
            {
                count++; //increase count everytime until the end of list is reached
                t = t->next;
            }
            if(count>1) //if count is greater than 1, print the number of occurrences
                printf("\nThe count of occurrence for %s is %d\n",name,count);
        }
    }
}

int main()
{
    char ch;
    char namelist[200],search[30];//string arrays
    int i=0;
    struct BinaryTree *root = NULL;//create an empty binary tree
    FILE *fp = fopen("names.dat","r"); //open the file containing names in read mode
    ch = fgetc(fp);
    while(ch!=EOF)// read character from the file until the end of file is reached
    {
        namelist[i] = ch; // add the characters to the string namelist
        ch = fgetc(fp);
        i++; //increment index counter
    }
    namelist[i]='\0'; //terminate the string with null character
    char *filenames = strtok(namelist,","); // use strtok() to tokenize the namelist based on ','
    while(filenames!= NULL ) { // for each of the name found in the file
        root = insert(root,filenames); //insert it to the binary tree
        filenames = strtok(NULL, ","); // find the next name
    }
    printf("Enter the name you want to search: "); //ask for user to enter the name to be searched
    gets(search);
    printf("The search Path for %s is: ",search);
    searchPath(root,search); // call the searchPath function to display the path and occurrence
    fclose(fp); //close the file
    return 0;
}

#include<stdio.h> #include<stdlib.h> #include<string.h> struct node //node to store the linked list details char name[30]; struct node *next; struct BinaryTree //BinaryTree to store the details of each node in the binary tree оо очоп вмроо о о п о оноо у о п во ме char name[30]; struct node *names; struct BinaryTree *left; struct BinaryTree *right; struct node *createTreeNode (char *n) //function to create new Tree node struct BinaryTree* temp = (struct BinaryTree *) malloc(sizeof(struct BinaryTree)); // al strcpy (temp->name, n); // copy the name sent as parameter to the name variable in the Tree temp->names = NULL; //assign names as null since Tree node will be created only for firs temp->left = NULL; //left pointer is assigned NULL temp->right = NULL; //right pointer is assigned NULL return temp;//return the created node struct BinaryTree* insert (struct BinaryTree* root, char * name)

" if (root == NULL) //if the root is null it means that the tree is empty return createTreeNode (name); //therefore create a new node " " " " " if(strcmpi (name, root->name) >0) //if the given name value is higher in order than root name value, we need to put it root->left = insert (root->left, name); // hence call the insert function recursively to insert node to the left else if(strcmpi (name, root->name) <0) //if the given name value is lower in order than root name value, we need to pu root->right = insert (root->right, name); // hence call the insert function recursively to in else //otherwise it means that the name value is already present in the tree. Hence linked list associated with the the rig fu struct node* temp = (struct node *) malloc(sizeof(struct node)); //allocate memory for a node using www strcpy (temp->name, name); // copy the name sent as parameter to the name variable in the node temp->next = NULL; //make next pointer NULL struct node *t = root->names; // we need to attach it to the node with same name value as input given //Hence consider the names list of the node if(t==NULL) //if it is null root->names = temp; //attach the newly created list node to the tree node else while(t->next!=NULL) // parse the list until we get the last list node t = t->next; In t->next = temp; //attach the newly created list node to the end of the list n return root; // return the root node

void searchPath(struct BinaryTree *root, char *name) //function to search for a name in the tree { int count; if(root==NULL) printf("Name not found\n"); else printf("%s", root->name); // print the root node value wwwwww to generate the search path if(strcmpi (name, root->name) >0) // if name to be searched is larger than the root name printf("-->"); // followed by ---> searchPath (root->left, name); // search to the left else if(strcmpi (name, root->name) <0) // if name to be searched is smaller than the root name O co Join W NO coon W NO coonWN printf("-->"); //followed by ---> searchPath (root->right, name); // search to the right else // else it means it is found count = 1; // i corresponds to value present in the node key struct node *t = root->names; //extract the root->names list while(t !=NULL) //parse the list to count the number of occurrences until the end of list is reached count++; //increase count t = t->next; if (count>l) //if count is greater than 1, print the number of occurrences printf("\nThe count of occurrence for $s is %d\n", name, count);

WN int main() char ch; char namelist [200], search [30]; //string arrays int i=0; struct BinaryTree root = NULL; // create an empty binary tree FILE *fp = fopen("names.dat", "r"); //open the file containing names in read mode ch = fgetc (fp); while (ch!EOF) // read character from the file until the end of file is reached 0 0 0 0 0 0 0 0 0 OOOOOOOOOHHHH namelist[i] = ch; // add the characters to the string mm ch = fgetc (fp); i++; //increment index counter io Coin i W NOC00) en W NOCO ww based on www namelist[i]='\0'; //terminate the string with null character char *filenames = strtok (namelist,", "); // use www to win the w while (filenames != NULL) { // for each of the name found in the file root = insert (root, filenames); //insert it to the binary tree filenames - strtok (NULL, ","); // find the next name printf ("Enter the name you want to search: "); //ask for user to enter the name to be searched gets (search); printf("The search Path for $s is: ", search); searchPath (root, search); call the searchPath function to display the path and occurrence fclose(fp); close the file return 0; 116 H 118 119

OUTPUT:

Enter the name you want to search: Kai The search Path for kai is: Dan-->Phil.->Kai Process returned @ (@xo_execution time : 1.950 S Press any key to continue.

Enter the name you want to search: Troy The search Path for Troy is: Dan-->Phil-->Zia-->Troy The count of occurrence for Troy is 3 Process returned o (Oxo) execution time : 2.502 s Press any key to continue.