Binary Search Tree remove node function

I am working on a binary search tree and i have been given an insertnode function that looks like

  void insertNode(Node **t, Node *n)
  {
       if(!(*t))
     *t=n;

     else if((*t)->key<n->key)insertNode(&(*t)->right,n);
     else if((*t)->key>n->key) insertNode(&(*t)->left,n);
  }

I am trying to write a function that removes nodes recursively so far i have come up with:

     void remove(int huntKey,Node **t)
   {
bool keyFound=false;
if(!(*t))
         cout<<"There are no nodes"<<endl;

    while(keyFound==false)
    {
        if((*t)->key==huntKey)
        {
            keyFound=true;
            (*t)->key=0;
        }
        else if((*t)->key < huntKey)remove(huntKey,&(*t)->right);
        else if((*t)->key> huntKey) remove(huntKey,&(*t)->left);
    }
       }

Both of these functions are getting called from a switch in my main function which looks like:

    int main()
    {
 int key=0,countCatch=0;char q;
 Node *t, *n;
 t=0;
 while((q=menu()) !=0)
 {
     switch(q)
     {
     case'?': menu(); break;
  开发者_StackOverflow社区   case'i': inOrderPrint(t); break;
     case'a': preOrderPrint(t); break;
     case'b': postOrderPrint(t); break;
     case'c': {cout<<"enter key: ";cin>>key;
     n=createNode(key);insertNode(&t,n);break;}

     case'r':{cout<<"enter the key you want removed: ";
     cin>>key;
     remove(key,&t);
     break;}

     case'n': {countCatch=countNodes(t);cout<<countCatch<<"\n"; };break;
     }
 }


 return 0;
     }

my remove node function is not working properly....any advice would help....

---

When you remove the node, you are only setting its key to '0', not actually removing it.

Example: '4' has child '2,' which has children '1' and '3.'

In your code, removing '2' gives you this tree: 4 has child 0, which has children 1 and 3.

To remove an internal node (a node with children), you must handle its parent pointer and its children. You must set the parent's child-pointer to one of the removed node's children. Check this article for more:

http://en.wikipedia.org/wiki/Binary_tree#Deletion

---

Look at the code, it is not recursive though http://code.google.com/p/cstl/source/browse/src/c_rb.c