-1

我正在编写一个迭代函数来搜索二叉树的某个值。在我了解如何泛化类之前，这已本地化为带符号的整数。

假设我的类是 BinarySearchTree，它有一个指向树根节点的指针。还假设节点是通过插入函数插入的，并且具有指向两个子节点的指针。这是 Node 结构的一个非常简略的版本：

struct Node
{
   public:
      Node *left_, *right_;
      int value_

      Node(int val) : value_(val), left_(0), right_(0) { }
      //done in this manner to always make sure blank children are
      //init to zero, or null
      Node(int val, Node *left, Node *right) : value_(val), left_(0), right_(0) 
          { left_ = left; right_ = right; } 
}

因此，您可以放心地假设节点的 uninit 指针将为 NULL。

这是我的代码：

int BinarySearchTree::search(int val)
{
    Node* next = this->root();

    while (next->left() != 0 || next->right () != 0)
    {
        if (val == next->value())
        {
            return next->value();
        }    
        else if (val < next->value())
        {
            next = next->left();   
        }
        else if (val > next->value())
        {
            next = next->right();
        }
    } 

    //not found
    return 0;
}

朋友拒绝此代码有两个原因：

1) 如果 next 没有子节点，则两者都将评估为零，并且我将过早退出循环（我永远不会检查搜索到的 val 与 next 的值）。

2）如果next有一个孩子，但是你要搜索的数据应该在树的空边，next将被设置为0，它会再次循环，比较next（即0）左右树之类while(0->left())的，导致未定义的行为。

有人告诉我，这两个问题的解决方案都在于循环条件，但我看不出我能做些什么来轻松解决这种情况。Stack Overflow 社区可以提供任何见解吗？

4

3 回答 3

2

我认为您应该测试循环中的 next 是否为 NULL，如下所示：

int BinarySearchTree::search(int val)
{
    Node* next = this->root();

    while (next)
    {
        if (val == next->value())
        {
            return next->value();
        }    
        else if (val < next->value())
        {
            next = next->left();   
        }
        else if (val > next->value())
        {
            next = next->right();
        }
    } 

    //not found
    return 0;
}
于 2009-07-11T03:45:57.070 回答
1

试试这个：

while (next != NULL)?

于 2009-07-11T03:45:03.140 回答
0

首先，我不确定你为什么要返回一个 int。如果您在树中搜索 0 怎么办。你可能想要这样的东西：

bool BinarySearchTree::Search(int val) {
  Node* current = root();
  while (current != NULL) {
    // Check if it's here
    if (val == current->value()) {
      return true;
    }
    if (val < current->value()) {
      current = current->left();
    } else {
      current = current->right();
    }
  }
  // Not found
  return false;
}

请注意循环不变量：在每个循环的开始，您处于一个需要“处理”的非空节点。首先检查它是否是您想要的节点。如果不是，则创建一个分支，并让循环决定分支是否“好”（即 - 非空）。然后，您将让下一个循环迭代负责测试。

于 2009-07-11T03:57:41.117 回答