删除叶节点 BST

Question

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

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)，因此父节点保持不变。在单个子节点的情况下，您可以通过将单个子节点复制到要删除的节点来解决它，然后删除单个子节点。但是在叶子的情况下，你没有做任何事情来修复 parent.

中的 link

一种方法是以某种方式传入父节点，以便当要删除的节点是叶子时，从父节点中断开 link 并将父节点的相应子节点设置为 NULL.

或者，您可以将父节点 link 添加到节点定义中，以便在删除节点时，可以从中派生父节点 link。

删除叶节点 BST

Deleting a Leaf node BST

c

binary-search-tree