Binary Search Tree In Data Structure Using C++

on

Data Structure Using C++

Tree Data Structure

Binary Search Tree 

class treeNode{
private:
 int info;
 treeNode* left;
 treeNode* right;
public:
        treeNode();
        treeNode(int i);
        void setInfo(int i);
 int getInfo();
 void setLeft(treeNode *l);
 treeNode* getLeft();
 void setRight(treeNode *r);
 treeNode* getRight();      
 int isLeaf();
};
// constructors
treeNode::treeNode() 
{
 left=NULL;
 right=NULL;
}
treeNode::treeNode(int i) 
{
 info=i;
 left=NULL;
 right=NULL;
}
int treeNode::getInfo() 
{ 
 return info; 
}
void treeNode::setInfo(int i) 
{ 
 info=i;
}
treeNode* treeNode::getLeft() 
{ 
 return left; 
}
void treeNode::setLeft(treeNode *l) 
{ 
 left=l;
}
treeNode* treeNode::getRight() 
{ 
 return right; 
}
void treeNode::setRight(treeNode *r) 
{ 
 right=r;
}     
int treeNode::isLeaf( )
{
 if(left==NULL&& right==NULL ) 
     return 1;
 return 0;
}
class BST{
 private:
  treeNode* root;
 public:
  BST(treeNode* r);
  void insert(int info);
  treeNode* remove(treeNode* tree, int info);
  treeNode* findMin(treeNode* tree);
  treeNode* findMax(treeNode* tree);
  treeNode* find(treeNode* tree, int info);
  void preorder(treeNode* treeNode);
  void inorder(treeNode* treeNode);
  void postorder(treeNode* treeNode);
};
BST::BST(treeNode* r){
 root=r;
}
void BST::insert(int info)
{
    treeNode* node = new treeNode(info);
    treeNode *p, *q;
    p = q = root;
    while(info!=(p->getInfo()) && q!= NULL )
    {
        p = q;
        if( info < p->getInfo() )
            q = p->getLeft();
        else
            q = p->getRight();
    }
 if( info == p->getInfo() ){
        cout << "attempt to insert duplicate: " << info << endl;
        delete node;
    }
    else if( info < p->getInfo() )
        p->setLeft( node );
    else
        p->setRight( node );        
} // end of insert
treeNode* BST::remove(treeNode* tree, int info)
{
    treeNode* t;
    int cmp = info - (tree->getInfo());
    if( cmp < 0 ){
        t = remove(tree->getLeft(), info);
        tree->setLeft( t );
    }
    else if( cmp > 0 ){
        t = remove(tree->getRight(), info);
        tree->setRight( t );
    }
    //two children, replace with inorder successor
    else if(tree->getLeft() != NULL && tree->getRight() != NULL ){  
        treeNode* minNode;
        minNode = findMin(tree->getRight());
        tree->setInfo( minNode->getInfo() );
        t = remove(tree->getRight(),(minNode->getInfo()));
        tree->setRight( t );
    }
    else {  // case 1
        treeNode* nodeToDelete = tree;
        if( tree->getLeft() != NULL ) //will handle 0 children
            tree = tree->getLeft();
        else if( tree->getRight() != NULL )
            tree = tree->getRight(); 
        else tree = NULL; 
        
        delete nodeToDelete;
    }
    return tree;
}
treeNode* BST::findMin(treeNode* tree)
{
    if( tree == NULL ) 
        return NULL;
    if( tree->getLeft() == NULL ) 
        return tree; // this is it.
    return findMin( tree->getLeft() );
}
treeNode* BST::findMax(treeNode* tree)
{
    if( tree == NULL ) 
        return NULL;
    if( tree->getRight() == NULL ) 
        return tree; // this is it.
    return findMax( tree->getRight());
}
treeNode* BST::find(treeNode* tree, int info)
{
 if(tree==NULL)
 {
  cout<<"Value not found!"<<endl;
  return NULL;
 }
    if(info==tree->getInfo()) 
     cout<<"Value found!"<<endl;
    else if(info<tree->getInfo())
     find(tree->getLeft(),info);
    else
     find(tree->getRight(),info);
    return tree;
}
void BST::preorder(treeNode* treeNode)
{
    if( treeNode != NULL ) 
    {
        cout << treeNode->getInfo()<<" ";
        preorder(treeNode->getLeft());
        preorder(treeNode->getRight());
    }
}
void BST::inorder(treeNode* treeNode)
{
    if( treeNode != NULL ) 
    {
        inorder(treeNode->getLeft());
        cout << treeNode->getInfo()<<" ";
        inorder(treeNode->getRight());
    }
}
void BST::postorder(treeNode* treeNode)
{
    if( treeNode != NULL ) 
    {
        postorder(treeNode->getLeft());
        postorder(treeNode->getRight());
        cout << treeNode->getInfo()<<" ";
    }
}

int main()
{
 int x[] = { 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5, -1};
 treeNode *root = new treeNode();
 root->setInfo(x[0]);
 BST tree(root);
 for(int i=1; x[i]>0; i++ )
 {
  tree.insert(x[i]);
 }
 treeNode *max;
 max=tree.findMax(root);
 cout<<"Max: "<<max->getInfo()<<endl;
 tree.find(root,16); 
 cout<<"preorder: "; 
 tree.preorder(root);
 cout<<endl<< "inorder: ";   
 tree.inorder(root);
 cout<<endl<<"postorder: "; 
 tree.postorder(root);
 cout<<endl<<"Remove: 14";
 tree.remove(root, 14);
 cout<<endl<< "inorder: ";   
 tree.inorder(root); 
}

Let me know in the comment section if you have any question.

Previous Post:
(Remove Function) Binary Search Tree In Data Structure Using C++

Comments

Post a Comment