c - 为什么我的 BST 根指针由于某些未知原因而改变？

Question

我正在尝试用 C 语言实现二叉搜索树数据结构，但我遇到了一个错误。由于我不明白的原因，我的指针值发生了变化。 (有关奇怪的输出，请参阅帖子底部 [删除功能和主要功能阐明输出来自何处])我的测试功能如下:

int main(void)
{
    Bst *bst = ( Bst* ) calloc( 1, sizeof( Bst ) );
    BstInsert( bst, 7 );
    BstInsert( bst, 8 );
    BstInsert( bst, 2 );
    BstInsert( bst, 1 );
    BstTraverse( bst );
    BstRemove( bst, 7); 
    printf("=========================\n");
    printf("Root Key: %d\n", bst->key );
    printf("Left Key: %d\n", bst->left->key );
    printf("Right Key: %d\n", bst->right->key );
    printf("Location: %p\n", &bst);
    BstTraverse( bst );

    return 0;
}

我的删除节点函数如下:

void BstRemove( Bst *root, int key ){
    //Seems like recursive algorithm would need doubly linked bst implementation
    Bst *temp_node = BstFind( root, key );
    Bst *parent_node = BstGetParent( root, key );
    Bst *replacement_node = ( Bst* ) calloc( 1, sizeof( Bst ) );
    if ( temp_node->key == root->key )
    {   
        if (root->left) replacement_node = BstMax( root->left );
        else if ( root->right ) replacement_node = BstMin( root->right );
        else replacement_node = NULL;
    }
    else if ( temp_node->left )
    {
        replacement_node = BstMax( temp_node );
        Bst *parent_replacement_node = BstGetParent( root, replacement_node->key );
        parent_replacement_node->right = NULL;
    }
    else if ( temp_node->right )
    {
        replacement_node = BstMin( temp_node );
        Bst *parent_replacement_node = BstGetParent( root, replacement_node->key );
        parent_replacement_node->left = NULL;
    }
    else
        replacement_node = NULL;

    if ( parent_node && key < parent_node->key )
        parent_node->left = replacement_node;
    else if ( parent_node )
        parent_node->right = replacement_node;

    if ( replacement_node )
    {
        if ( root->left->key != replacement_node->key ) replacement_node->left = temp_node->left;
        if ( root->right->key != replacement_node->key ) replacement_node->right = temp_node->right;
    }
    root = replacement_node;
    printf("Root Key: %d\n", root->key );
    printf("Left Key: %d\n", root->left->key );
    printf("Right Key: %d\n", root->right->key );
    printf("Location: %p\n", &root);
    free(temp_node);
}

输出如下:

1
2
7
8
Root Key: 2
Left Key: 1
Right Key: 8
Location: 0x7fffc5cf52e8
=========================
Root Key: 0
Left Key: 2
Right Key: 8
Location: 0x7fffc5cf5338
1
2
8
0
8

这让我如此困惑的原因是因为我使用的是指针。当 root->key 值在删除函数中为 2 时，我看不出有什么理由改变它，一旦它被处理
root->key 变为 0。我感谢任何能指出我的问题或帮助我朝正确方向发展的人。您可以在 https://github.com/PuffNotes/C/blob/master/data_structures/binary_tree.c 查看我当前的 BST 实现如有必要。我最近开始尝试每天编程以获得一些技能，并认为自己是 C 的初学者(供引用)。谢谢。

Answer 1

您没有更改根节点指针。它按值传递给删除函数，并且由于它肯定是删除的可行目标，因此它应该按地址传递，因为它可能会更改为不同的节点。注意:如果我在某处遗漏了一个 root，我深表歉意，但你的编译应该会捕捉到它)。

注意:我没有验证通过此代码是否正确甚至有效；但真正的提示是底部的 root = 出了问题，然后是打印输出，然后是调用者 (main()) 执行相同的打印输出并显示不同的根指针值。

void BstRemove( Bst **root, int key )
{
    //Seems like recursive algorithm would need doubly linked bst implementation
    Bst *temp_node = BstFind( *root, key );
    Bst *parent_node = BstGetParent( *root, key );
    Bst *replacement_node = ( Bst* ) calloc( 1, sizeof( Bst ) );
    if ( temp_node->key == (*root)->key )
    {   
        if ((*root)->left) replacement_node = BstMax( (*root)->left );
        else if ( (*root)->right ) replacement_node = BstMin( (*root)->right );
        else replacement_node = NULL;
    }
    else if ( temp_node->left )
    {
        replacement_node = BstMax( temp_node );
        Bst *parent_replacement_node = BstGetParent( (*root), replacement_node->key );
        parent_replacement_node->right = NULL;
    }
    else if ( temp_node->right )
    {
        replacement_node = BstMin( temp_node );
        Bst *parent_replacement_node = BstGetParent( (*root), replacement_node->key );
        parent_replacement_node->left = NULL;
    }
    else
        replacement_node = NULL;

    if ( parent_node && key < parent_node->key )
        parent_node->left = replacement_node;
    else if ( parent_node )
        parent_node->right = replacement_node;

    if ( replacement_node )
    {
        if ( (*root)->left->key != replacement_node->key ) replacement_node->left = temp_node->left;
        if ( (*root)->right->key != replacement_node->key ) replacement_node->right = temp_node->right;
    }
    *root = replacement_node;

    printf("Root Key: %d\n", (*root)->key );
    printf("Left Key: %d\n", (*root)->left->key );
    printf("Right Key: %d\n", (*root)->right->key );
    printf("Location: %p\n", root);
    free(temp_node);
}

像这样调用它:

BstRemove( &bst, 7); 

并习惯于通过地址传递根，因为当您开始编写平衡算法时，您将大量这样做。