# include <string.h># include <stdio.h># include <stdlib.h>class ContactInfo{ public: ContactInfo(char *name, char *number); //constructor char *getName(); // get function for contactName char *getNumber(); //get function for contactNumber void printInfo(); // prints contactName and contactNumber to standard output private: char *contactName; char *contactNumber; }; //end of class ContactInfo ContactInfo::ContactInfo(char *name, char *number){ contactName = (char *) malloc(100); contactNumber = (char *) malloc(100); strcpy(contactName, name); strcpy(contactNumber,number);}char *ContactInfo::getName(){ return contactName;}char *ContactInfo::getNumber(){ return contactNumber;}class TreeNode { public: TreeNode(char * searchArg, ContactInfo *data); //constructor ContactInfo *getInfo(); // accesses the contact info stored in the data portion this node TreeNode *getLeftChild(); //just returns leftChild. Used to traverse the BST TreeNode *getRightChild(); //just returns rightChild. void setLeftChild (TreeNode *newChild); //used to build the binary search tree void setRightChild(TreeNode *newChild); //ditto char *getSearchKey(); private: char *searchKey; //Holds the searchArg specified in the constructor //This is the value used for sorting the BST ContactInfo *data; //Stores the contact information for this node as supplied to the // constructor TreeNode *leftChild; TreeNode *rightChild;}; //end of class TreeNode TreeNode::TreeNode(char * searchArg, ContactInfo *data){ searchKey = (char *) malloc(sizeof(searchArg)); strcpy(searchKey, searchArg); this->data = data; leftChild = NULL; rightChild = NULL;}ContactInfo *TreeNode::getInfo(){ return data;}TreeNode *TreeNode::getLeftChild(){ return leftChild;}TreeNode *TreeNode::getRightChild(){ return rightChild;}void TreeNode::setLeftChild (TreeNode *newChild){ leftChild = newChild;}void TreeNode::setRightChild(TreeNode *newChild){ rightChild = newChild;} char *TreeNode::getSearchKey(){ return searchKey;}class BinSearchTree { public: BinSearchTree(); //constructor /******************************************************************** * The following member function inserts a node containing new contact information * into the BST at the proper position as determined by the value of the searchArg. * Note that the searchArg will be either the contactName or contactNumber depending on * whether the BST is sorted by name or number. If the new node is successfully inserted, * the function returns TRUE. If a node with the matching search argument already exists, * or the insertion fails for any other reason, the function returns FALSE. *****************************************************************/ bool insertNode(char *searchArg, ContactInfo *newEntry); /******************************************************************* * The following member function searches for a node in the BST whose searchKey matches * the searchArg. If a match is found, the function returns a pointer to the contact * information stored in the node. Otherwise, a null pointer is returned. *****************************************************************/ ContactInfo *findInfo(char *searchArg); /******************************************************************* * The following member function prints the contents of the tree (contact information * only) in sorted order--i.e. via an in-order traversal of the tree. **************************************************************************/ void printTree(); private: TreeNode *root_ptr; //pointer to the root of the BST}; //end of class BinSearchTreeBinSearchTree::BinSearchTree(){ root_ptr = NULL; }bool BinSearchTree::insertNode(char *searchArg, ContactInfo *newEntry){ TreeNode t(searchArg,newEntry); if(NULL == root_ptr) { root_ptr = &t; return true; } else { TreeNode *x = root_ptr; while(NULL != x) { if(0 == strcmp(searchArg, x->getSearchKey())) { return false; } else if(0 < strcmp(searchArg, x->getSearchKey())) { if(NULL == x->getRightChild()) { x->setRightChild(&t); return true; } x = x->getRightChild(); } else { if(NULL == x->getLeftChild()) { x->setLeftChild(&t); return true; } x = x->getLeftChild(); } } } return false;}ContactInfo *BinSearchTree::findInfo(char *searchArg){ // ContactInfo c("Josh","123-8588"); // return &c; }void printInfo(TreeNode *x){ if(NULL != x) { //printInfo(x->getLeftChild()); ContactInfo *c = x->getInfo(); printf("%s ",c->getName()); printf("%s\n",c->getNumber()); //printInfo(x->getRightChild()); }}void BinSearchTree::printTree(){ printInfo(root_ptr);}int main(){ ContactInfo c("Josh","123-8588"); ContactInfo d("Katie","555-8944"); ContactInfo e("Dwiju","789-4345"); printf("%s\n",c.getName()); printf("%s\n",c.getNumber()); TreeNode t("J",&c); TreeNode u("K",&d); TreeNode v("D",&e); t.setLeftChild(&u); t.setRightChild(&v); ContactInfo *x = t.getInfo(); printf("%s\n",t.getSearchKey()); printf("%s\n",x->getNumber()); printf("%s\n",x->getName()); TreeNode *kid1 = t.getLeftChild(); x = kid1->getInfo(); printf("%s\n",kid1->getSearchKey()); printf("%s\n",x->getNumber()); printf("%s\n",x->getName()); TreeNode *kid2 = t.getRightChild(); x = kid2->getInfo(); printf("%s\n",kid2->getSearchKey()); printf("%s\n",x->getNumber()); printf("%s\n",x->getName()); /*ContactInfo c("Josh","123-8588"); ContactInfo k("Katie","555-8944"); BinSearchTree b; b.insertNode("Josh",&c); b.printTree(); */ getchar(); return 1;}