How do I develop a method of a binary search tree class, to return multiple elements of 5 in a list? C ++
How do I develop a method of a binary search tree class, to return multiple elements of 5 in a list? C ++
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