63 203
Assignments Done
99,3%
Successfully Done
In July 2018

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

Question #52538
write a program that inserts integers 1 to 20 to a binary search tree.assume the root node is created with value 10.
Expert's answer
#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();
      
   }
}


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be first!

Leave a comment

Ask Your question

Submit
Privacy policy Terms and Conditions