C++ Binary Search Tree class

Ocak 26, 2008 tarihinde C/C++ kategorisi altında kayda geçti

here is the code that would be useful entire of your life. this is binary search tree class man! the best recursively implemented data structure in the world :) talk is cheap. let me show you the code :)

class tnode{public:string file;tnode *left;
 
tnode *right;
 
tnode(string s);
 
};
 
tnode::tnode(string str){
 
file=str;
 
left=NULL;
 
right=NULL;
 
}

The class above is the tnode class which is a leaf of binary search tree class.A tnode has 3 attirubute.file is the data which a node can hold. left and right pointers are the pointers which points the left and right child of each node. keep your eye on this.the pointers are the type in tnode.dont miss this.

class bst{private:tnode *root;
 
public:
 
void remove(tnode *&root,string s);
 
string suitable(tnode *root);
 
void insert(tnode* &root, string file);
 
bool isfound( tnode *root, string file );
 
void displayinorder(tnode* root);
 
void display();
 
void insert(string s);
 
void remove(string s);
 
bool isfound(string s);
 
bst();
 
};
 
bst::bst(){
 
root=NULL;
 
}
 
bool bst::isfound(string s){
 
if(isfound(root,s))
 
return true;
 
else
 
return false;
 
}
 
void bst::insert(string s){
 
insert(root,s);
 
}
 
void bst::remove(string s){
 
remove(root,s);
 
}
 
void bst::display(){
 
displayinorder(root);
 
}
 
//Displays tree inorder recursively
 
void bst::displayinorder(tnode *root){
 
if(root==NULL)
 
return ;
 
displayinorder(root->left);
 
cout<file<< endl;
 
displayinorder(root->right);
 
}
 
bool bst::isfound( tnode *root, string file ) {
 
if ( root == NULL ) {
 
return false;
 
}else if ( file == root->file ) {
 
return true;
 
}else if ( file < root->file ) {
 
return isfound( root->left, file );
 
}else {
 
return isfound( root->right, file );
 
}
 
}
 
void bst::remove(tnode *&root,string s){
 
if(root->file==s){
 
//if it is a child
 
if(root->left==NULL && root->right==NULL){
 
delete root;
 
root=NULL;
 
}
 
//if the root has only one child
 
else if(root->left==NULL){
 
tnode *temp;
 
temp=root;
 
root=root->right;
 
delete temp;
 
}else if(root->right==NULL){
 
tnode *temp;
 
temp=root;
 
root=root->left;
 
delete temp;
 
}
 
//if the root has two childiren
 
else{
 
string temp;
 
temp=suitable(root);
 
remove(root,temp);
 
root->file=temp;
 
}
 
}else if(root->file>s){
 
remove(root->left,s);
 
}else{
 
remove(root->right,s);
 
}
 
}
 
string bst::suitable(tnode *root){
 
tnode *temp;
 
temp=root->right;
 
while(temp->left!=NULL)
 
temp=temp->left;
 
return temp->file;
 
}
 
void bst::insert(tnode* &root, string file) {
 
if ( root == NULL ) {
 
root = new tnode( file );
 
return;
 
}
 
else if ( file < root->file ) {
 
insert( root->left, file );
 
}
 
else {
 
insert( root->right, file );
 
}
 
}

the above class uses the tnode class as you see. the reason why overloaded the function insert is i used this class in an another class and i dont have a such a variable root there.because of this i overloaded this function. i dont need to explain whole code but if you dont understand anything here feel free to ask me. good luck ;)