二进制搜索树：在插入函数中丢失指针

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

在使用这个功能，插入一个节点工作得很好（大概是因为树形>根是空的，所以它退出，如果语句中），但是当我尝试插入第二个并离开此功能，树中只有第一个节点。

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

来源

2012-03-16 Joshua Soileau

投票结束：要求陌生人通过检查发现代码中的错误并不是富有成效的。您应该通过使用调试器或打印语句来识别（或至少隔离）问题，然后返回一个更具体的问题。 – 2012-03-16 22:59:11

我的错误，我会看看我是否可以缩小范围。 – 2012-03-16 23:17:43

的问题是在这里：

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或right。

来源

2012-03-16 22:58:03

二进制搜索树：在插入函数中丢失指针

回答

相关问题