gpt4 book ai didi

c - 二叉搜索树 : lost pointer in insertion function

转载 作者:行者123 更新时间:2023-11-30 15:58:27 25 4
gpt4 key购买 nike

用 BST 做一个项目,我的插入函数中的某个地方有逻辑错误,只是似乎找不到它。

插入功能:

int bst_insert (bst_t *tree, bst_key_t key)
{
bst_node_t *node, *temp_node;
if( tree == NULL ) {
printf("Invalid tree pointer.\n");
return;
}
if( tree->root == NULL ) {
node = (bst_node_t *)malloc(sizeof(bst_node_t));
node->left = node->right = NULL;
node->key = key;
tree->root = node;
return 1;
}
temp_node = tree->root;
while(1) {
if( temp_node == NULL ) {
node = (bst_node_t *)malloc(sizeof(bst_node_t));
node->left = node->right = NULL;
node->key = key;
temp_node = node;
return 1;
}
if( temp_node->key == key ) {
temp_node->data_ptr = data;
return 0;
} else if( key < temp_node->key ) {
temp_node = temp_node->left;
} else if( temp_node->key < key ) {
temp_node = temp_node->right;
}
}
}

在使用这个函数时,插入一个节点效果很好(可能是因为tree->root为空,所以它在if语句中退出),但是当我尝试插入第二个节点并离开这个函数时,树只其中有第一个节点。

如果我忘记提供任何相关信息,请告诉我。

最佳答案

问题出在这里:

temp_node = tree->root;
...
temp_node = node;

您假设当您执行第二次分配时,它实际上会影响 temp_node 指向的节点。但事实上,它只是替换了 temp_node 的内容,而没有更改任何其他内容(它是一个局部变量)。

一种解决方案是使用一个指向“节点指针”的指针。然后,当您更改该指针指向的值时,您实际上是在“改变世界”,而不是更改局部变量。像这样的东西:

bst_node_t **temp_node;
...
temp_node = &tree->root;

/* To change the value that temp_node is pointing to */
*temp_node = node;

/* To change temp_node itself */
...
} else if( key < temp_node->key ) {
temp_node = &temp_node->left;
} else if( temp_node->key < key ) {
temp_node = &temp_node->right;
}

可以在不使用指针到指针的情况下解决此问题,但是您必须记住前一个(父)指针,以及是否需要更改 left正确

关于c - 二叉搜索树 : lost pointer in insertion function,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9745468/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com