once again, i need help to meet the deadline at work. I have provided  
95%(most)  of the program already (the header file, driver file and main   
program). It runs with a few errors on my microsoft visual  C++   
compiler. Please read the question well and what i need done to the   
program .I would be most grateful if I could have the program Before  
the end of friday 05/16/2003  
  
  
Specifications:  
  
In this project we want to create a program that presents an  
interactive menu to a user (on a console or terminal) and permits the  
user to build and manipulate a Binary Search Tree.  The menu should  
look like the following diagram and it should provide all the options  
shown:  
  
===========================================================================  
   Interactive BST Simulator  
    Main Menu  
(1) Create a new BST  
  
(2) Populate the nodes of the BST  
  
(3) Display the BST on the console  
  
(4) Traverse the BST (Inorder)  
  
(5) Traverse the BST (Preorder)  
  
(6) Traverse the BST (Postorder)  
  
(7) Traverse the BST (Level Order)  
  
(8) Optimize the BST  
  
(9) Search the BST for a node occurence  
  
(10) Delete a node from the BST  
  
(11) Delete the entire BST  
  
(12) Exit the program  
============================================================================  
  
Input your selection ===>  
  
The node data for the BST should be defined in the following manner:  
  
#define WORDLEN 50  
  
struct ELEMENT  
{ int wordcount;                  /* number of times the word was  
loaded in the tree*/  
  int wordlength;    /* length of the word*/  
};  
  
typedef struct BSTNODE *pBST;  
typedef struct BSTNODE  
{ char wordkey[WORDLEN+1];  
  struct ELEMENT NodeData;  
  pBST leftchild;  
  pBST rightchild;  
} BST;  
  
  
When you display the BST onto the user's console, you should make it  
look like a BST.  When you traverse the BST, you should print all the  
node contents (one line per node), where wordcount is the number of  
times the user attempted to insert the wordkey in the BST and  
wordlength is the string length of the wordkey.  
   
                                John  
  
                  Billy                         Lenny  
  
               
Adam                       Bob              Kilroy                   Louie  
  
  
When you print the BST it should appear on the user’s console in the  
following manner( you only need to display the node key values(which  
are string values):  
  
                               John  
  
                  Billy                         Lenny  
  
               
Adam                       Bob              Kilroy                   Louie  
  
  
Be sure to incorporate the appropriate user-friendliness, robustness,  
error-checking, and security in this program. Also make sure that your  
program  does not leak memory. You should check to make sure that the  
proper sequence of user events has occurred: for example, the user  
should not be able to execute options 3 through 11 before the  
successfully execute option 1 and 2 in that order,  
  
You should submit your C standard API program source code (as a  
separate custom header file, function library source file, and driver  
program source file) and a report showing the following information.  
  
1) screen print of your main menu  
2) screen print of BST with depth 5  
3) screen print of the same BST, except after you optimize it.  
  
  
I have a very good shell::Please make changes to this code as you  
wish.  
  
/********************************************************/  
                                  */  
/*                                                      */  
/* NOTE: List of some things you need to fix:           */  
/*    1. This BST shell is NOT hacker proof!            */  
/*    2. This BST shell is NOT robust!                  */  
/*    3. This BST shell is NOT C Standard API.          */  
/*    4. This BST shell is NOT complete -- you'll need  */  
/*       to code the delete node, delete tree, and print*/  
/*       tree functions.                                */  
/*                                                      */  
/********************************************************/  
#include <stdio.h>  
#include <stddef.h>  
#include <stdlib.h>  
#include <math.h>  
#include <string.h>  
  
#define BUFSIZE     80  
#define WORDLEN  80  
#define SUCCESS  0  
#define FAILURE  -1  
#define TRUE  1  
#define FALSE  0  
#define SCRNSIZE 26  
#define STARTX  48  
#define STARTY  2  
#define IS_FULL(ptr) (!(ptr))  
#define IS_EMPTY(ptr) (!(ptr))  
  
  
/* ADT BST object declarations */  
typedef int BOOL;  
  
struct ELEMENT  
{ int wordlength;  
 int wordcount;  
};  
  
