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

on

Data Structure Using C++

Tree Data Structure

Binary Search Tree

(Remove Function) Binary Search Tree

#include "treeNode.cpp"
void insert(treeNode* root, int info);
treeNode* remove(treeNode* tree, int info);
treeNode* findMin(treeNode* tree);
void inorder(treeNode* treeNode);
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]);
 for(int i=1; x[i]>0; i++ )
 {
  insert(root, x[i] );
 } 
 cout<<endl<< "inorder: "<<endl;   
 inorder(root);
 
 cout<<endl<<"Remove: "<<endl;
 remove(root, 14);
 
  cout<<endl<< "inorder: "<<endl;   
 inorder(root); 
}
treeNode* 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* findMin(treeNode* tree)
{
    if( tree == NULL ) 
        return NULL;
    if( tree->getLeft() == NULL ) 
        return tree; // this is it.
    return findMin( tree->getLeft() );
}

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

Previous Post:
(PreOder | InOrder | PostOrder Traverse Using Non Recursive Calls) Binary Search Tree In Data Structure Using C++

Comments

Post a Comment