Рекурсивный поиск в двоичном дереве

Question

Я новичок, и я застрял на функции, которая ищет неупорядоченное двоичное дерево для заданного ключа. Узел состоит из значения и указателей на левый и правый узел. Вот мой код:

node *btree::search(int key, node *leaf){
    if(leaf != NULL)
    {
        if(key == leaf->value)
        {
            return leaf;
        }
        search(key, leaf->left);
        search(key, leaf->right);

    }
    else
    {
        return NULL;
    }
}

node *btree::search(int key){
    return search(key, root);
}

В некоторых случаях моя функция возвращает правильный узел, но в других это ошибка времени выполнения. Что с этим не так и что можно сделать, чтобы это исправить? И мне не разрешено использовать какие-либо внешние библиотеки, такие как queue или другие.

Answer 1

Это довольно частая ошибка новичков. Ваша рекурсивная функция возвращает указатель узла, но когда вы выполняете рекурсивные вызовы, вы игнорируете возвращаемое значение.

    search(key, leaf->left);
    search(key, leaf->right);

Это должно выглядеть так

    node* ptr = search(key, leaf->left);
    if (ptr != NULL)
        return ptr;
    else
        return search(key, leaf->right);

Т.е. вернуть узел, найденный поиском в левом поддереве, но если это NULL, то выполните поиск в правом поддереве и вернуть найденный там узел (если есть).

Когда вы пишете рекурсивный код, вы должны думать не только о рекурсивных вызовах, но и о том, что возвращается из рекурсивных вызовов.

Answer 2

Вы вызываете неопределенное поведение, поскольку не все пути кода ваших рекурсивных функций возвращают значение. Это может привести к «ошибке времени выполнения», ошибке sh или просто к непредсказуемому результату.

Кстати, преимущество дерева поиска обычно состоит в том, что вы получаете среднее время доступа к вашим элементам во время выполнения. сложность n * log (n). Но для этого дерево необходимо упорядочить, и я не могу себе представить допустимый вариант использования неупорядоченного двоичного дерева; в этом случае связанный список тоже подойдет.

В случае упорядоченного дерева:

node *btree::search(int key, node *leaf){
    if(leaf != NULL)
    {
        if(key == leaf->value) {
            return leaf;
        } else if (key < leaf->value) {
            return search(key, leaf->left);
        } else {
            return search(key, leaf->right);
        }
    }
    else
    {
        return NULL;
    }
}

В случае неупорядоченного дерева:

node *btree::search(int key, node *leaf){
    if(leaf != NULL)
    {
        if(key == leaf->value) {
            return leaf;
        }
        leaf = search(key, leaf->left);
        if (! leaf) {
          leaf = search(key, leaf->right);
        }
        return leaf;
    }
    else
    {
        return NULL;
    }
}