typedef struct BSTNODE *pBST;  
typedef struct BSTNODE  
{ char wordkey[WORDLEN];  
 struct ELEMENT nodedata;  
 pBST left_child;  
 pBST right_child;  
} BST;  
  
  
/* ADT function prototypes */  
pBST CreateBST(void);  
pBST PopulateBST(void);  
int  InsertNode(pBST *, char *);  
void InorderTraversal(pBST);  
void VisitNode(pBST);  
void PerformSearch(pBST);  
BOOL BSTSearch(pBST, char *);  
pBST ModifiedBSTSearch(pBST, char *);  
void PrintBST(pBST, short, short);  
void DeleteBST(pBST);  
pBST DeleteNode(pBST);  
pBST OptimizeBST(pBST);  
  
/* Screen Manipulation functions */  
int  DisplayMainMenu(int *);  
int  ProcessMenuSelection(void);  
void ClearScreen(void);  
void HoldScreen(void);  
void nomemory(void);  
  
  
/* Screen Display and Menu functions */  
  
int DisplayMainMenu(int *selection)  
{  
 int result=0;  
 int returncode=SUCCESS;  
 char buffer[BUFSIZE]=" ";  
  
 ClearScreen();  
  
 printf("\t\t  INTERACTIVE BST SIMULATOR\n");  
 printf("\t\t===========================================\n");  
 printf("\t\t|        MAIN MENU                        |\n");  
 printf("\t\t| (1) Create a new BST                    |\n");  
 printf("\t\t| (2) Populate the nodes of the BST       |\n");  
 printf("\t\t| (3) Display the BST on the console      |\n");  
 printf("\t\t| (4) Optimize the BST                    |\n");  
 printf("\t\t| (5) Seach the BST for a node occurrence |\n");  
 printf("\t\t| (6) Traverse the BST (Inorder)          |\n");  
 printf("\t\t| (7) Delete a node from the BST          |\n");  
 printf("\t\t| (8) Delete the entire BST               |\n");  
 printf("\t\t| (9) Exit the program                    |\n");  
 printf("\t\t===========================================\n");  
 printf("\t\tEnter your selection =>");  
  
 fgets(buffer, BUFSIZE, stdin);  
 result=sscanf(buffer, "%d", selection);  
  
 if (result != 1)  
 { *selection = 0;  
  returncode=FAILURE;  
 }  
   
 return returncode;  
}  
  
  
int ProcessMenuSelection(void)  
{  
 int repeat_flag=FALSE;  
 int returncode=SUCCESS;  
 int result=0;  
 int selection=0;  
 pBST root=NULL;  
  
 do  
 { returncode=DisplayMainMenu(&selection);  
    
  switch(selection)  
  {  
   case 1:  
    if(root)   
     DeleteBST(root);  
  
    root=CreateBST();  
  
    printf("\n\t\tBST Created.\n");  
    HoldScreen();  
  
    repeat_flag=TRUE;  
    break;  
  
   case 2:  
    root=PopulateBST();  
    repeat_flag=TRUE;  
    break;  
  
   case 3:  
    ClearScreen();  
  
    if(IS_EMPTY(root))  
    { fflush(stdout);  
     printf("\nTree is empty.\n");  
    }  
    else  
     PrintBST(root, STARTX, STARTY);  
  
    HoldScreen();  
    repeat_flag=TRUE;  
    break;  
  
   case 4:  
    root=OptimizeBST(root);  
    repeat_flag=TRUE;  
    break;  
  
   case 5:  
    PerformSearch(root);  
    repeat_flag=TRUE;  
    break;  
  
   case 6:  
    ClearScreen();  
  
    if(IS_EMPTY(root))  
    { fflush(stdout);  
     printf("\nTree is empty.\n");  
    }  
    else  
     InorderTraversal(root);  
  
    HoldScreen();  
    repeat_flag=TRUE;  
    break;  
  
   case 7:  
    root=DeleteNode(root);  
    repeat_flag=TRUE;  
    break;  
  
   case 8:  
    DeleteBST(root);  
    repeat_flag=TRUE;  
    break;  
  
   case 9:  
    repeat_flag=FALSE;  
    break;  
  
   default:  
    printf("\nERROR: Invalid slection, please try again.\n");  
  
    result=DisplayMainMenu(&selection);  
  
    if(result != SUCCESS)  
    { returncode=FAILURE;  
        repeat_flag=FALSE;  
    }  
    else  
     repeat_flag=TRUE;  
  }  
 }  
 while(repeat_flag==TRUE);  
  
 return returncode;  
}  
  
  
void ClearScreen(void)  
{  
 int i=0;  
  
 fflush(stdout);  
  
 for(i=0; i<=SCRNSIZE; i++)  
  fprintf(stdout, "\n");  
  
 return;  
}  
  
  
void HoldScreen(void)  
{  
 char buffer[BUFSIZE]=" ";  
 printf("\nPress any key to continue.\n");  
 fgets(buffer, BUFSIZE, stdin);  
  
 return;  
}  
  
  
void nomemory(void)  
{ fprintf(stderr, "Not enough memory to run program.\n");  
 exit(200);  
}  
  
  
/* ADT function prototypes */  
  
