首页 文章

对二叉树进行递归搜索，返回true和false

提问于
浏览 次
0

对于赋值，我应该提出一个名为 all_less 的递归函数，它接受一个指向 any 任意树（ TN<T>* ）和 T 参数的指针 . 如果所有值都小于T参数，则返回true，否则返回false .

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

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 之前放了一些print语句来看看发生了什么 .

举个例子，假设我们在二叉树中有值12,15,14,5 . 运行我的功能：

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

作为输入，将输出：

true
false
true
true

即使假一次返回，最终结果也会成立 . 如何获取它，如果它返回false，该函数返回false并立即停止？还有更好的方法来实现这个功能吗？我最初有一些额外的if-else语句来检查右/左子树是否为null并从那里继续，但那些似乎没有做任何事情 .

c++ recursion tree binary-tree

2 回答

  • 2

    您忽略了递归调用的返回值 .

    最终结果最终会成立，即使一次返回false也是如此 .

    那个 false 是从一个不同的函数调用返回的，并且已经消失在天空中的巨大bitbucket中 .

    递归函数与任何其他函数完全一样 - 如果有的话

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

    g(0) 将返回1，即使0是"returned once" .
    如果 g(0) 应返回 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));
}
    回复于
  • 0

    你的功能：

    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;
}

    附：未经测试的代码 .

    回复于

相关问题