二叉树中的搜索键

Question

我遇到的问题是，对于某些键，我的功能有效，但对于某些键却无效。如果树中没有具有该键的元素，则该函数应该 return 指向具有 key == givenKey 或 NULL 的节点的指针。这是结构，下面是函数。

typedef struct node
{
    int key;
    struct node *l, *r;
}NodeT;

NodeT *search(NodeT *root, int givenKey)
{
    if(root == NULL || root->key == givenKey)
        return root;
    search(root->l, givenKey);
    search(root->r, givenKey);
}

这是main函数的调用：

    NodeT *q = search(root, 9);
    NodeT *r = search(root, 7);
    printf("%p\n%p\n", q, r);

这是给定的二叉树：（例如 q 得到正确的地址，但是 r 将是 NULL 即使有一个元素 key = 7 在我们的二叉树中。

如果你能告诉我哪里出了问题，我将不胜感激，因为我尝试更改了很多次功能，但都没有用。我什至用调试器查看了我的代码，但它似乎没有太大帮助。提前致谢！

Answer 1

检查根是否包含密钥，并递归地检查子项。它 return NULL 如果没有找到具有该键的节点。

NodeT* search(NodeT* root, int givenKey)
{
    if (!root)
        return NULL;
    else if (root->key == givenKey)
        return root;

    NodeT* search_child_result = NULL;
    if (root->l)
    {
        search_child_result = search(root->l, givenKey);
        if (search_child_result)
            return search_child_result;
    }

    if (root->r)
    {
        search_child_result = search(root->r, givenKey);
        if (search_child_result)
            return search_child_result;
    }

    return search_child_result;
}

二叉树中的搜索键

Search key in binary tree

c

recursion

binary-tree

pointers

recursive-datastructures