pBST CreateBST(void)  
{  
 pBST tree=NULL;  
  
 tree=(pBST) malloc(sizeof(BST));  
   
 if (IS_FULL(tree)) nomemory();  
  
 tree->left_child =NULL;  
 tree->right_child=NULL;  
 strncpy(tree->wordkey," ",WORDLEN);  
 tree->nodedata.wordlength=0;  
 tree->nodedata.wordcount =0;  
  
 return tree;  
}  
  
  
pBST PopulateBST(void)  
{  
 char doitagain[2]="N";  
 char word[WORDLEN]=" ";  
 char buffer[BUFSIZE]=" ";  
 pBST tree=NULL;  
  
 do  
 { fprintf(stdout, "Enter a string (word) for the node key==>");  
  fgets(buffer, BUFSIZE, stdin);  
  sscanf(buffer, "%s", word);  
  
  InsertNode(&tree, word);  
    
  fprintf(stdout, "Do you want to enter another word (y/n)?");  
  fgets(buffer, BUFSIZE, stdin);  
  sscanf(buffer, "%s", doitagain);  
 }  
 while(strncmp(doitagain,"y",1)==0 || strncmp(doitagain,"Y",1)==0);  
  
 return tree;  
}  
  
  
void InorderTraversal(pBST ptr)  
{  
 if(ptr)  
 { InorderTraversal(ptr->left_child);  
  VisitNode(ptr);  
  InorderTraversal(ptr->right_child);  
 }  
  
 return;  
}  
  
  
void VisitNode(pBST ptr)  
{ fprintf(stdout,"%s %d\n", ptr->wordkey, ptr->nodedata.wordlength);  
 return;  
}  
  
  
pBST ModifiedBSTSearch(pBST tree, char *searchword)  
{  
 pBST temp=NULL;  
  
 if (IS_EMPTY(tree))   
  temp=NULL;  
 else  
 while(tree)  
 { if(strncmp(searchword,tree->wordkey,tree->nodedata.wordlength)==0)  
  { (tree->nodedata.wordcount)++;  
   return NULL;  
  }  
  else  
  if(strncmp(searchword,tree->wordkey,tree->nodedata.wordlength)<0)  
  { temp=tree;  
   tree=tree->left_child;  
  }  
  else  
  { temp=tree;  
   tree=tree->right_child;  
  }  
 }  
  
 return temp;  
}  
  
  
int InsertNode(pBST *node, char *newword)  
{  
 int returncode=SUCCESS;  
 pBST ptr=NULL, temp=NULL;  
  
 temp=ModifiedBSTSearch(*node, newword);  
  
 if (temp || !(*node))  
 {   
  ptr=(pBST) malloc(sizeof(BST));  
  if (IS_FULL(ptr)) nomemory();  
  
  strncpy(ptr->wordkey,newword,WORDLEN);  
  ptr->nodedata.wordcount=1;  
  ptr->nodedata.wordlength=strlen(ptr->wordkey);  
  ptr->left_child =NULL;  
  ptr->right_child=NULL;  
  
  if (*node)  
         { if (strncmp(newword,temp->wordkey,WORDLEN)<0)  
    temp->left_child=ptr;  
   else  
    temp->right_child=ptr;  
  }  
  else  
   (*node)=ptr;  
     
 }  
  
 return returncode;  
}  
  
  
pBST DeleteNode(pBST tree)  
{  
 return;  
}  
  
  
void DeleteBST(pBST tree)  
{  
 return;  
}  
  
  
void PerformSearch(pBST tree)  
{  
 return;  
}  
  
  
BOOL BSTSearch(pBST tree, char *searchword)  
{  
 int result=SUCCESS;  
  
 return result;  
}  
  
  
void PrintBST(pBST root, short x, short y)  
{  
 return;  
}  
  
  
pBST OptimizeBST(pBST tree)  
{  
 return;  
}