我正在尝试实现一个AVL树只是为了学习 . 我设法插入，但我坚持删除 . 我在删除叶节点时遇到问题（单子案例工作正常） . 问题是，当我删除节点时，它不会从BST中删除，相反，它的值只是变为0，因此当删除节点时树永远不会失衡 . 我基本上做的是，如果我遇到没有孩子的节点，我就把它释放出来 . 这是函数的代码（没有重新 balancer 部分）：
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
这可能是一个明显的错误，但我无法找到它 . 任何解释为什么它不工作将不胜感激 .
1 回答
删除节点时，需要更改其父节点的相应子字段 . 但是在您的代码中，您只传递节点到删除本身（
node_t *root），因此父节点保持不变 . 在单个子案例中，您可以通过将单个子项复制到要删除的节点来解决此问题，并删除单个子项 . 但在叶子情况下，您无法修复父级链接 .一种方法是以某种方式传递父节点，以便当节点到删除是叶子时，断开父节点的链接并将父节点的相应子节点设置为
NULL.或者，您可以向节点定义添加父链接，以便在删除节点时，可以从中派生父链接 .