代码之家  ›  专栏  ›  技术社区  ›  jkeys

搜索二叉树

  •  -1
  • jkeys  · 技术社区  · 17 年前

    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; } 
    }
    

    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;
    }
    

    while(0->left()) ,导致行为不明确。

    我被告知,这两个问题的解决方案都存在于循环条件中,但我看不出我能做些什么来轻松补救这种情况。Stack Overflow社区能提供任何见解吗?

    3 回复  |  直到 17 年前
        1
  •  2
  •   Tom Dalling    17 年前

    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;
    }
    
        2
  •  1
  •   Somnath Muluk    14 年前

    while (next != NULL) ?

        3
  •  0
  •   Tom    17 年前

    首先,我不知道你为什么返回一个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;
    }