1

キュー（配列）を使用してツリーをレベル順に印刷するコードを書いています。

    void printLevelOrder(node *root) {
         node* queue[10];
         node*t=root;
         int y=0;
         queue[y]=t;
         for(int i=0;i<10;i++)
         {
                 printf("%d,",queue[i]->val); 

                 t=queue[i];
                 if((t->left)!=NULL){
                 queue[++y]=t->left;
                 }
                 if((t->right)!=NULL){
                 queue[++y]=t->right;
                 }
         } 
}

メソッドを再帰メソッドに変換したい。試しましたが、正しい解決策が得られません。この種の問題を再帰呼び出しの使用に変換することは可能ですか?

4

4 に答える 4

0

これがあなたが探していたものかどうかはわかりませんが、部分再帰です。

void print_level_part(node* p, level) {
    if(p) {
        if(level==1) {
            printf("%d", p->val);
        } else {
            print_level_part(p->left, level-1);
            print_level_part(p->right, level-1);
        }
    }
}

//the loop in main which does the main printing.
for(int i=0; i<n; ++i) {
    print_level_part(root, i);
}

完全に再帰的なソリューションが必要な場合は、再帰関数のforループを変更することをお勧めします。main

于 2012-10-09T13:37:22.137 に答える
0

これは、Qnan が話していたことの例です。

void printNext(node **queue,int i,int y)
{
  if (i==y) return;

  node *t = queue[i++];
  printf("%d,",t->val);

  if (t->left)  queue[y++] = t->left;
  if (t->right) queue[y++] = t->right;

  printNext(queue,i,y);
}

void printLevelOrder(node *root)
{
  node *queue[10]; /* be careful with hard-coded queue size! */
  int y=0, i=0;

  queue[y++]=root;
  printNext(queue,i,y);
  printf("\n");
}
于 2012-10-09T14:25:38.237 に答える
0

私が理解している限り、ツリーを「レベル順」で出力することは、実際には特定のツリーのBFSトラバーサルであり、再帰は適していません。再帰はDFSに適したアプローチです。

再帰は内部的にスタック(LIFO 構造) で動作しますが、BFS はキュー(FIFO 構造) を使用します。ルートの解がサブツリーの解 (結果または走査順序のみ) に依存する場合、ツリー アルゴリズムは再帰に適しています。再帰はツリーの「下」に行き、下から上に向かって問題を解決します。これから、事前順序、順序内、および順序後のトラバーサルを再帰として実行できます。

  • pre-order : ルートを出力し、左のサブツリーを出力し、右のサブツリーを出力します
  • in-order : 左のサブツリーを出力し、ルートを出力し、右のサブツリーを出力します
  • post-order : 左のサブツリーを出力し、右のサブツリーを出力し、ルートを出力します

ただし、レベルオーダーは「ルートを何とかし、部分木ごとに何とか」というように分解することはできません。唯一可能な「再帰的」実装は @Qnan の提案に従うものであり、彼が言ったようにあまり意味がありません。

ただし、可能なことは、再帰アルゴリズムをかなり洗練された反復アルゴリズムに変換することです。内部再帰は実際にはスタックで機能するため、この状況での唯一のトリックは、システム スタックの代わりに独自のスタックを使用することです。この種の再帰的実装と反復的実装のわずかな違いは次のとおりです。

  • iterativeを使用すると、関数呼び出しの時間を節約できます
  • recursiveを使用すると、通常、より直感的なコードが得られます
  • recursiveを使用すると、関数呼び出しごとに戻りアドレスに余分なメモリが割り当てられます
  • iterativeでは、メモリを割り当て、メモリが割り当てられる場所を決定します
于 2012-10-09T14:53:07.463 に答える