1

次のようなバイナリ ツリーを出力する必要があります。

--------x-------
----x-------x---
--x---x---x---x-
-x-x-x-x-x-x-x-x 
xxxxxxxxxxxxxxxx

再帰を使用して、最初の行を除いて、行の左側と行の右側を印刷します。したがって、この関数は、左側の開始点と右側の終了点のパラメーターを使用して表示関数を呼び出します。次に、左側と右側の 2 回、自分自身を呼び出します。

    #include <stdio.h>

#define LENGTH 16

void makeBranches(int, int);
void display(int, int);

int main(){

  makeBranches(0, LENGTH-1);
}

void makeBranches(int left, int right){

  if(left >= right){
    return;
  } else{
    display(left, right);
      makeBranches(left, (right+left)/2);
      makeBranches((right+left)/2+1, right);  
  }
}

void display(int left, int right){
  int mid = (left+right)/2;
  int i;

  for(i = left; i <= right; i++){
    if(i == mid)
      printf("X");
    else
      printf("-");
  }

  if(right == LENGTH-1)
    printf("\n");

}

何度も変更されていますが、これが現在のコードの外観です。

makeBranches execute の最初の呼び出しを取得してから 2 番目の呼び出しを取得する方法がわかりません。現在、左側の呼び出しのみを行い、次のようになっています。

-------X--------
---X-----X--X-
4

2 に答える 2

0

幅優先のトラバーサルを行う必要があります。

于 2012-11-08T20:03:11.407 に答える
0

すでにおわかりのように、問題は再帰関数を呼び出す構造ツリーにあります。この種の動作を防ぐには、何かを出力する前にツリー全体をスキャンする設計を実装する必要があります。

現在の呼び出し構造は次のように機能します。

makeBranches(left,right) -> 
  makeBranches(left, (right+left)/2) ->
    makeBranches(left, ((right+left)/2+left)/2) ->
      makeBranches(left, (((right+left)/2+left)/2+left)/2) -> etc.
  makeBranches((right+left)/2+1,right) ->
    makeBranches((right+(right+left)/2+1)/2+1,right) ->
      makeBranches((right+(right+(right+(right+left)/2+1)/2+1)/2+1)/2+1,right) -> etc.

これを平らにするために、印刷する前に各レベルをキャプチャすることを目指す必要があります。これを行うには、各側に追加するリンク リストなどの何らかの形式のコレクションが必要です。その後、ツリー全体がスキャンされたら、図面を再構築できます。

関数内で、displayこれが行の左側か右側かを知るためのチェックを既に作成しています。

if(right == LENGTH-1)
    printf("\n");

それでは、表示呼び出しを変更しましょう。

void display(int left, int right){
  int mid = (left+right)/2;
  int i;
  string thisLine = "";

  for(i = left; i <= right; i++){
    if(i == mid)
      thisLine += "X";
    else
      thisLine += "-";
  }

  if(right == LENGTH-1) {
    rightList.add(thisLine);
  } else {
    leftList.add(thisLine);
  }
}

ここで、main()ツリー全体が構築された後、各リストのすべてのノードを出力しますleft->right->"\n"(空になるまで繰り返します)。

注意できるいくつかの警告がありますが、設計できるのは、最初の呼び出しでdisplay行全体が作成されるという事実です。私のコードを使用すると、rightリストにドロップされ、次のように描画する必要があります。right->(left->right->"\n")repeat

これは理にかなっていますか？私はこれをすべて概念的に行ったので、何もスキップしなかったことを願っています:\

于 2012-11-08T19:19:33.190 に答える