6

私が混乱している簡単な質問があります。二分探索ツリーにキーと値のペアを持つという概念と、ツリーが構築されたときにどのように見えるかを知っています。

私が確信していないのは、そのキーが何であるかがわからない場合、そのような BST で値を検索する方法です。

例えば：

整数 (値として) と一意の整数 (キーとして) でいっぱいの二分探索木があるとします。そして、この BST で特定の整数 (たとえば 200) が発生する回数を数えたいとします。つまり、200 は「キー」ではなく「値」です。したがって、私はキーをまったく知りません。

BST全体ですべての「200」を検索するにはどうすればよいですか? これで単純な BST になり、キーはまったく必要ありませんか? 繰り返しますが、ツリーは値ではなく「キー」を使用して左の子と右の子に配置されます。

BST を初期化する方法のコード サンプルも提供できます。

void insertNode(TreeNode *&p, int key, int value)
{
  if (p == NULL) {
    p = new TreeNode;
    p->key = key;
    p->value = value;
    p->left = NULL;
    p->right = NULL;
    return;
  }

  if (key < p->key)
    insertNode(p->left, key, value);
  else
    insertNode(p->right, key, value);
}

どんな助けでも大歓迎です。

4

2 に答える 2

7

キーの代わりに値で検索したい場合、木が二分探索木であるという事実を利用することはできません。したがって、たとえば BFS を使用してツリー全体を反復処理する以外に選択肢はありません。

于 2013-03-16T20:40:04.087 に答える
1

二分探索木 (BST)は、迅速なアクセス、保存、および削除のためにデータを保存するのに非常に役立ちます。二分探索ツリーのデータはツリー ノードに格納され、それらに序数値またはキーが関連付けられている必要があります。これらのキーは、左側の子ノードの値が親ノードの値よりも小さく、右側の子ノードの値が親ノードの値よりも大きくなるようにツリーを構築するために使用されます。場合によっては、キーとデータムがまったく同じです。

一般的なキー値には単純な整数または文字列が含まれます。キーの実際のデータはアプリケーションによって異なります。string/double ペアを格納する二分探索木を考えてみましょう。つまり、キーは文字列値であり、キーに関連付けられたデータは double 値です。開発者は、文字列値を使用してツリーを検索できます。

この場合、基本的な再帰的検索アルゴリズムは次のようになります。

 node search (node, key) {
   if node is null then return null;

   if node.key = key then
      return node

   if key < node then
      return search (node.left, key);
   else
      return search (node.right, key);
  }

ここで、パラメーターはnode : ツリーのルート & key : 検索する値です。

したがって、通常、必要なキーに基づいて検索できますが、キーに関連付けられた値に基づいて検索することはできません。

于 2013-03-16T20:39:57.313 に答える