バイナリツリーを検索する

Question

私はある値のバイナリツリーを検索するための反復関数を書いています。これは、クラスをジェネリック化する方法に入るまで、signed intにローカライズされています。

私のクラスはBinarySearchTreeであり、ツリーのルートノードへのポインタを持っているものとします。また、ノードが挿入関数を介して挿入され、2つの子へのポインタを持つとします。

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をチェックしません）。

2）次の子が1つの子であるが、検索しているデータがツリーの空の側にある場合は、次に0が設定され、次の（0）と左と右のツリーはwhile(0->left())のようになり、結果として未定義の動作が発生します。

私は、両方の問題に対する解決策がループ状態にあると言われていますが、私は簡単に状況を改善するために何ができるのかわかりません。スタックオーバーフローのコミュニティは何か洞察を提供できますか？

while (next != NULL)：

Answer 1

私は次のようにのようなあなたのループ内で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

はこれを試してみてください？

Answer 3

まず、私はなぜあなたがintを返すされているかわかりません。ツリー内で0を検索している場合はどうなりますか？各ループの最初に、あなたは「プロセス」に必要なnull以外のノードである：ループ不変ということに注意してください

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

：あなたは、おそらくこのような何かをしたいです。最初に、それがあなたが望むノードであるかどうかを確認します。そうでない場合は、ブランチを作成し、ブランチが「良い」（つまり、非ゼロ）かどうかをループに決定させます。それで、次のループの反復でテストができるようにします。