Поиск в рекурсивном бинарном дереве поиска - PullRequest
Новая
       6

Поиск в рекурсивном бинарном дереве поиска

0 голосов
/ 19 октября 2018

Я использую рекурсию для поиска элемента в моем бинарном дереве поиска, но мой код перестает работать, если элемент отсутствует в BST. 

void tree::searching(node *root,int key)
{
    if(root->key==key||root==NULL)
    {
       cout<<"Congratulation Element found in the BST"<<"\n";
       return;
    } else {
        if(key<root->key)
        {
           searching(root->left,key);
        } else {
           searching(root->right,key);
        }
    }
}

Ответы [ 3 ]

0 голосов
/ 19 октября 2018

Вы разыменовываете нулевой указатель здесь: 

if(root->key==key||root==NULL)
{
    cout<<"Congratulation Element found in the BST"<<"\n";
    return;
}

Оператор || сначала очищает левую сторону, и если это значение , то , он оценивает правую сторону.Таким образом, вы разыменовываете root перед проверкой, имеет ли он значение NULL.

Сначала выполните проверку NULL и вернитесь, если вы найдете указатель NULL: 

void tree::searching(node *root,int key)
{
    if (root == nullptr) {
        return;
    }

    if(root->key==key) {
        cout<<"Congratulation Element found in the BST"<<"\n";
    } else if(key<root->key)
        searching(root->left,key);
    } else {
        searching(root->right,key);
    }
}
0 голосов
/ 19 октября 2018

Вы печатаете слишком рано.Если программы перейдут на лист, они будут напечатаны, потому что выражение в первой части будет оценено как истинное.

void tree::searching(node *root,int key)
{
    if (root == nullptr)
    {
        return;
    }
    if(root->key==key)
    {
        cout<<"Congratulation Element found in the BST"<<"\n";
        return;
    }
    else
    {
        if(key<root->key)
        {
            searching(root->left,key);
        }
        else
        {
            searching(root->right,key);
        }
    }

 }
0 голосов
/ 19 октября 2018

Проблема

Если root будет nullptr в этом выражении: 

    if(root->key==key||root==NULL)

, вы сначала разыменуете нулевой указатель с помощью root->key, который является UB, перед проверкой, является ли это NULL.

Решение

Сделайте наоборот: 

    if(root==nullptr||root->key==key)

В этом случае, если root равен NULL, предложение if равнонемедленно исполненТолько если root будет не NULL, указатель будет разыменован.

Примечание: вы говорите, что элемент был найден, даже если элемент не найден (т.е. root достиг nullptr, даже не обнаружив правильный ключ).Подумайте о том, чтобы иметь разные случаи для nullptr (означает, что он не был найден) и равенства (означает, что он был найден).

...