Answer to Question #52538 in Programming & Computer Science for biruk

Question

write a program that inserts integers 1 to 20 to a binary search tree.assume the root node is created with value 10.

Answer 1

#include <iostream>
#include <queue>
#include <cstdlib>
#include <fstream>

using namespace std;

template <typename T>
struct node{
T data;
struct node *left;
struct node *right;
};

template <typename T>
class PDBinarySearchTree{
public:
node<T> *tree;
PDBinarySearchTree(){
tree = NULL;
}
void PDcreateTree(node<T> **,T item);
void PDpreOrder(node<T> *);
void PDinOrder(node<T> *);
void PDpostOrder(node<T> *);
void PDdetermineHeight(node<T> *,T *);
int PDtotalNodes(node<T> *);
int PDinternalNodes(node<T> *);
int PDexternalNodes(node<T> *);
void PDremoveTree(node<T> **);
void PDFindPersonByMonth(node<T>* n, int month);
void PDFindPersonByName(node<T>* n, string name);
void PDFindPersonByStatus(node<T>* n, string personStatus);
void PDSaveToFile&#40;node<T>* n&#41;;
void PDlevelOrder(node<T>* n);
node<T> **PDsearchElement(node<T> **,T);
void PDfindSmallestNode(node<T> *);
void PDfindLargestNode(node<T> *);
void PDdeleteNode(T);
};

int main() {

PDBinarySearchTree<int>* tree = new PDBinarySearchTree<int>();

tree->PDcreateTree(&tree;->tree, 20);

for (int i = 0; i < 20; i++)
tree->PDcreateTree(&tree;->tree, i + 1);

tree->PDinOrder(tree->tree);

system&#40;"pause"&#41;;

return 0;
}


template <typename T>
void PDBinarySearchTree<T> :: PDcreateTree(node<T> **tree,T item){
if(*tree == NULL){
*tree = new node<T>;
(*tree)->data = item;
(*tree)->left = NULL;
(*tree)->right = NULL;
}
else{
if( (*tree)->data > item)
PDcreateTree( &((*tree)->left),item);
else
PDcreateTree( &((*tree)->right),item);
}
}

template <typename T>
void PDBinarySearchTree<T> ::PDFindPersonByMonth(node<T>* node, int month) {

if ( node != NULL ) {

PDFindPersonByMonth(node->left, month);

if (node->data.getMonth() == month) {
cout <<node->data.getFirstName()<<" "<<node->data.getLastName()<<endl;
}

PDFindPersonByMonth(node->right, month);
}
}

template <typename T>
void PDBinarySearchTree<T> ::PDFindPersonByName(node<T>* node, string name) {

if ( node != NULL ) {

PDFindPersonByName(node->left, name);

if (node->data.getLastName() == name) {
cout<<"address : "<<endl;
node->data.displayAddress();
cout<<"phone - ";
node->data.displayPhoneNumber();
cout<<"date of birth - ";
node->data.displayDate();

}

PDFindPersonByName(node->right, name);
}
}

template <typename T>
void PDBinarySearchTree<T> ::PDFindPersonByStatus(node<T>* node, string personStatus) {

if ( node != NULL ) {

PDFindPersonByStatus(node->left, personStatus);

if (node->data.getPersonStatus() == personStatus) {
cout <<node->data.getFirstName()<<" "<<node->data.getLastName()<<endl;
}

PDFindPersonByStatus(node->right, personStatus);
}
}

template <typename T>
void PDBinarySearchTree<T> :: PDpreOrder(node<T> *tree){
if( tree != NULL){
std::cout<<tree->data<<endl;
PDpreOrder(tree->left);
PDpreOrder(tree->right);
}
}

template <typename T>
void PDBinarySearchTree<T> :: PDinOrder(node<T> *tree){
if( tree!=NULL){
PDinOrder( tree->left);
std::cout<<tree->data<<endl;
PDinOrder(tree->right);
}
}

template <typename T>
void PDBinarySearchTree<T> :: PDpostOrder(node<T> *tree){
if( tree!=NULL){
PDpostOrder( tree->left);
PDpostOrder( tree->right);
std::cout<<tree->data<<endl;
}
}

template <typename T>
void PDBinarySearchTree<T> :: PDdetermineHeight(node<T> *tree, T *height){
int left_height, right_height;
if( tree == NULL)
*height = 0;
else{
PDdetermineHeight(tree->left, &left;_height);
PDdetermineHeight(tree->right, &right;_height);
if( left_height > right_height)
*height = left_height + 1;
else
*height = right_height + 1;
}
}

