c - 删除叶节点 BST

Question

我只是为了学习而尝试实现 AVL 树。我设法进行了插入，但我坚持删除。我在删除叶节点时遇到问题(独生子女的情况很好)。问题是，当我删除节点时，它不会从 BST 中删除，相反，它的值只是变为 0，因此当删除节点时树永远不会变得不平衡。我基本上做的是，如果我遇到一个没有 child 的节点，我就释放它。这是函数的代码(没有重新平衡部分):

node_t *Delete ( node_t *root, int num ){

   if ( !root ){
     printf ("Not Found\n");
     return root;
   }

//=======Search for the Element=============

   if ( num > root->data )
       Delete ( root->right , num );

   else if ( num < root->data )
       Delete ( root->left , num );

//======Delete element==============

   else if ( num == root->data ){

     if ( root->right && root->left ){ //two child case

         node_t *auxP = root->right;

         while ( auxP->left ) //finding the successor 
            auxP=auxP->left; 

         root->data = auxP->data; 

         root->right = Delete ( root->right, auxP->data );     
     }

     else{ //one or no child

         if ( !root->right && !root->left ){ // no childs
           free(root);       
         }
         else{ //one child
             node_t *auxP = ( root->right ?  root->right : root->left );
             *root=*auxP;
             free(auxP);
         }                
     }  

   }
  return root;
}

如果我有一棵这样的树:

        10
       /  \
      5    15 
     / \    \
    2   6    17

我试着删除6，结果是这样

        10
       /  \
      5   15 
     / \    \
    2   0    17

这可能是一个明显的错误，但我找不到它。任何关于它为什么不起作用的解释将不胜感激。

Answer 1

当你删除一个节点时，你需要更改其父节点的相应子字段。但是在您的代码中，您只传入要删除的节点本身 (node_t *root)，因此父节点保持不变。在单个子节点的情况下，您可以通过将单个子节点复制到要删除的节点来解决它，然后删除单个子节点。但在叶子的情况下，您无需修复父级中的链接。

一种方法是以某种方式传递父节点，以便当要删除的节点是叶节点时，断开与父节点的链接并将父节点的相应子节点设置为NULL。

或者，您可以向节点定义添加父链接，以便在删除节点时，可以从中派生父链接。