-1

二分木で特定の値を検索する反復関数を作成しています。これは、クラスをジェネリック化する方法を説明するまでは、signed int にローカライズされています。

私のクラスが BinarySearchTree で、ツリーのルート ノードへのポインターがあるとします。また、挿入関数によってノードが挿入され、2 つの子へのポインターがあるとします。以下は 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;
}

このコードは、次の 2 つの理由で友人によって拒否されています。

1) next に子がない場合、両方ともゼロと評価され、途中でループを終了します (検索された val を next の値に対してチェックすることはありません)。

2) next に 1 つの子があるが、検索しているデータがツリーの空の側にある必要がある場合、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;
}

ループ不変であることに注意してください。各ループの開始時に、「処理」する必要がある非 null ノードにいます。最初に、それが必要なノードかどうかを確認します。そうでない場合は、分岐を作成し、分岐が「適切」であった (つまり、null でない) かどうかをループに判断させます。次に、次のループ反復でテストを処理します。

于 2009-07-11T03:57:41.117 に答える