3

整数配列に先行順トラバーサルとインオーダートラバーサルがある場合に、ツリーの後順トラバーサルを出力するコードが与えられます。inorder と postorder 配列を指定して同様に preorder を取得するにはどうすればよいですか?

void postorder( int preorder[], int prestart, int inorder[], int inostart, int length)
{ 
  if(length==0) return; //terminating condition
  int i;
  for(i=inostart; i<inostart+length; i++)
    if(preorder[prestart]==inorder[i])//break when found root in inorder array
      break;
  postorder(preorder, prestart+1, inorder, inostart, i-inostart);
  postorder(preorder, prestart+i-inostart+1, inorder, i+1, length-i+inostart-1);
  cout<<preorder[prestart]<<" ";
}

これが preorder() のプロトタイプです

void preorder( int inorderorder[], int inostart, int postorder[], int poststart, int length)

postorder() を使用するには、次のようになります

int preorder[6]={6,4,1,5,8,9};
int inorder[6]={1,4,5,6,8,9};
postorder( preorder,0,inorder,0,6);

出力は

1 5 4 9 8 6

以下は print_preorder() の間違ったコードで、まだ動作していません

void print_preorder( int inorder[], int inostart, int postorder[], int poststart, int length)
    {
      if(length==0) return; //terminating condition
      int i;
      for(i=inostart; i<inostart+length; i++)
        if(postorder[poststart+length-1]==inorder[i])
          break; 
      cout<<postorder[poststart+length-1]<<" ";
      print_preorder(inorder, inostart , postorder, poststart, i-inostart);
      print_preorder(inorder, inostart+i-poststart+1, postorder, i+1, length-i+inostart-1);
    }
4

2 に答える 2

9

ここにいくつかのヒントがあります：

  • サブ配列の最後の要素がpostorder新しいpreorderルートです。
  • アレイは、新しいルートのinorder両側で 2 つに分割できます。preorder
  • これらの 2 つのサブ配列でprint_preorder関数を再帰的に呼び出すことができます。inorder
  • print_preorder関数を呼び出すと、inorderとpostorder配列は同じサイズになります。
  • 範囲外の配列アクセスがあります: 配列postorder[poststart+length]の末尾を超えています。最後の要素を取得するには、postorder[poststart+length-1]
  • 最初の再帰print_preorder関数が間違った長さを選択しています。lengthこれは部分配列の長さですが、配列inostart内の絶対位置であることを忘れないでくださいinorder。関数はおそらく負の値で呼び出されlengthます。
  • 2 番目の再帰関数は、境界と長さを変換するにはかなり離れています。紙に描いてアルゴリズムをトレースすると、おそらく役立つでしょう。

ツリーを描画すると役立つ場合があります。

     6
   /   \
  4     8
 / \     \
1   5     9

次に、3 つのトラバーサルを書き出します。

// index:         0 1 2 3 4 5
int postorder[6]={1,5,4,9,8,6};
int inorder[6]=  {1,4,5,6,8,9};
int preorder[6]= {6,4,1,5,8,9};

さて、コンピュータを置いて、ペンと紙を取り出して、問題について考えてみてください:)

このコール スタックを想像してください (新しいルートは左側に表示されます)。

6 print_preorder(len=6, in=[1 4 5 6 8 9], post=[1 5 4 9 8 6])
4 |-> print_preorder(len=3, in=[1 4 5], post=[1 5 4])
1 |   |-> print_preorder(len=1, in=[1], post=[1])
  |   |   |-> print_preorder(len=0, in=[], post=[])
  |   |   |-> print_preorder(len=0, in=[], post=[])
5 |   |-> print_preorder(len=1, in=[5], post=[5])
  |       |-> print_preorder(len=0, in=[], post=[])
  |       |-> print_preorder(len=0, in=[], post=[])
8 |-> print_preorder(len=2, in=[8 9], post=[9 8])
      |-> print_preorder(len=0, in=[], post=[])
9     |-> print_preorder(len=1, in=[9], post=[9])
          |-> print_preorder(len=0, in=[], post=[])
          |-> print_preorder(len=0, in=[], post=[])

幸運を ：）

于 2010-06-09T01:54:09.013 に答える
4

  1. ポスト オーダーの最後の要素がツリーのルートになります。

  2. その後、ルートの位置を決定するために Inorder 配列を調べます。配列の左側が左サブツリーで、右側が右サブツリーです。

  3. そのインデックスを使用して、ルートである左の要素を決定します。

  4. 同様に、右のサブツリーについても行います。主なアイデアは、順序付けられた配列を調べて、左のサブツリーと右のサブツリーのインデックスを決定することです。私が明確だったことを願っています..

    public static void printpreorder(char []inorder,int i_start,int i_end,char[] postorder,int p_start,int p_end)
{
  if(i_start > i_end || p_start > p_end)
         return ; 
  char root = postorder[p_end];
  System.out.print(root);
  System.out.print("(");
    int k=0;
      for(int i=0; i< inorder.length; i++){
          if(inorder[i]==root){
            k = i;
            break;
          }
      }
  printpreorder(inorder, i_start, k-1, postorder, p_start, p_start+k-(i_start+1));
  System.out.print(")(");
  printpreorder(inorder, k+1, i_end, postorder, p_start+k-i_start, p_end-1);
  System.out.print(")");    
}

これは私にとって宿題でした。良い答えをくれた@Stephenに感謝

于 2014-05-24T07:20:06.350 に答える