Question

(IN C)

Write the code to manage a Binary Tree. Each node in the binary tree includes an integer value and string. The binary tree is sorted by the integer value. The functions include:

• Insert into the binary tree. This function will take in as parameters: the root of the tree, the integer value, and the string. Note that this function requires you to create the node.

• Find a node by integer value: This function takes in two parameters: the root of the tree and the integer value to find. If it finds the integer value, return the node. If it is unable to find the integer value, return NULL.

• Traverse the tree. This function takes in two parameters: the root of the tree, and a flag to indicate the order: preorder, inorder, or postorder. The flags are defined as macros:

#define PREORDER 0

#define INORDER 1

#define POSTORDER 2

Answer 1

/*
 *  C - Program
 *  BST - Insertion and Searching
 */

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

#define PREORDER 0
#define INORDER 1
#define POSTORDER 2
#define S 50

struct Node
{ 
  int ID;
  char str[30];
  struct Node *left;
  struct Node *right; 
}; 
   
struct Node *newNode(int id, char *str) 
{ 
  struct Node *temp =  (struct Node *) malloc(sizeof(struct Node)); 
  
  temp->ID = id;
  strcpy(temp->str, str);
  temp->left = temp->right = NULL;
  
  return temp; 
} 

void preOrder(struct Node *root) 
{ 
  if (root != NULL) 
  { 
    printf("%d\t%s\n", root->ID, root->str);
    preOrder(root->left); 
    preOrder(root->right);
  } 
}

void postOrder(struct Node *root)
{
  if (root != NULL)
  {
    preOrder(root->left);
    preOrder(root->right);
    printf("%d\t%s\n", root->ID, root->str);
  }
}

void inOrder(struct Node *root)
{
  if (root != NULL)
  {
    preOrder(root->left);
    printf("%d\t%s\n", root->ID, root->str);
    preOrder(root->right);
  } 
}

struct Node* insert(struct Node* root, int id, char *str)
{
  if (root == NULL)
    return newNode(id, str); 

  if (id < root->ID) 
    root->left  = insert(root->left, id, str); 
  else if (id > root->ID) 
    root->right = insert(root->right, id, str);    

  return root; 
}

int search(struct Node* root, int id) 
{ 
  if (root->ID == id)
  {
    printf("Found: %d, %s\n", root->ID, root->str);
    return 1; 
  }
  
  if (root->ID < id) 
    return search(root->right, id); 
  
  return search(root->left, id);
}

void traverse(struct Node* root, int flag)
{
  printf("ID\tName\n");
  switch (flag)
  {
    case 0  :   preOrder(root);
                break;
    case 1  :   inOrder(root);
                break;
    case 2  :   postOrder(root);
                break;
  }
}
   
int main() 
{
  int idNum;
  struct Node *root = NULL; 
  
  root = insert(root, 30, "John");
  insert(root, 20, "Bill");
  insert(root, 10, "Jennifer");
  insert(root, 40, "Sophia");
  
  traverse(root, INORDER);
  printf("\n");

  printf("Enter ID number to search: ");
  scanf("%d", &idNum);
  
  if (!search(root, idNum))
    printf("Record not found\n");

  return 0; 
}
/*  Program ends here */