0

現在、特定の値が範囲内にあるかどうかを確認するために、バイナリ ツリーをトラバースしようとしています。for ループは 1 から 50 までのすべての値をテストし、一致した値ごとに true を返します。

ここに現在のツリーがあります：

              8
            /    \
           4      38
          / \    /  \
         3  7   31  39
        /      / \   \
       1     16  33  45

IntegerData test(0);
for (int i = 0; i < 50; i++) {
  test.value = i;
  if (bt->member(&test)) {
   cout << "member true for " << i << endl;
  }
}

ここで、メンバー関数を実装する必要があり、正しいアイデアが得られましたが、ルート、ルート->左、およびルート->右をチェックした後に停止します。正しい形式の再帰を使用しているように感じますが、そうではないと思います。これが私のコードです：

bool BinaryTreeNode::member(Data * data) {
BinaryTreeNode *newNode = new BinaryTreeNode(data);
   if (data->compareTo(this->nodeData) == 0) {
       return true;
   }
   else if (data->compareTo(this->left->nodeData) == 0) {
       return true;
       newNode->member(data);
   }
   else if (data->compareTo(this->right->nodeData) == 0) {
       return true;
       newNode->member(data);
   }
   return false;
}

前述の for ループが出力されます

member true for 8
member true for 4
member true for 38

しかし他には何もありません。

誰かが擬似コードまたはスクリプトを介して何らかの方向性を提供しますか? 私は自分でそれを理解したいので、コードを提供する必要はありません。ありがとう。

4

2 に答える 2

1

これが順序付けられた BST であると仮定します。

bfs(root) {
    if (root is null) 
        return false // if we get to leaves without finding the target, it's not there
    if (root is target value)
        return true // if we found it, then YAY
    if (root is less than target value)
        return bfs(right child) // if target > root, target must lie in right subtree
    return bfs(left child) // otherwise target < root, check left subtree

ルートの値がターゲット値であるかどうかのみを確認します。子をチェックすると、それらの一部を 2 回チェックすることになります (1 回は子のとき、もう 1 回はルートのとき)。また、コードがより複雑になり、おそらく論理エラーが発生した可能性があります。

編集:アルゴリズムのこの説明を見つけました。

編集:また、多くの人が行っているのを見た、あなたが犯した小さな間違いを強調したいと思います-何かを返す関数を呼び出しますが、戻り値では何もしません。

私が話している線はnewNode->member(data);線です。再帰の次のステップを呼び出しましたが、結果を使用していません。つまり、プログラムは、ツリーの下位にあるターゲットを見つけるとバックトレースしません。再帰関数で戻り値を使用するには、return next_call()(この場合はreturn newNode->member(data);) が必要です。

于 2012-10-08T02:07:08.207 に答える
0

これは、ツリー トラバーサル アルゴリズムの不安定な実装です。ただし、持っているものを保持したい場合は、return ステートメントの位置をその下のステートメントに切り替えることを検討してください。

ただし、これは私があなたのコードをリファクタリングする方法です

bool member(BinaryTreeNode *node, Data *data) {
   // Create wrapper for data
   BinaryTreeNode *newNode = new BinaryTreeNode(data);

   if (data->compareTo(node->nodeData) == 0) { // Check the current node only!
       return true;
   else  // delegate the rest of the tree to recursion.
       if (member(node->left,  data)) // Check the left
       || (member(this->right, data)) // Check the right
           return true;
       else
         return false;
}

繰り返しますが、これをテストして、機能するかどうかをお知らせください。私は Ruby 出身で、しばらく C++ でプログラミングしていません。

ああ、ドライバー コードでこれを呼び出す場合は、バイナリ ツリーのルート ノードを最初のノードとして渡します。これがクラスまたはモジュール関数である場合は、 を渡してみてくださいself。私の希望は、ノードをself指すことですroot

于 2012-10-08T01:42:45.377 に答える