21

二分探索木の前順トラバーサルが 6、2、1、4、3、7、10、9、11 の場合、後順トラバーサルを取得するにはどうすればよいですか?

4

11 に答える 11

28

出力、左へのトラバース、右へのトラバースを行うことによって構築される、ツリーの事前順序のトラバーサルが与えられます。

ポスト オーダー トラバーサルは BST に由来するため、数値をソートすることで、ポスト オーダー トラバーサルからインオーダー トラバーサル (左にトラバース、出力、右にトラバース) を推測できます。あなたの例では、順序通りのトラバーサルは 1、2、3、4、6、7、9、10、11 です。

2 つのトラバーサルから、元のツリーを構築できます。これには、より簡単な例を使用してみましょう。

  • 予約注文: 2、1、4、3
  • 順番：1、2、3、4

pre-order traversal により、ツリーのルートは 2 になります。in-order traversal は、1 が左側のサブツリーに分類され、3、4 が右側のサブツリーに分類されることを示します。左サブツリーの構造は、単一の要素を含むため自明です。右側のサブツリーの事前順序トラバーサルは、元の事前順序トラバーサルからこのサブツリー内の要素の順序を取得することによって推定されます: 4, 3. これから、右側のサブツリーのルートは 4 であり、順序通りの走査 (3, 4) から、3 が左側のサブツリーに分類されることがわかります。最終的なツリーは次のようになります。

  2
 / \
1   4
   /
  3

ツリー構造を使用すると、ツリーをたどることでポスト オーダー トラバーサルを取得できます: 左にトラバース、右にトラバース、出力。この例では、ポストオーダー トラバーサルは 1、3、4、2 です。

アルゴリズムを一般化するには:

  1. pre-order トラバーサルの最初の要素はツリーのルートです。ルートよりも小さい要素は、左側のサブツリーを形成します。ルートより大きい要素は、右側のサブツリーを形成します。
  2. ステップ 1 を使用して、左と右のサブツリーの構造を見つけます。これは、元の事前順序トラバーサルに現れる順序で配置されたそのサブツリーにあることがわかった要素で構成される事前順序トラバーサルです。
  3. 結果のツリーを事後順序でトラバースして、指定された事前順序トラバーサルに関連付けられた事後順序トラバーサルを取得します。

上記のアルゴリズムを使用すると、問題の事前順序トラバーサルに関連付けられた事後順序トラバーサルは、1、3、4、2、9、11、10、7、6 になります。そこに到達する方法は演習として残します。

于 2010-12-27T10:36:46.977 に答える
9

プレオーダー =現在のノード、左サブツリー、右サブツリーの順序でバイナリ ツリーの値を出力すること。

ポストオーダー= 二分木の値を、左のサブツリー、次に右のサブツリー、現在のノードの順序で出力すること。

二分探索ツリーでは、左側のサブツリーのすべてのノードの値が現在のノードの値よりも小さくなります。右側のサブツリーについても同様です。したがって、バイナリ サーチ ツリーのプレオーダー ダンプの開始 (つまり、そのルート ノードの値) がわかっている場合、ダンプ全体をルート ノードの値、左側のサブツリーのノードの値、および次の値に簡単に分解できます。右のサブツリーのノード。

ツリーをポストオーダーで出力するには、再帰と出力の並べ替えが適用されます。この作業は読者に任されています。

于 2010-12-27T10:28:49.740 に答える
4

Ondrej Tucny の回答に基づいています。BST のみに有効な
例: 

     20  
    /  \  
   10  30  
   /\    \  
  6  15   35

プレオーダー = 20 10 6 15 30 35
ポスト = 6 15 10 35 30 20

BST の場合、In Preorder トラバーサル。配列の最初の要素は 20 です。これがツリーのルートです。配列内の 20 未満のすべての数値は左側のサブツリーを形成し、それより大きい数値は右側のサブツリーを形成します。

//N = number of nodes in BST (size of traversal array)
int post[N] = {0}; 
int i =0;

void PretoPost(int pre[],int l,int r){
  if(l==r){post[i++] = pre[l]; return;}
  //pre[l] is root
  //Divide array in lesser numbers and greater numbers and then call this function on them recursively  
  for(int j=l+1;j<=r;j++) 
      if(pre[j]>pre[l])
          break;
  PretoPost(a,l+1,j-1); // add left node
  PretoPost(a,j,r); //add right node
  //root should go in the end
  post[i++] = pre[l]; 
  return;
 }

間違いがあれば訂正してください。

于 2011-04-04T23:28:24.663 に答える
3

事前注文のトラバーサル結果が表示されます。次に、値を適切なバイナリ検索ツリーに配置し、取得した BST のポストオーダー トラバーサル アルゴリズムに従います。

于 2011-10-18T05:28:26.650 に答える