How do I develop a method of a binary search tree class

0

How do I develop a method of a binary search tree class, to return multiple elements of 5 in a list? C ++

    
asked by anonymous 29.05.2014 / 20:29

1 answer

1

File Binarysearchtree.h

  struct tree_node
  {
    tree_node *left;
    tree_node *right;
    int data;
  };
class Binarysearchtree
{
private:

    tree_node *root;
public:
    Binarysearchtree();
    bool isempty() const;
    void inorder ( tree_node * );
    void printinorder();
    void preorder ( tree_node * );
    void printpreorder();
    void postorder ( tree_node * );
    void printpostorder();
    bool binarytreesearch( int );
    void insert ( int );
    void remove ( int );
};

File binarysearchtree.cpp

#include <iostream>
#include "Binarysearchtree.h"
using namespace std;

Binarysearchtree::Binarysearchtree()
{
    root = 0;
}
bool Binarysearchtree::isempty() const
{
    return root == 0;
}
void Binarysearchtree::insert ( int d )
{
    tree_node *t = new tree_node;
    t->data = d;
    t->left = t->right = 0;
    tree_node *parent = 0;

    if ( root == 0)
        root = t;
    else
    {
        tree_node *curr;
        curr = root;
        while ( curr )
        {
            parent = curr;
            if ( d > curr->data )
                curr = curr->right;
            else curr = curr->left;
        }
        if ( d > parent->data )
            parent->right = t;
        else parent->left = t;
    }   
}
void Binarysearchtree::remove ( int d )
{
    if ( root == 0 )
    {
         cout << "Tree is empty. No removal. "<<endl;
         return;
    }
    if ( !binarytreesearch ( d ) )
    {
         cout << "Value is not in the tree. No removal." << endl;
         return;
    }
    tree_node *curr;
    tree_node *parent;
    tree_node *parent1;
    tree_node *temp;
    parent = 0;
    parent1 = 0;

    curr = root;

    while ( d != curr->data )
    {
        parent = curr;
        if ( d > curr->data )
            curr = curr->right;
        else
            curr = curr->left;
    }

    if ( curr->data == d )//it is leaf node
    {
        if ( curr->left == 0 && curr->right == 0 )
            {
                if ( parent != 0 )
                {
                    if (  parent->right  != 0 && ( parent->right )->data == curr->data ) 
                    parent->right = 0;
                    else parent->left = 0;
                    delete curr;
                }
                else
                {
                    root = 0;
                    delete curr;
                }
            }

    else if ( curr->left != 0 && curr->right == 0 )
    {
        if ( parent != 0 )
        {
            if ( parent->right != 0 &&  ( parent->right )->data == curr->data )
                parent->right = curr->left;
            else 
            parent->left = curr->left;

          delete curr;
        }
        else
        {
            root = curr->left;
            delete curr;
        }
    }
    else if ( curr->left == 0 && curr->right != 0 )
    {
        if ( parent != 0 )
        {
            if ( parent->right != 0 &&  (parent->right)->data == curr->data )
            parent->right = curr->right;
          else
              parent->left = curr->right;
          delete curr;
        }
        else 
        {
            root = curr->right;
            delete curr;
        }
    }
    else if ( curr->left != 0 && curr->right != 0)
    {
        if ( parent == 0 )
        {
            temp = curr->right;
            if ( temp->left == 0 )
            {
                temp->left = curr->left;
                curr->right = 0;
                root = temp;
                delete curr;
            }
            else
            {

                while ( temp->left != 0 )
                {
                    parent = temp;
                    temp = temp->left;
                }
                if ( temp->right == 0 )
                    {
                        parent->left = 0;
                        temp->left = curr->left;
                        temp->right = curr->right;
                        root = temp;
                        delete curr;
                    }
                else
                {
                    parent->left = 0;
                    parent->left = temp->right;
                    temp->left = curr->left;
                    temp->right = curr->right;
                    root = temp;
                    delete curr;
                }
            }
        }//end parent == 0
        else // parent != 0
        {
            temp = curr->right;
            if ( temp->left == 0 )
            {
                curr->right = 0;
                temp->left = curr->left;

                if ( parent->left != 0 && ( parent->left)->data == curr->data )
                { parent->left = 0; parent->left = temp; }
                else { parent->right = 0; parent->right = temp; }
                delete curr;
            }
            else
            {
                while ( temp->left  != 0 )
                {
                    parent1 = temp;
                    temp = temp->left;
                }
                if ( temp->right == 0)
                {
                    parent1->left = 0;
                    temp->left = curr->left;
                    temp->right = curr->right;
                    if ( parent->left != 0 && ( parent->left )->data  == curr->data )
                    {   parent->left = 0; parent->left = temp; }
                    else { parent->right = 0; parent->right = temp; }
                        delete curr;
                }
                else 
                {
                    parent1->left = 0;
                    parent1->left = temp->right;
                    temp->left = curr->left;
                    temp->right = curr->right;
                    if ( parent->left != 0 && ( parent->left )->data == curr->data)
                    { parent->left = 0; parent->left = temp; }
                    else  { parent->right = 0; parent->right = temp; } 
                        delete curr;
                }
            }
        }//end paret == 0
    }
  }
}
void Binarysearchtree::printinorder()
{
    inorder ( root );
}
void Binarysearchtree::inorder( tree_node *p )
{
    if ( p != 0 )
    {
        inorder(p->left);
        cout << " " << p->data << " ";  
        inorder ( p->right );
    }
}
void Binarysearchtree::printpostorder()
{
    postorder ( root );
}
void Binarysearchtree::postorder ( tree_node *p )
{
    if ( p != 0 )
    {
        if ( p->left )
            postorder ( p->left );
        if ( p->right )
            postorder ( p->right );
        cout << " " << p->data << " ";
    }
}
void Binarysearchtree::printpreorder()
{
    preorder ( root );
}
void Binarysearchtree::preorder ( tree_node *p )
{
    if ( p != 0 )
    {
       cout << " " << p->data << " ";
       if ( p->left )
        preorder ( p->left );
        if ( p->right )
        preorder ( p->right );
    }

}
bool Binarysearchtree::binarytreesearch( int d  )
{
    bool found = false;
    if ( root == 0 )
    {
        cout << "tree is empty";
    }
    tree_node *curr;
    tree_node *parent;
    parent = 0;
    curr = root;
    while ( curr != 0 )
    {
        if ( d == curr->data )
            {
                cout << "found";
                found = true;
                break;
        }
        else if ( d > curr->data )
        {
            parent = curr;
            curr = curr->right;
        }
        else
        {
            parent = curr;
            curr = curr->left;
        }

    }
    if ( !found )
        cout << "not found";
    return found;
} 

