我正在尝试用 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。我很感谢任何能够指出我的问题或帮助我朝正确方向前进的人。您可以在以下位置查看我当前的 BST 实现:https://github.com/PuffNotes/C/blob/master/data_structs/binary_tree.c https://github.com/PuffNotes/C/blob/master/data_structures/binary_tree.c如果需要的话。我最近开始尝试每天编程来获得一些技能,并认为自己是C初学者(仅供参考)。谢谢。