为什么我的BST根指针由于某种未知原因而发生变化? [英] Why is my BST root pointer changing for some unknown reason?

问题描述

我正在尝试用C实现二进制搜索树数据结构，并且遇到了一个错误.我的指针值更改是由于我不了解的原因. (有关奇怪的输出，请参见文章底部[删除功能和主要功能说明输出来自何处]) 我的测试功能如下:

I am trying to implement a Binary Search Tree data structure in C, and I have run into a bug. My pointer value changes for a reason I do not understand. (Please see bottom of post for strange output [Delete function and main functions clarify where output comes from] ) My Test function below:

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;
}

下面的我的删除节点"功能:

My Delete Node function below:

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

之所以让我感到困惑，是因为我使用了指针.我发现在delete函数中将root-> key值更改为2并进行处理后，没有理由更改
root-> key变为0.对于任何能指出我的问题或朝正确方向提供帮助的人，我深表感谢.您可以在 https://github.com/PuffNotes上看到我当前的BST实现. /C/blob/master/data_structures/binary_tree.c (如有必要).我最近开始尝试每天进行编程以获取一些技能，并认为自己是C语言的初学者(仅供参考).谢谢.

The reason this confuses me so much is because I am using a pointer. I see no reason for the root->key value to change when it is 2 within the delete function, and once it is processed
root->key becomes 0. I am grateful for anybody who can point out my problem or help me in the right direction. You can see my current BST implementation at https://github.com/PuffNotes/C/blob/master/data_structures/binary_tree.c if necessary. I recently started trying to program everyday to gain some skills, and consider myself to be a beginner in C ( for reference ). Thank you.

推荐答案

您没有更改根节点指针.它按值传递给remove函数，并且由于它肯定是删除的可行目标，因此应按地址传递，因为它可能会更改为其他节点.注意:如果我错过了某个地方的root，我表示歉意，但是您的编译应该会捕获到它.)

You're not changing your root node pointer. It is passed by value to the remove function, and since it is certainly a viable target of the delete, it should be passed by address since it might change to a different node. Note: if I missed a root in there somewhere I apologize, but your compile should catch it).

注意:对于此代码正确无误，我没有通过否验证；但是真正的错误提示是底部的root =，然后是打印输出，然后调用方(main())执行相同的打印输出并显示了不同的根指针值.

Note: I made no validation pass on whether this code is correct or even works; but the real hint something was wrong was the root = at the bottom, followed by the print-out, then the caller (main()) doing the same print-out and showing a different root pointer value.

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); 

并习惯于按地址传递根，因为开始编写平衡算法时您会做很多操作.

And get used to passing the root in by address, as you will do plenty of it when you start writing balancing algorithms.

这篇关于为什么我的BST根指针由于某种未知原因而发生变化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！