0

我目前正在尝试遍历二叉树以检查某些值是否在其中。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

但没有别的。

有人会通过伪代码或脚本提供一些指导吗？你不必给我代码，因为我想自己解决这个问题。谢谢。

4

2 回答 2

1

假设这是一个有序的 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

您只想检查根处的值是否是目标值。如果你检查孩子，你会检查他们中的一些人两次（一次是孩子，一次是根）。它还使代码更加复杂，这可能是导致您的逻辑错误的原因。

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

编辑：我还想强调你犯的一个小错误，我见过很多人都这样做 - 调用一个返回一些东西但没有对返回值做任何事情的函数。

我所说的线条是newNode->member(data);线条。在那里你调用了递归的下一步，但你还没有使用结果。这意味着您的程序一旦在树中找到较低的目标就不会回溯。要在递归函数中使用返回值，您必须拥有return next_call()（在这种情况下return newNode->member(data);）。

于 2012-10-08T02:07:08.207 回答
0

这是树遍历算法的一个不稳定的实现。但是，如果您想保留现有的内容，请考虑将 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. 我的希望是self指向root节点

于 2012-10-08T01:42:45.377 回答