c++ - B 树递归搜索 C++

Question

该函数递归调用自身搜索 Btree，如果找到值则返回 true，如果未找到则返回 false。如果找不到，我还希望它在最后一次“找不到”。它工作正常，除了它多次说“未找到”（每次它下降到它说未找到的水平），因为它调用了自己。

bool lookup(int val, btnode *n) //returns true/false if value is in btree
{

if (n==NULL) return false; //empty tree

for (int i=0;i< n->count;i++) //check in present node for the val
    if(n->value[i]==val)
    {
        flag = true;
        return true;
    }



//check in child node

    for(int i =0;i<n->count;i++) //check for child node
    {   if(val < n->value[i])
        {   cout<<"checking a different node."<<endl;
            lookup(val,n->child[i]);
        }
    }
    if(val > n->value[(n->count)-1])
    {
        cout<<"searching a right subtree"<<endl;
        lookup(val, n->child[n->count]);
    }
if (flag==false)
return false;
else return true;
}

bool lookup2(int val, btnode *n)
{
if(lookup(val, n)==false)
{
    cout<<"not found"<<endl;
    return false;
}
else
{
    cout<<"Found it"<<endl;
    return true;
    }
}

Answer 1

您可能想要创建一个调用此查找函数并进行打印的辅助方法。就像是：

bool lookup_print(int val, btnode *n) {
    bool found = lookup(val, n);
    if (found) {
        cout << "Found it!" << endl;
    } else {
        cout << "Not found..." << endl;
    }
    return found;
}

此外，您需要确保递归调用在找到节点时返回它们的值。所以在你递归的任何地方，你都会想要这样的东西：

bool found = lookup(val,n->child[i]);
if (found) {
    return found;
}