C++ Data Structures using 3 files for program Binary Search Tree Output file: tr
ID: 3575450 • Letter: C
Question
C++ Data Structures using 3 files for program
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
Program name: main.cpp, bst,cpp, bst.hpp , makefile
Explanation / Answer
Bst.h
#ifndef BST
#define BST
#include <iostream>
/*
* Node Declaration
*/
struct node
{
string name;
string phone;
string email;
string address;
struct node *left;
struct node *right;
}*root;
class Bst
{
public:
void findPhoneNumber(int, node **, node **);
void insertNumber(int);
void deleteNumber(int);
void TreeCaseA(node *,node *);
void TreeCaseB(node *,node *);
void TreeCaseC(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void displayResult(node *, int);
Bst()
{
root = NULL;
}
};
#endif
-------------------------------------------------------------------------------------------------------------------------------------------------------
Bst.cpp
# include <iostream>
#include "Bst.h"
using namespace std;
void Bst::findPhoneNumber(int phone, node **temp_par, node **location)
{
node *ptr, *savePtr;
if (root == NULL)
{
*location = NULL;
*temp_par = NULL;
return;
}
if (phone == root->phone)
{
*location = root;
*temp_par = NULL;
return;
}
if (phone < root->phone)
ptr = root->left;
else
ptr = root->right;
savePtr = root;
while (ptr != NULL)
{
if (phone == ptr->phone)
{
*location = ptr;
*temp_par = savePtr;
return;
}
savePtr = ptr;
if (phone < ptr->phone)
ptr = ptr->left;
else
ptr = ptr->right;
}
*location = NULL;
*temp_par = savePtr;
}
/* Inserting new contact into tree*/
void Bst::insertNumber(node *tree, node *tempNode)
{
if (root == NULL)
{
root = new node;
root->phone = tempNode->phone;
root->left = NULL;
root->right = NULL;
cout<<"Root Node added successfully"<<endl;
return;
}
if (tree->phone == tempNode->phone)
{
cout<<"This contact already exist."<<endl;
return;
}
if (tree->phone > tempNode->phone)
{
if (tree->left != NULL)
{
insertNumber(tree->left, tempNode);
}
else
{
tree->left = tempNode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Contact Added To Left sub tree"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insertNumber(tree->right, tempNode);
}
else
{
tree->right = tempNode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right sub tree"<<endl;
return;
}
}
}
/* Delete contact from tree */
void Bst::deleteNumber(int phone)
{
node *rootParent, *location;
if (root == NULL)
{
cout<<"Empty tree"<<endl;
return;
}
findPhoneNumber(phone, &rootParent, &location);
if (location == NULL)
{
cout<<"contact not found"<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
TreeCaseA(rootParent, location);
if (location->left != NULL && location->right == NULL)
TreeCaseB(rootParent, location);
if (location->left == NULL && location->right != NULL)
TreeCaseB(rootParent, location);
if (location->left != NULL && location->right != NULL)
TreeCaseC(rootParent, location);
free(location);
}
void Bst::TreeCaseA(node *temp_par, node *location )
{
if (temp_par == NULL)
{
root = NULL;
}
else
{
if (location == temp_par->left)
temp_par->left = NULL;
else
temp_par->right = NULL;
}
}
void Bst::TreeCaseB(node *temp_par, node *location)
{
node *child;
if (location->left != NULL)
child = location->left;
else
child = location->right;
if (temp_par == NULL)
{
root = child;
}
else
{
if (location == temp_par->left)
temp_par->left = child;
else
temp_par->right = child;
}
}
void Bst::TreeCaseC(node *temp_par, node *location)
{
node *ptr, *savePtr, *suc, *parsuc;
savePtr = location;
ptr = location->right;
while (ptr->left != NULL)
{
savePtr = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = savePtr;
if (suc->left == NULL && suc->right == NULL)
TreeCaseA(parsuc, suc);
else
TreeCaseB(parsuc, suc);
if (temp_par == NULL)
{
root = suc;
}
else
{
if (location == temp_par->left)
temp_par->left = suc;
else
temp_par->right = suc;
}
suc->left = location->left;
suc->right = location->right;
}
/* Pre order */
void Bst::preorder(node *ptr)
{
if (root == NULL)
{
cout<<"Empty tree"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->phone<<" "<<ptr->name<<" "<<ptr->email<<" "<<ptr->address;
preorder(ptr->left);
preorder(ptr->right);
}
}
/*
* In Order
*/
void Bst::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Empty Tree"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->phone<<" "<<ptr->name<<" "<<ptr->email<<" "<<ptr->address;
inorder(ptr->right);
}
}
/*
* Postorder Traversal
*/
void Bst::postorder(node *ptr)
{
if (root == NULL)
{
cout<<"Empty tree"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->phone<<" "<<ptr->name<<" "<<ptr->email<<" "<<ptr->address;
}
}
//display data
void Bst::displayResult(node *ptr, int tempLevel)
{
int i;
if (ptr != NULL)
{
displayResult(ptr->right, tempLevel+1);
if (ptr == root)
cout<<"Root Value ->: ";
else
{
for (i = 0;i < tempLevel;i++)
cout<<" ";
}
cout<<ptr->phone<<" "<<ptr->name<<" "<<ptr->email<<" "<<ptr->address;
displayResult(ptr->left, tempLevel+1);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.