C++ Data Structures Binary Search Tree Output file: tree.dat For this program, y

ID: 3575082 • Letter: C

Question

C++ Data Structures

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

…

Telephone number:

3167229876

John Wesley deleted

IN (for in-order)

John Wesley 316-722-9876

Program name: main.cpp, bst,cpp, bst.hpp , makefile

Explanation / Answer

SOURCE CODE:

#include <iostream>
#include <cstdlib>
#include<fstream>
using namespace std;

class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
int phoneNumber;
string name;
string email;
string address;
};
tree_node* root;

public:
BinarySearchTree()
{
root = NULL;
}

bool isEmpty() const { return root==NULL; }

void search(int number)
{
tree_node* parent = NULL;

if(!isEmpty())
{
tree_node* curr;
curr = root;
while(curr)
{
parent = curr;
if(number > curr->phoneNumber)
               curr = curr->right;
else if(number < curr->phoneNumber)
               curr = curr->left;
           else if(number == curr->phoneNumber)
           {
               cout<<" "<<curr->phoneNumber<<" "<<curr->name<<" "<<curr->email<<" "<<curr->address;
               return;
           }
}

}
}

void insert(int d,string n,string e,string a)
{
tree_node* t = new tree_node;
tree_node* parent;
t->phoneNumber = d;
t->name = n;
t->email = e;
t->address = a;
t->left = NULL;
t->right = NULL;
parent = NULL;

if(isEmpty()) root = t;
else
{
tree_node* curr;
curr = root;
while(curr)
{
parent = curr;
if(t->phoneNumber > curr->phoneNumber) curr = curr->right;
else curr = curr->left;
}

if(t->phoneNumber < parent->phoneNumber)
parent->left = t;
else if(t->phoneNumber > parent->phoneNumber)
parent->right = t;
}
}

void remove(int d)
{
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}

tree_node* curr;
tree_node* parent;
curr = root;

while(curr != NULL)
{
if(curr->phoneNumber == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->phoneNumber) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
       {
cout<<" Telephone Number not found! "<<endl;
return;
}

if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL && curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}

       if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
              delete curr;
              return;
}

if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else
{
if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->phoneNumber = lcurr->phoneNumber;
delete lcurr;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->phoneNumber = tmp->phoneNumber;
curr->right = tmp->right;
delete tmp;
}

}
return;
}

}

void print_inorder()
{
inorder(root);
}

void inorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->phoneNumber<<" "<<p->name<<" "<<p->email<<" "<<p->address;
if(p->right) inorder(p->right);
}
else return;
}

void print_inorder(ofstream &outfile)
{
return inorder(root,outfile);
}

void inorder(tree_node* p,ofstream &outfile)
{
if(p != NULL)
{
if(p->left)
inorder(p->left,outfile);
outfile<<" "<<p->phoneNumber<<" "<<p->name+" "<<p->email+" "<<p->address;
if(p->right)
inorder(p->right,outfile);
}
else return;
}

void print_preorder()
{
preorder(root);
}

void preorder(tree_node* p)
{
if(p != NULL)
{
cout<<" "<<p->phoneNumber<<" "<<p->name<<" "<<p->email<<" "<<p->address;
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}

void print_postorder()
{
postorder(root);
}

void postorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<" "<<p->phoneNumber<<" "<<p->name<<" "<<p->email<<" "<<p->address;
}
else return;
}

};
int main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
string n,e,a;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Add a new telephone number and information into the tree "<<endl;
cout<<" 2. Locate a telephone number in the tree "<<endl;
cout<<" 3. Traverse and print tree to screen in in-order "<<endl;
cout<<" 4. Traverse and print tree to screen in pre-order "<<endl;
cout<<" 5. Traverse and print tree to screen in post-order "<<endl;
cout<<" 6. Delete a number from the tree "<<endl;
cout<<" 7. Quit the program "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Telephone Number: ";
cin>>tmp;
cout<<" Name: ";
cin>>n;
cout<<" Email: ";
cin>>e;
cout<<" Address: ";
cin>>a;
b.insert(tmp,n,e,a);
break;
case 2 : cout<<" Telephone Number: ";
cin>>tmp;
b.search(tmp);
break;
case 3 : cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_inorder();
break;
case 4 : cout<<endl;
cout<<" Pre-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_preorder();
break;
case 5 : cout<<endl;
cout<<" Post-Order Traversal "<<endl;
cout<<" --------------------"<<endl;
b.print_postorder();
break;
case 6 : cout<<" Telephone Number : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 7 :
            ofstream outfile;
                    outfile.open("Telephone_Directory.txt");
                    b.print_inorder(outfile);
                    outfile.close();
return 0;

}
}
}

Navigate

C++ Data Structure Recursion Sketch Inductive Proof (by using some values) The f

C++ Data Structures Course about Recursion We want to write a function that coun

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

C++ Data Structures Binary Search Tree Output file: tree.dat For this program, y

Question

Explanation / Answer

Related Questions

Navigate