检查树节点等于一个值

Question

我正在尝试为任意二叉树编写一个递归函数，该函数接受一个值和一个叶节点，并检查叶节点是否具有该值。这就是我现在的大致情况。

bool tree_eq(value, N* node){
  if (node == nullptr){
    return false;
    }
  else{
    if node->value == value{
      return true;
    }
    else{
      return tree_eq(value, N->left);
      return tree_eq(value, N->right);
    }

我知道我无法 return 两件事，这是我正在努力解决的部分。如果给定根而不是叶，如何递归检查右侧和左侧？谢谢

Answer 1

你需要知道节点是在左侧还是右侧（这边并不重要），所以你可以说：

 ...
 else {
    return (tree_eq(value,N->left) || tree_eq(value,N->right) );
 }

这些将导致深度优先搜索，其中始终考虑最左边的节点分支。

Answer 2

当你的树未排序时，将你的结尾 else 子句从

更改为

 return tree_eq(value, N->left);
 return tree_eq(value, N->right);

并尝试'Or'这两个结果，如

 return (tree_eq(value, N->left) ||
         tree_eq(value, N->right));

如果您的树已排序，您只需要在一侧或另一侧进行 dfs，而不是同时进行。

注意'||'如果在左分支中找到，则不会调用右分支。

检查树节点等于一个值

Checking tree node equal to a value

c++

tree

recursion