c - 二叉树递归搜索c代码[不是二叉搜索树]

Question

我的代码的问题是，当搜索左孩子值时，由于递归级别，它会返回并检查右孩子。并且返回不正确。我找不到克服它的方法。

node * search(node *ptr,int key)
{
    if(ptr->data==key)
        return ptr;
    else
    {
        if(ptr->lchild!='\0')
            search(ptr->lchild,key);
        else
            return '\0';
        if(ptr->rchild!='\0')
            search(ptr->rchild,key);
        else
            return '\0';
    }
}

Answer 1

或许像这样

node * search(node *ptr,int key)
{
    node *pwk;
    if(ptr == NULL) return NULL;
    if(ptr->data==key)
        return ptr;
    if(NULL!=(pwk=search(ptr->lchild,key)))
        return pwk;
    if(NULL!=(pwk=search(ptr->rchild,key)))// or return search(ptr->rchild,key);
        return pwk;
    return NULL;
}

Answer 2

Node *search(Node *ptr, int key)
{
    Node *found;
    if ( !ptr || ptr->data == key) return ptr;

    found = search(ptr->lchild, key);

    return (found) ? found : search(ptr->rchild, key);
}

注意：两者都使用 和||短路评估，这使我可以将条件数量减少到一个。?:if(...)

更新：如果允许我们使用“残缺三元”运算符 gnu-extension，我们也可以避免使用该变量：

Node *search2(Node *ptr, int key)
{
    if ( !ptr || ptr->data == key) return ptr;

    return search2(ptr->lchild, key) ?: search2(ptr->rchild, key);
}

添加另一个三元会完全删除if(...)：

Node *search3(Node *ptr, int key)
{
    return ( !ptr || ptr->data == key) 
        ? ptr
        : search3(ptr->lchild, key) ?: search3(ptr->rchild, key);
}

Answer 3

这是正确的。尝试这个：

node * search(node *ptr,int key)
{
    if(ptr->data==key)
        return ptr;
    else
    {
        node *current = NULL;
        if(ptr->lchild != NULL)
            current = search(ptr->lchild,key);

        if(current == NULL) /* not found in the left subtree */
        {
            if(ptr->rchild != NULL)
                current = search(ptr->rchild,key);
        }
        return current;
    }
}

Answer 4

node * search(node *ptr,int key)
{
    Node * p;

    // Found the key, return the pointer to the node
    if (ptr->data==key)
        return ptr;

    if (ptr->lchild != NULL)
    {
        p = search(ptr->lchild,key);
        // Found the key, return the pointer to the node
        if(p != NULL)
            return p;
    }
    // Didn't find it in the lchild, so search rchild
    if (ptr->rchild != NULL)
    {
        p = search(ptr->rchild,key);
        // Found the key, return the pointer to the node
        if(p != NULL)
            return p;
    }

    // Not found in left or right child, return NULL
    return NULL;
}

避免\0在这种情况下使用。\0用于空字符。NULL用于空指针。虽然两者通常都是 0，但最好NULL用于指针。检查此问题以获取更多详细信息 - NULL、'\0' 和 0 之间有什么区别