C++ Data Structures using 3 files for program. Program name: main.cpp, bst,cpp,
ID: 3575755 • Letter: C
Question
C++ Data Structures using 3 files for program. Program name: main.cpp, bst,cpp, bst.hpp , makefile
Binary Search Tree
Output file: tree.dat
For this program, you will develop a C++ program that will implement a binary search tree. The data structure for the tree will contain a phone number, name, email, and complete address. The phone number will be used for the key into the search tree. The following operations should be implemented:
Add a new telephone number and information into the tree
Delete a number from the tree
Locate a telephone number in the tree (Determine if the number is in the tree.)
Traverse and print tree to screen in pre-order
Traverse and print tree to screen in post-order
Traverse and print tree to screen in in-order
Quit the program.
The tree should be printed in ascending numerical order of the phone numbers. Use linked lists (dynamic memory) to implement the tree. When the user quits the program, save the tree into a file named tree.dat using the indented notation traversed in pre-order.
There should not be any duplicate telephone numbers in the tree.
Sample input and output:
A (for add or you can use numbers to select)
Telephone number:
3167229876
Name:
John Wesley
Address
151 S. Pinecrest, Wichita, KS 67218
Email:
rndhixon@yahoo.com
…
D
Telephone number:
3167229876
John Wesley deleted
IN (for in-order)
John Wesley 316-722-9876
Q
Explanation / Answer
makefile:
all:
g++ main.cpp bst.h bst.cpp -o bst
./bst
bst.cpp:
#include <iostream>
#include <cstdlib>
#include "bst.h"
using namespace std;
node* root;
BST::BST(){root = NULL;}
void BST::locateNode(string item, node **par, node **loc){
node *ptr, *ptrsave;
if (root == NULL){
*loc = NULL;
*par = NULL;
return;
}
if (item == root->telephoneNo)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->telephoneNo){ ptr = root->left; }
else{ ptr = root->right; }
ptrsave = root;
while (ptr != NULL){
if (item == ptr->telephoneNo){
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->telephoneNo){ ptr = ptr->left; }
else{ ptr = ptr->right; }
}
*loc = NULL;
*par = ptrsave;
}
void BST::insertNode(node *tree, node *newnode){
if (root == NULL){
root = new node;
root->telephoneNo = newnode->telephoneNo;
root->name = newnode->name;
root->address = newnode->address;
root->email = newnode->email;
root->left = NULL;
root->right = NULL;
return;
}
if (tree->telephoneNo == newnode->telephoneNo){ return; }
if (tree->telephoneNo > newnode->telephoneNo){
if (tree->left != NULL){ insertNode(tree->left, newnode); }
else{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
return;}}
else{
if( tree->right != NULL ){
insertNode(tree->right, newnode); }
else{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
return;
}
}
}
void BST::deleteNode(string item){
node *parent, *where;
if (root == NULL){ return; }
locateNode(item, &parent, &where);
if (where == NULL){ return; }
if (where->left == NULL && where->right == NULL){ case_a(parent, where); }
if (where->left != NULL && where->right == NULL){ case_b(parent, where); }
if (where->left == NULL && where->right != NULL){ case_b(parent, where); }
if (where->left != NULL && where->right != NULL){ case_c(parent, where); }
cout << "Deleted "<< where->name << endl;
free(where);
}
void BST::case_a(node *par, node *loc ){
if (par == NULL){ root = NULL; }
else{
if (loc == par->left){ par->left = NULL; }
else{ par->right = NULL; }
}
}
void BST::case_b(node *par, node *loc){
node *child;
if (loc->left != NULL){ child = loc->left; }
else{ child = loc->right; }
if (par == NULL){
root = child;
}
else{
if (loc == par->left){
par->left = child; }
else{ par->right = child; }
}
}
void BST::case_c(node *par, node *loc){
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL){
ptrsave = ptr;
ptr = ptr->left; }
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL){ case_a(parsuc, suc); }
else{ case_b(parsuc, suc);}
if (par == NULL){ root = suc; }
else{
if (loc == par->left){ par->left = suc; }
else{ par->right = suc; }}
suc->left = loc->left;
suc->right = loc->right;
}
void BST::preorder(node *ptr){
if (root == NULL || ptr == NULL){ return; }
cout << ptr->telephoneNo << "-" << ptr->name << " ";
preorder(ptr->left);
preorder(ptr->right);
}
void BST::preorder(node *ptr, ofstream &out){
if (root == NULL || ptr == NULL){ return; }
out << ptr->telephoneNo << "-" << ptr->name << " ";
preorder(ptr->left, out);
preorder(ptr->right, out);
}
void BST::inorder(node *ptr){
if (root == NULL || ptr == NULL){ return; }
inorder(ptr->left);
cout << ptr->telephoneNo << "-" << ptr->name << " ";
inorder(ptr->right);
}
void BST::postorder(node *ptr){
if (root == NULL || ptr == NULL ){
return;
}
postorder(ptr->left);
postorder(ptr->right);
cout << ptr->telephoneNo << "-" << ptr->name << " ";
}
bst.h:
#ifndef BST_H
#define BST_H
#include <string>
#include <fstream>
using namespace std;
struct node{
string telephoneNo;
string name;
string address;
string email;
struct node *left;
struct node *right;
};
class BST
{
public:
void locateNode(string, node **, node **);
void insertNode(node*, node*);
void deleteNode(string);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void preorder(node *, ofstream &out);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST();
};
#endif
main.cpp:
#include <iostream>
#include <cstdlib>
#include <fstream>
#include "bst.h"
using namespace std;
extern node* root;
int main(){
int input;
string number;
ofstream out("tree.dat"); //to save final tree
BST bst;
node *temp;
while (1){
cout<<"Allowed Operations: "<<endl;
cout<<"1. Add a new telephone number"<<endl;
cout<<"2. Delete a telephone number"<<endl;
cout<<"3. Locate a telephone number"<<endl;
cout<<"4. Inorder Traversal"<<endl;
cout<<"5. Preorder Traversal"<<endl;
cout<<"6. Postorder Traversal"<<endl;
cout<<"7. Quit the program"<<endl;
cout<<"Please enter your input : ";
cin>>input;
if( input == 1){
temp = new node;
cout<<"Enter the telephone number of the person: ";
cin>> temp->telephoneNo;
cout << "Enter name of the person : ";
cin >> temp->name;
cout << "Enter address of the person : ";
getline(cin, temp->address );
getline(cin, temp->address );
cout << "Enter email of the person : ";
cin >> temp->email;
bst.insertNode(root, temp);
}
else if( input == 2 ){
if (root == NULL){
cout<<"Nothing to delete"<<endl;
continue;
}
cout<<"Enter the telephone number to be deleted : ";
cin>>number;
bst.deleteNode(number);
}
else if( input == 3 ){
cout<<"Enter the number to locate : ";
cin >> number;
node *parent, *where;
bool found = false;
if (root != NULL){
bst.locateNode( number , &parent, &where); }
if (where != NULL){ found = true; }
if( !found ){
cout << "Doesn't exist" << endl; }
else{
cout << "Found!!!" << endl;
}
}
else if( input == 4 ){
cout<<"Inorder Traversal :"<<endl;
bst.inorder(root);
cout<<endl;
}
else if( input == 5 ){
cout<<"Preorder Traversal :"<<endl;
bst.preorder(root);
cout<<endl;
}
else if( input == 6 ){
cout<<"Postorder Traversal :"<<endl;
bst.postorder(root);
cout<<endl;
}
else if( input == 7 ){
break;
}
}
bst.preorder( root, out);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.