首页 文章

二进制搜索树节点删除

提问于
浏览 次
0

我正在实现从二叉搜索树中删除节点的功能 . 该功能的原型已设置，我无法更改它，这是一项学校作业 . 我的代码：

typedef struct tBSTNode {
    char Key;                                                                 
    struct tBSTNode * LPtr;                                
    struct tBSTNode * RPtr;  
} *tBSTNodePtr; 

void BSTDelete (tBSTNodePtr *RootPtr, char K) {
  tBSTNodePtr *tmp;

  if (*RootPtr != NULL) {
    if (K < (*RootPtr)->Key)
        BSTDelete(&(* RootPtr)->LPtr, K);
    else if (K > (*RootPtr)->Key)
        BSTDelete(&(* RootPtr)->RPtr, K);
    else {
            if ((* RootPtr)->LPtr == NULL) {
                /* there is only right branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->RPtr;
                free(*tmp);
                *tmp = NULL;
            }
            else if ((* RootPtr)->RPtr == NULL) {
                /* there is only left branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->LPtr;
                free(*tmp);
                *tmp = NULL;
            }
            else
                /* there are both branches, but that is for another topic*/
        }
    }
}

如果没有分支连接到我正在删除的节点，此代码可以正常工作 . 我希望 *tmp = NULL; 行存在问题，我将地址丢失到分支的其余部分，但另一方面，如果不包括此行，我会得到一个SEGFAULT，我试图找出原因 .

编辑：

好的，现在我知道错误在哪里 . 这是愚蠢的错误，我应该使用 tBSTNodePtr tmp; 而不是 *tBSTNodePtr tmp;

c binary-search-tree nodes

2 回答

  • 1

    你有使用指针的问题 . 如果我们有 sometype *ptr 并且我们检查这个ptr是否有一些空间我们写 (ptr!=NULL) . *ptr 正在引用值本身，例如指向您的structre . 阅读有关C中指针类型的更多信

    回复于
  • 0

    你的删除逻辑是错误的

    if ((* RootPtr)->LPtr == NULL) {
                /* there is only right branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->RPtr;
                free(*tmp);
                *tmp = NULL;
            }

    在此代码中，您将删除所需的节点，但不添加该节点的子根

    if ((* RootPtr)->LPtr == NULL) {
                /* there is only right branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->RPtr;
                free(*tmp);
                *tmp = NULL;
                insert(RootPtr);  //insert the child node again in the tree
            }
    回复于

相关问题