搜索二叉树

Question

我正在编写一个迭代函数来在二叉树中搜索特定值。 在我了解如何泛化类之前，它被本地化为有符号整数。

假设我的类是 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 没有子节点，则两者的计算结果都为零，我将过早退出循环（我永远不会根据 next 的值检查搜索到的 val）。

2）如果next有一个孩子，但你要查找的数据应该在树的空一侧，next将被设置为0，并且它会再次循环，左右比较next（即0）像 while(0->left()) 这样的树，导致未定义的行为。

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

Answer 1

我认为你应该测试循环中的 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;
}

Answer 2

试试这个：

while (next != NULL) ？

Answer 3

首先，我不确定你为什么要返回一个 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;
}

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