3

StackOverflowコミュニティの皆さん、こんにちは。

ツリーを構築せずに、プレオーダーまたはポストオーダートラバーサル（大きな違いはないはずです）のみを指定して、BSTの内部パス長を計算する方法を理解しようとしています。つまり、上記のトラバーサルの1つだけを使用したいと思います。これはほとんどの人にとって簡単な答えかもしれませんが、あなたはすでに私が木にかなり慣れていないと思っていたかもしれません。

よく考えていただければ幸いです。

4

3 に答える 3

0

http://geeksforgeeks.org/?p=6633に、事前順序および順序内トラバーサルからツリーを構築する方法について説明しているページがあります。ここでは、ツリーが検索ツリーであるため、(キーの並べ替え順序を使用して) 暗黙的に順序どおりに走査します。そのサイトにあるような再帰アルゴリズムを使用して、各ツリー ノードのレベルを計算し (ツリーを構築する必要はありません)、レベルを合計して内部パスの長さを取得できます。このアルゴリズムは、トラバーサルを検索して各ノードの正しい子を見つけるため、最も効率的ではないかもしれませんが、機能するはずです。これは、シングルパス アルゴリズムを実行する方法に関する私の最善の推測です (すべてのキーが異なると仮定します)。

int internal_path_length(key_iter& cur_node, key_iter end, int level, key max_key) {
  if (cur_node == end) return 0;
  key cur_key = *cur_node;
  if (cur_key > max_key) return 0;
  ++cur_node;
  int len1 = internal_path_length(cur_node, end, level + 1, cur_key);
  int len2 = internal_path_length(cur_node, end, level + 1, max_key);
  return len1 + len2 + level;
}

皮切りに：

key_iter i = preorder.begin();
internal_path_length(i, preorder.end(), 0, mk);

mkツリー内で可能な最大のキーよりも大きい場所。

于 2011-02-23T05:48:28.093 に答える
0

これは BST であるため、暗黙的にツリー (要素のソートされたリスト) を順番にトラバーサルします。

preorder または postorder トラバーサルから一意のツリーを作成できます。 Pre は [R、R 未満の要素のリスト、R より大きい要素のリスト] Post は [R 未満の要素のリスト、R より大きい要素のリスト、 R]

擬似コードは次のようになります。

findIPLPreOrder(poArray,startIndex,endIndex, height) {
     if(startIndex==endIndex){
          retrn height;
     }
     m=findIndexOfEndofLeftSubTree(poArray,start,end);
     return findIPLPreOrder(poArray,start+1,m,height + 1) + findIPLPreOrder(poArray,m+1,end,height + 1);     
}

findIndexOfEndofLeftSubTree(poArray,start,end){
  R=poArray[start]
  for(i=start+1;i<=end;i++){
     if(R < poArray[i]){
         return i-1;
       }
  }
}
于 2011-02-23T05:52:16.413 に答える
-1

あなたの問題を理解していれば、それは不可能かもしれません。2 本の木を考える

   A         A
  / \        |
 B   C       B
             |
             C

これらのプリオーダー トラバーサル (ABC) は同じですが、内部パスの長さが異なります (2 と 3)。

于 2011-02-23T05:44:02.670 に答える