Двоичное дерево поиска - реализация функции поиска - PullRequest
Новая
       7

Двоичное дерево поиска - реализация функции поиска

0 голосов
/ 17 сентября 2018

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

Функция должна возвращать адрес узла, значение которого соответствует параметру ключа, или NULL, если узел не существует. 

#include <iostream>
#include <string>
#include <vector>

using namespace std;
struct TreeNode {
    string data;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
};

int main()
{
    TreeNode* search(TreeNode* root, string key);
    TreeNode* insert(TreeNode* root, TreeNode* parent, string key);
    void delAll(TreeNode* root);

    vector<string> vals{"yo", "check", "boy", "hope", "this", "doesn't", "break"};
    TreeNode* root = NULL;

    // Build tree
    for (auto key : vals)
    {
        root = insert(root, NULL, key);
    }

    cout << endl;

    // Search for all keys
    for (auto key: vals)
    {
        cout << key << " found at " << search(root, key) <<  endl;
    }

    delAll(root);

    return 0;
}
void delAll(TreeNode* root)
{
    if (root == NULL)
        return;

    delAll(root->left);
    TreeNode* next = root->right;

    delete root;

    delAll(next);
 }
TreeNode* search(TreeNode* root, string key)
{
    if (root == NULL)
        return NULL;
    if (root->data == key)
        return root;

    if (key < root->data)
        search(root->left, key);
    else
        search(root->right, key);
}
TreeNode* insert(TreeNode* root, TreeNode* parent, string key)
{

    if (!root)
    {
        root = new TreeNode;
        root->data = key;
        root->left = NULL;
        root->right = NULL;
        root->parent = parent;
        cout << "Added \"" << key << "\" at " << root << endl;
    }
    else if (key > root->data)
        root->right = insert(root->right, root, key);
    else
        root->left = insert(root->left, root, key);    

    return root;
}

Когда я запускаю код, я получаю следующее: 

Added "yo" at 0x5574f9b94f60
Added "check" at 0x5574f9b953b0
Added "boy" at 0x5574f9b953f0
Added "hope" at 0x5574f9b95430
Added "this" at 0x5574f9b95470
Added "doesn't" at 0x5574f9b954b0
Added "break" at 0x5574f9b954f0

yo found at 0x5574f9b94f60
check found at 0x7ffe97caf730
boy found at 0x7ffe97caf730
hope found at 0x7ffe97caf730
this found at 0x7ffe97caf730
doesn't found at 0x7ffe97caf730
break found at 0x7ffe97caf730

Я знаю, что указатели "left" и "right" каждого узла связаны правильно, потому что функция "delAll" успешно удаляет все узлы.

Добавление операторов «cout» в функцию «search» показывает, что функция, похоже, возвращает правильный адрес. Почему при вызове с основного печатается неправильный адрес?

1 Ответ

0 голосов
/ 17 сентября 2018

У тебя почти было это. Поскольку функция поиска является рекурсивной, она должна возвращать свой результат. 

TreeNode* search(TreeNode* root, string key)
{
    if (root == NULL)
        return NULL;
    if (root->data == key)
        return root;

    if (key < root->data)
        return search(root->left, key);  // return this value
    else
        return search(root->right, key); // return this value
    return NULL; // never hit
}
...