二进制搜索树删除节点函数

Question

我正在处理一个二进制搜索树，我得到了一个插入节点函数，它看起来像这样

  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);
  }

我正在尝试编写一个递归删除节点的函数，到目前为止我已经想出了：

     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);
    }
       }

这两个函数都是从我的main函数中的一个开关调用的，如下所示：

    int main()
    {
 int key=0,countCatch=0;char q;
 Node *t, *n;
 t=0;
 while((q=menu()) !=0)
 {
     switch(q)
     {
     case'?': menu(); break;
     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;
     }

我的删除节点功能不起作用，properly....any建议会有帮助...

Answer 1

当您移除节点时，您只是将其键设置为'0'，而不是实际移除它。

例如：“4”具有子项“2”，而子项“1”和“3”

在您的代码中，删除'2‘会得到这样的树:4有子元素0，子元素有1和3。

要移除内部节点(具有子节点的节点)，必须处理其父指针及其子节点。您必须将父节点的子指针设置为已删除节点的子节点之一。有关更多信息，请查看本文：

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

Answer 2

看看代码，它不是递归的，虽然是http://code.google.com/p/cstl/source/browse/src/c_rb.c