二进制搜索树-实现“搜索”功能

Question

我正在尝试实现一个二叉查找树，但是“搜索”函数对于除了根之外的每个条目都返回了错误的值。

该函数应返回其值与键参数匹配的节点的地址，如果节点不存在，则返回 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

我知道每个节点的“左”和“右”指针链接正确，因为“delAll”函数成功删除了所有节点。

将“cout”语句添加到“search”函数表明该函数似乎返回了正确的地址。为什么从主主调用时会打印错误的地址？

Answer 1

你差点就成功了。因为搜索函数是递归的，所以它必须返回结果。

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
}