File Source.cpp

#include <conio.h>
#include <iostream>
#include <cstdlib>
#include "Binarysearchtree.h"
using namespace std;


int main()
{
    Binarysearchtree b;
    int ch,tmp,tmp1, temp2;
    while(1)
    {
       cout<<endl<<endl;
       cout<<" Binary Search Tree Operations "<<endl;
       cout<<" ----------------------------- "<<endl;
       cout<<" 1. Insertion/Creation "<<endl;
       cout<<" 2. In-Order Traversal "<<endl;
       cout<<" 3. Pre-Order Traversal "<<endl;
       cout<<" 4. Post-Order Traversal "<<endl;
       cout<<" 5. search " << endl;
       cout<<" 6. Removal "<<endl;
       cout<<" 7. Exit "<<endl;
       cout<<" Enter your choice : ";
       cin>>ch;
       switch(ch)
       {
           case 1 : cout<<" Enter Number to be inserted or enter to quit: ";     
                    cin >> tmp; 
                    b.insert( tmp );
                    break;
           case 2 : cout<<endl;
                    cout<<" In-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    b.printinorder();
                    break;
           case 3 : cout<<endl;
                    cout<<" Pre-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    b.printpreorder();
                    break;
           case 4 : cout<<endl;
                    cout<<" Post-Order Traversal "<<endl;
                    cout<<" --------------------"<<endl;
                    b.printpostorder();
                    break;
           case 5:
                    cout << "enter number for search ";
                    cin >> temp2;
                    b.binarytreesearch( temp2 );
                    break;
           case 6 : cout<<" Enter data to be deleted : ";
                    cin>>tmp1;
                    b.remove(tmp1);
                    break;
           case 7 : system("pause");
                    return 0;
                    break;
       }
    }
}

Source: Here

    
29.05.2014 / 20:43