C - функция рекурсивного поиска находит ключ и возвращает NULL

Question

Эта функция должна возвращать указатель на узел со значением ключа, но вместо этого перебирает значения до тех пор, пока не достигнет значения ключа, и вместо этого возвращает NULL.Я не уверен почему.

BST_Node *BST_search(BST_Node *root, int bar, double index){ 
if (root==NULL){
    return root;
}

double queryKey=(10.0*bar)+index;

if (queryKey==((10.0*root->bar)+root->index)){ 
    return root;
} 
if (queryKey<((10.0*root->bar)+root->index)){ 
    return BST_search(root->left, bar, index);
}
else if (queryKey>((10.0*root->bar)+root->index)){ 
    return BST_search(root->right, bar, index);
    }
}

Спасибо за вашу помощь.

Answer 1

Я думаю, @bruceg правильно намекает, почему вы всегда получаете ноль. Сравнение с плавающей точкой в ​​поисках точного равенства может потерпеть неудачу.

Попробуйте с этими правками:

// Your tolerance for equality, may need to adjust depending your use-case
#define EPSILON 0.0000001  

BST_Node *BST_search(BST_Node *root, int bar, double index){ 
    if (root==NULL){
        return NULL;
    }

    double queryKey= 10.0*bar+index; // consider passing this as parameter to avoid recomputing on every call
    double rootKey = 10.0*root->bar+root->index;  
    if (queryKey<(rootKey - EPSILON )){ 
        return BST_search(root->left, bar, index);
    }
    if (queryKey>(rootKey + EPSILON)) { 
        return BST_search(root->right, bar, index);
    }
    // Equality is assumed if we reach this code
    return root;
}