搜索二叉树

假设我的类是BinarySearchTree,它有一个指向树的根节点的指针。还假设节点是通过insert函数插入的,并且有指向两个子节点的指针。以下是节点结构的简化版本:

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()) ,导致未定义的行为。