Question

(in C) Binry Srch tree problem:

1. Need to read words from a “in” text file and build a binary search tree. (1^st line will state number of elements)

2. strcmp() can be used to compare data and decide were to insert a new node.

3. The output should include:

-print the tree as in-order traversal.

-print the character count in the tree.

-Ask user input for a word to search, print an output if either found or not. (typing exit will exit program)

-print height of tree

Sample in.txt:

13

lion

koala

coyote

chicken

rat

roach

moose

shark

puma

fox

wolf

duck

horse

//Please use following struct and function//

struct tree_node {

int data;

struct tree_node* lft;

struct tree_node* rght;

};

//even nodes//

int prntEvn(struct tree_node *current_ptr) {

if (currnt_ptr != NULL) {

if (currnt_ptr->data % 2 == 0)

printf(“%d “, current_ptr->data);

prntEvn(current_ptr->lft);

prntEvn(current_ptr->rght);

}

}

Answer 1

//C program

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

typedef struct tree_node {
   char data[10];
   struct tree_node* lft;
   struct tree_node* rght;

}node;

node* createnode(char data[]){
   node* newnode=(node*) malloc(sizeof(node));
   strcpy(newnode->data , data);
   newnode->lft=NULL;
   newnode->rght=NULL;
   return newnode;
}

node* insertnode(node*tree,char data[]){
   if(!tree)return createnode(data);
  
   if(strcmp(tree->data,data) < 0){
   tree->rght= insertnode(tree->rght,data);
   }
   else if(strcmp(tree->data,data) > 0){
   tree->lft=insertnode(tree->lft,data);
   }
   return tree;
}

void inorder(node*tree){
   if(!tree)return;
   inorder(tree->lft);
   printf("%s\n",tree->data);
   inorder(tree->rght);
}

int countCharacters(node *tree){
   if(tree == NULL)return 0;
   return strlen(tree->data) + countCharacters(tree->lft) + countCharacters(tree->rght);
}

int height(node * tree){
   if(tree == NULL)return 0;
   int lheight = height(tree->lft);
   int rheight = height(tree->rght);
  
   if(lheight > rheight) return lheight + 1;
   return rheight+1;
}

int search(node*tree , char name[]){
   if(tree == NULL) return 0;
   if(strcmp(tree->data , name) == 0)return 1;
   if(strcmp(tree->data , name) < 0) return search(tree->rght , name);
   return search(tree->lft , name);
}

int main(){
   FILE* input;
   input = fopen("in.txt","r");
   char name[10];
   node*bst = NULL;
  
   int n ,i;
   fscanf(input , "%d" ,&n);
  
   for(i=0;i<n;i++){
       fscanf(input , "%s" ,name);
       bst = insertnode(bst , name);
   }
  
   printf("In-order traversal\n");
   inorder(bst);
  
   printf("\nThe character count in the tree : %d\n",countCharacters(bst));
  
   printf("Enter name to search : ");
   scanf("%s",name);
  
   if(search(bst , name)){
       printf("%s found in tree\n",name);
   }
   else{
       printf("%s not found in tree\n",name);
   }
  
   printf("Height of tree : %d\n",height(bst));
   fclose(input);
   return 0;
}

//sample output

In-order traversal chicken coyote duck fox horse koala lion moose puma rat roach shark wolf The character count in the tree : 60 Enter name to search : horse horse found in tree Height of tree : 5 Process exited after 16.02 seconds with return value o Press any key to continue