3

我一直停留在这个简单的二叉搜索树上，因为我的主要问题是函数 bst_get() 中的 (BST * bst) 为 NULL。

typedef struct {
    char *key;
    void *value;
} KVP;
typedef struct bst {
    struct bst *left;
    struct bst *right;
    KVP kvp;
} BST;

此插入函数从输入文件中获取参数并进行相应排序

BST *bst_insert(BST *bst, char*key, void *value){
    if(bst==NULL){
        BST * tempBST = (BST * )malloc(sizeof(BST));
        //strcpy(tempBST->kvp.key , key);
        tempBST->kvp.key = key;
        tempBST->kvp.value = value;
        tempBST->left = NULL;
        tempBST->right = NULL;
        puts(key);
        return tempBST;
    }else
    //if(strcmp(key , bst->kvp.key) > 0){ // i tried to compare strings but it failed
    if(key > bst->kvp.key && bst != NULL){
        bst->right = bst_insert(bst->right , key , value);
        return bst;
    }
    else
    if(key < bst->kvp.key){
        bst->left = bst_insert(bst->left , key, value);
        return bst;
    }    
}

以及何时将该 BST 与密钥（来自另一个文件）进行比较，如下所示

KVP *bst_get(BST *bst , char *key)

    if(bst!=NULL){
        if(key==bst->kvp.key){
            return &bst->kvp;
        }
        else if (key > bst->kvp.key) {
           return bst_get(bst->right , key);
        } else if (key < bst->kvp.key){
           return bst_get(bst->left , key);
        } 
    }else{
        printf("BST IS EMPTY!\n");
    }
}

打印出“BST IS EMPTY”语句。我不知道我的 BST 发生了什么，因为我提到了其他类似的问题，似乎我在这里错过了一些重要的问题，并希望得到一些帮助。

感谢您的时间

4

3 回答 3

4

我还没有仔细阅读所有代码，但这部分是错误的：

if(key > bst->kvp.key && bst != NULL)

bst考虑进入此语句的 NULL场景。

首先，它将与key使用bst->kvp.key指针的bst进行比较。由于bst是 NULL，你刚刚遇到了一个崩溃的错误。（可能是分段违规）。

您需要颠倒顺序，以便在尝试使用指针之前检查 bst 是否为 NULL ：

if( (bst != NULL) && (key > bst->kvp.key) )

此外，根据您在此声明之前注释掉的代码，我认为您想尝试：

if( (bst != NULL) && strcmp(key , bst->kvp.key) > 0) {

这既可以防止 NULL 指针，又可以使用字符串比较而不是指针比较。

于 2013-04-03T13:41:27.163 回答
1

在 functionbst_get()中，key==bst->kvp.key比较指针，而不是字符串内容。用于strcmp比较字符串内容。比较密钥的所有其他地方也是如此。

于 2013-04-03T13:40:39.953 回答
0

当然，您将到达in的地步，bst因为您不断地使用 the或成员递归调用该函数。迟早会出现其中一个，导致您打印字符串。NULLbst_getleftrightNULL

如果您使用调试器单步执行代码和递归调用，您会注意到这一点。

于 2013-04-03T13:52:12.523 回答