0
How do I develop a method of a binary tree class of search, to return multiple elements of 5 in a list? C++
1 answer
1
Filing cabinet 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 );
};
Filing cabinet 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;
}
Filing cabinet 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
Browser other questions tagged c++
You are not signed in. Login or sign up in order to post.
It tells you more details about your problem, or what point you’re having problems with, because your question seems very superficial, try to add more details so that someone can help you more easily.
– Fernando Leal