template <typename T>
int PDBinarySearchTree<T> :: PDtotalNodes(node<T> *tree){
if( tree == NULL)
return 0;
else return( PDtotalNodes(tree->left) + PDtotalNodes(tree->right) + 1 );
}

template <typename T>
int PDBinarySearchTree<T> :: PDinternalNodes(node<T> *tree){
if( (tree == NULL) || (tree->left == NULL && tree->right == NULL))
return 0;
else return( PDinternalNodes(tree->left) + PDinternalNodes(tree->right) + 1 );
}

template <typename T>
int PDBinarySearchTree<T> :: PDexternalNodes(node<T> *tree){
if( tree == NULL )
return 0;
else if( tree->left == NULL && tree->right == NULL)
return 1;
else return( PDexternalNodes(tree->left) + PDexternalNodes(tree->right));
}

template <typename T>
void PDBinarySearchTree<T> :: PDremoveTree(node<T> **tree){
if( (*tree) != NULL){
PDremoveTree( &(*tree)->left );
PDremoveTree( &(*tree)->right );
delete( *tree );
}
}

template <typename T>
node<T> ** PDBinarySearchTree<T> :: PDsearchElement(node<T> **tree, T item){
if( ((*tree)->data == item) || ( (*tree) == NULL) )
return tree;
else if( item < (*tree)->data)
return PDsearchElement( &(*tree)->left, item);
else return PDsearchElement( &(*tree)->right, item);
}

template <typename T>
void PDBinarySearchTree<T> :: PDfindSmallestNode(node<T> *tree){
if( tree == NULL || tree->left == NULL)
std::cout<< tree->data;
else
PDfindSmallestNode( tree->left);
}

template <typename T>
node<T> * find_Insucc(node<T> *curr)
{
node<T> *succ = curr->right;
if(succ != NULL){
while(succ->left != NULL)
succ = succ->left;
}
return(succ);
}

template <typename T>
void PDBinarySearchTree<T> :: PDfindLargestNode(node<T> *tree){
if( tree == NULL || tree->right == NULL)
std::cout<<tree->data;
else
PDfindLargestNode(tree->right);
}

template <typename T>
void PDBinarySearchTree<T> :: PDdeleteNode(T item){

node<T> *curr = tree,*succ,*pred;

int flag = 0,delcase;

while(curr!=NULL && flag!=1)
{
if(item < curr->data){
pred = curr;
curr = curr->left;
}
else if(item > curr->data){
pred = curr;
curr = curr->right;
}
else{
flag=1;
}
}

if(flag == 0){
std::cout<<"\nItem does not exist : No deletion\n";
system&#40;"pause"&#41;;
return;
}


if(curr->left==NULL && curr->right==NULL)
delcase=1;
else
if(curr->left!=NULL && curr->right!=NULL)
delcase = 3;
delcase = 2;
if(delcase==1){
if(pred->left == curr)
pred->left=NULL;
pred->right=NULL;
delete(curr);
}


if(delcase == 2){
if(pred->left==curr){
if(curr->left==NULL)
pred->left=curr->right;
else
pred->left=curr->left;
}
else{
if(curr->left==NULL)
pred->right=curr->right;
else
pred->right=curr->left;
}
delete(curr);
}

if(delcase == 3){
succ = find_Insucc(curr);
T item1 = succ->data;
PDdeleteNode(item1);
curr->data = item1;
}
}

template<typename T>
void PDBinarySearchTree<T>::PDSaveToFile&#40;node<T>* n&#41; {

queue<node<T>*> q;

q.push(n);

ofstream fout("Programming Assignment 4 Data.txt");

while ( ! q.empty() )
{
node<T>* v = q.front();
fout<< v->data.toString();

if ( v->left != NULL )
q.push(v->left);

if ( v->right != NULL )
q.push(v->right);

q.pop();

}

fout.close();
}

template<typename T>
void PDBinarySearchTree<T>::PDlevelOrder(node<T>* n) {

queue<node<T>*> q;

q.push(n);

while ( ! q.empty() )
{
node<T>* v = q.front();
cout << v->data.toString()<<endl;

if ( v->left != NULL )
q.push(v->left);

if ( v->right != NULL )
q.push(v->right);

q.pop();

}
}