c++ - 为什么这个递归函数的行为与预期的不同？

Question

我正在写一棵二叉树，我被困在一个搜索函数上，该函数接受一个值 x 并确定它是否是树中的叶子。

这是我的:

bool search(Node<T>* &currentNode, const T& x) const
{
    /* Base Case */
    if ( currentNode != nullptr && (leaf(currentNode) == true) && currentNode->data == x )
    {
        return true;
    }

    /* Recursive Case */
    else {

        if (currentNode != nullptr)
        {
        search(currentNode->left, x);
        search(currentNode->right, x);
        }

        //If first if condition is not met for all values then value must not exist
        return false;

        }


bool leaf(Node<T>* currentNode) const 
{
    if (currentNode != nullptr)
    {
    return ((currentNode->left == nullptr && currentNode->right == nullptr) ? true : false);        
    }
    else  
    {
        return true;
    }
}

代码总是返回false，为什么第一个IF语句从未被触发？

编辑: 代码调用搜索:

for (int i = 0; i < 101; i++)           
            if ((t.search(i) == true) ? cout << "LEAF FOUND: " << i  << endl : cout << " NOT A LEAF: " << i << endl);

Answer 1

处理递归可能很棘手 :D。

除非根节点是叶子，否则您的代码将始终返回 return false 您的代码返回 true 给调用的函数，而不是一直返回到原始调用者(在递归之前)

假设您的树具有三个元素，并且该项目位于左叶中 所以在根节点中你用左节点调用自己所以它返回 true 给调用者(根节点)，根节点对此不做任何事情并继续执行。

这可以通过添加一个 if 语句来检查您调用的函数的返回值来简单地解决

if (currentNode != nullptr)
{
    if(search(currentNode->left, x)) return true;
    if(search(currentNode->right, x)) return true;
}
return false;