二叉树的递归搜索同时返回 true 和 false

Question

对于一个赋值，我应该想出一个名为 all_less 的递归函数，它接受一个指向 any 任意树的指针（TN<T>* ) 和一个 T 参数。如果所有值都小于 T 参数，则 returns 为真，否则 returns 为假。

我的 Tree class 的实例变量是这样的：

T      value;
TN<T>* left;
TN<T>* right;

all_less 的函数原型如下所示：

template<class T>
bool all_less(TN<T>* t, T v)

因为我必须考虑一个未排序的二叉树，所以我认为递归地向下遍历每个子树并检查每个值就可以了。测试完此功能后：

template<class T>
bool all_less(TN<T>* t, T v)
{
    if(v <= t->value) {
        return false;
    } else if(v > t->value) {
        if(t->right != nullptr && t->left != nullptr) {
            all_less(t->right, v);
            all_less(t->left, v);
        }
    }
    return true;
}

在几乎总是返回 true 的函数出现一些问题后，我在 return true 和 return false 之前放置了一些打印语句以查看发生了什么。

举个例子，假设我们在二叉树中有值 12、15、14、5。运行我的函数使用：

TN<int>* t;
std::cout << all_less(t, 15);

作为输入，会输出这个：

true
false
true
true

即使返回了一次 false，最终结果还是 true。我如何得到它，以便如果它 returns false，函数 returns false 并立即停止？还有更好的方法来实现这个功能吗？我最初确实有几个额外的 if-else 语句来检查 right/left 子树是否为 null 并从那里继续，但这些似乎实际上没有做任何事情。

Answer 1

你的函数：

template<class T>
bool all_less(TN<T>* t, T v)
{
    if(v <= t->value) {
        return false;
    } else if(v > t->value) { // Why do you need this check?
        if(t->right != nullptr && t->left != nullptr) {
            // This is wrong because it's possible for one them to
            // nullptr while the other is not.

            all_less(t->right, v);
            all_less(t->left, v);
            // The above function calls are no op. You are calling
            // the function recursively but are ignoring the return
            // values.
        }
    }
    return true;
}

这应该有效：

template<class T>
bool all_less(TN<T>* t, T v)
{
   if(v <= t->value) {
      return false;
   }

   if(t->right != nullptr )
   {
      if ( !all_less(t->right, v) )
      {
         return false;
      }
   }

   if ( t->left != nullptr)
   {
      if ( !all_less(t->left, v) )
      {
         return false;
      }
   }
   return true;
}

p.s。未经测试的代码。

Answer 2

您忽略了递归调用的 return 值。

The end result would end up true, even though a false was returned once.

那个 false 是 return 从另一个函数调用中编辑出来的，已经消失在天空中的大 bitbucket 中。

递归函数的工作方式与任何其他函数完全相同 - 如果您有

int f() { return 0:}
int g(int x) { 
    if (x == 0) 
        f(); 
    return 1; 
}

g(0) 将 return 1，即使 0 是 "returned once".
如果 g(0) 应该 return f() 的值，它必须明确地这样做：

int g(int x) { 
    if (x == 0) 
        return f(); 
    return 1; 
}

您还假设所有节点都有零个或两个子节点。

如果采用空树中的所有项都小于该值的约定，可以这样写

template<class T>
bool all_less(TN<T>* t, T v)
{
    return !t
         || (  t->value < v
            && all_less(t->right, v)
            && all_less(t->left, v));
}

二叉树的递归搜索同时返回 true 和 false

Recursive search on binary tree returning both true and false

c++

tree

recursion

binary-tree