测试二叉树的成员

Question

我目前正在尝试遍历二叉树以检查某些值是否在其中。for 循环正在测试 1 到 50 之间的所有值，并将为每个匹配的值返回 true。

这是当前的树:

              8
            /    \
           4      38
          / \    /  \
         3  7   31  39
        /      / \   \
       1     16  33  45

IntegerData test(0);
for (int i = 0; i < 50; i++) {
  test.value = i;
  if (bt->member(&test)) {
   cout << "member true for " << i << endl;
  }
}

现在我必须实现成员函数，我有正确的想法下来，但它在检查根后停止，根 -

bool BinaryTreeNode::member(Data * data) {
BinaryTreeNode *newNode = new BinaryTreeNode(data);
   if (data->compareTo(this->nodeData) == 0) {
       return true;
   }
   else if (data->compareTo(this->left->nodeData) == 0) {
       return true;
       newNode->member(data);
   }
   else if (data->compareTo(this->right->nodeData) == 0) {
       return true;
       newNode->member(data);
   }
   return false;
}

前面所述的for循环打印输出

member true for 8
member true for 4
member true for 38

但仅此而已。

有人会通过伪代码或脚本提供一些方向吗？你不必给我代码，因为我想自己弄清楚。谢谢。

Answer 1

这是一个不可靠的树遍历算法的实现。但是，如果您想保留现有内容，请考虑将return语句的位置与其下面的语句进行交换。

然而，这就是我如何重构你的代码

bool member(BinaryTreeNode *node, Data *data) {
   // Create wrapper for data
   BinaryTreeNode *newNode = new BinaryTreeNode(data);

   if (data->compareTo(node->nodeData) == 0) { // Check the current node only!
       return true;
   else  // delegate the rest of the tree to recursion.
       if (member(node->left,  data)) // Check the left
       || (member(this->right, data)) // Check the right
           return true;
       else
         return false;
}

话说回来，你应该测试一下，让我知道它是否有效。我来自Ruby，我已经有一段时间没有用C编程了。

哦，当您想在驱动程序代码中调用它时，请将二叉树的根节点作为第一个节点传递。如果这是一个类或模块函数，请尝试传递 self。我的希望是自我指向根节点

Answer 2

假设这是一个有序的 BST：

bfs(root) {
    if (root is null) 
        return false // if we get to leaves without finding the target, it's not there
    if (root is target value)
        return true // if we found it, then YAY
    if (root is less than target value)
        return bfs(right child) // if target > root, target must lie in right subtree
    return bfs(left child) // otherwise target < root, check left subtree

如果你检查子节点，你会检查其中的一些两次（一次是子节点，一次是根节点）。这也使得代码更加复杂，这可能是导致你的逻辑错误的原因。

编辑：刚刚找到了算法的解释。

编辑：我还想强调你犯的一个小错误，我已经看到很多人这样做 - 调用一个返回某些东西但不对返回值做任何事情的函数。

我说的台词是新节点-