0

BSTの場合、[a、b]のノードの値を最大値から最小値の形式で見つけたいと思います。私が考えることができる最も簡単な方法は次のとおりです。

void printRange(BSTNode<Key,E>* root,int lowValue,int highValue) const
{
    if(root==NULL) return;

    printRange(root->right(),lowValue,highValue);
    if(root->key()>=lowValue&&root->key()<=highValue)
        cout<<root->key()<<" ";

    printRange(root->left(),lowValue,highValue);
}

しかし、訪問するノードを減らしてこれらの値を出力する方法があるかどうか知りたいですか？

4

2 に答える 2

1

範囲内にあるかどうかに関係なく、BSTのすべてのノードにアクセスしています。そして、必要な値だけを印刷します。より洗練されたアルゴリズムは次のようになります。

  1. BSTを順番にトラバースします。

  2. ルートから開始します。

  3. 左側のサブツリーのルートが「lowValue」よりも小さい場合にのみ、左側のサブツリーを順序どおりに処理します。

  4. 右側のサブツリーのルートが「highValue」より大きい場合にのみ、右側のサブツリーを処理します

  5. それ以外の場合は、関数から戻るだけです。

    このようにして、BSTの必要な部分のみを訪問して、フィルター処理された順序トラバーサルを実行します。

于 2012-12-03T08:31:44.227 に答える
1

この質問に対する答えは疑似コードで、次のようにする必要があります。

void printRange(int lower, int upper, BSTNode * node){
  if (node == NULL) return
  if (node->key <= upper) printRange(lower, upper, node->right);
  if (node->key >= lower && node->key <= upper) printf("%d",node->value);
  if (node->key >= lower) printRange(lower, upper, node->left);
}
于 2016-11-01T05:03:26.490 に答える