C言語で2分木構造の実装

![]ttps://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.momoyama-usagi.com%2Fentry%2Finfo-algo-tree-traverse&psig=AOvVaw3AGtH1evbZaou6u2ksi6St&ust=1636866178615000&source=images&cd=vfe&ved=0CAsQjRxqFwoTCLDrpvjHlPQCFQAAAAAdAAAAABAI

例えばこのような2分木であるとしたら,

15(10(4(NULL,NULL),14(12(NULL,NULL),NULL)),19(17(NULL,NULL),NULL))

と出力するプログラムを実装しようとしています.

引数はNode型のnです.

Node型は

c
1typedef struct node {
2  char *label;
3  struct node *left;
4  struct node *right;
5} Node;

と定義してあります。

再帰関数で実装できそうだなというところまでしか思いつかず,うまくいきません。

実装の考え方を教えて頂きたいです。よろしくお願いします。

yu-ima

2021/11/13 05:43

4を4(NULL,NULL)と表現するのであれば、12,17でも12(NULL,NILL), 17(NULL,NULL)ではないですか？

jimbe

2021/11/13 05:50 編集

リンク先に考え方やコードが載っていますが、それを実装・実行してみたりはしていないのでしょうか。

Mellonn

2021/11/13 06:07

yu-imaさん,修正しました jimbeさん,別のところでリンク先のコードを参考にしました。今回の質問内容である2分木の構造の実装に関しては記載がないです。

jimbe

2021/11/13 07:24

> 今回の質問内容である2分木の構造の実装に関しては記載がない。つまり問題は、2分木による "表示" では無く、2分木の生成自体ということでしょうか。

Mellonn

2021/11/13 07:28

2分木の生成自体はできています。(私の1つ前の質問を見ていただければわかります) 生成したNode型で構成されている2分木を本質問に記載しているような出力のように表示させたいのが現状です。

jimbe

2021/11/13 07:33

であれば、リンク先の情報・コードで十分対応できると思うのですが、どこが分からないのでしょうか。

Mellonn

2021/11/13 07:50

https://www.momoyama-usagi.com/entry/info-algo-tree-traverse 私はこのリンクの内容を本質問内容へと昇華できませんでした。単純にノードのlabelを出力するだけであればよいのですが,ノードとその子のノードも合わせてとなると,リンク先の実装に比べると複雑になると自分は感じました。

Mellonn

2021/11/13 07:51

もう少しリンクの内容を落とし込んで考えてみます。

jimbe

2021/11/13 08:51 編集

>単純にノードのlabelを出力するだけであればよいのですが,ノードとその子のノードも合わせてとなると～難しく考えすぎのように思います。ツリーが再帰関数で処理できるのは、ツリーを構成する各部分がツリーだからです。まずはツリーにデータが1つもない場合(=ルートが null の場合)にどう表示されるべきかを考え、それを実装してそのように表示されることを確認してください。次にデータが1つ(例でいえば "15" )を入れ、どう表示されるべきかを考え、それを実装してそのように表示されることを確認してください。そして同時に、先の「データが1つもない場合」のツリー構造に戻してもコードを直さずに先の結果と同じく表示されることを確認してください。これだけでもほぼ形は出来ていることと思います。

行動規範の内容に同意します

回答2件

ベストアンサー

まずは再帰を考えず、データが無いツリーを表示すると考えてみます。

ご提示されている例にはありませんが、恐らく "NULL" とだけ表示されることでしょう。
つまり(関数名はテキトウです)

c
1  void printTree(Node *n) {
2    printf("NULL");
3  }

これだけです。

次に "15" だけが入ったツリーとしましょう。
先の root=NULL を壊さずに実装するとして、

c
1  void printTree(Node *n) {
2    if(n == NULL) {
3      printf("NULL");
4    } else {
5      printf("15(NULL,NULL)");
6    }
7  }

が一番簡単でしょうか。ズルイ？　でも、結果は想定通りです。
このコードから始めます。

もちろんこのままでは実際のデータに関係無く "15" や "NULL" になってしまいますので、表示の各部分を置き換えていきます。

まず、 else の表示部分を固定部分と可変部分に分けます。
(以降、else の中だけ表記します。)

c
1      printf("15"); //可変
2      printf("("); //固定
3      printf("NULL"); //可変
4      printf(","); //固定
5      printf("NULL"); //可変
6      printf(")"); //固定

"15" は引数 n からの label に入っていますので置き換えます。

c
1      printf(n->label);
2      printf("(");
3      printf("NULL");
4      printf(",");
5      printf("NULL");
6      printf(")");

最初の "NULL" は同じく n からの left の値で、その次は right です。

c
1      printf(n->label);
2      printf("(");
3      if(n->left == NULL) {
4        printf("NULL");
5      }
6      printf(",");
7      if(n->right == NULL) {
8        printf("NULL");
9      }
10      printf(")");

・・・これでは left も right もそれぞれ NULL じゃない場合に何も出力されません。
では、例えば left が NULL では無い場合、何を表示するのでしょうか。

"left をルートとしたツリー" を表示すれば良いはずです。
恐らくはココが一番のキモと思います。

ここで、「ツリーの一部はまたツリー」を処理する為に再帰を使うことになります。

c
1      printf(n->label);
2      printf("(");
3      if(n->left == NULL) {
4        printf("NULL");
5      } else {
6        printTree(n->left);
7      }
8      printf(",");
9      if(n->right == NULL) {
10        printf("NULL");
11      } else {
12        printTree(n->right);
13      }
14      printf(")");

これで完成・・・ではあるのですが、コードを注意してみると、left や right が NULL の場合の処理は printTree に既に「if(n == NULL) {}」としてあります。
ですのでそれぞれの if 文は省くことが出来ます。(関数全体を表記します。)

c
1  void printTree(Node *n) {
2    if(n == NULL) {
3      printf("NULL");
4    } else {
5      printf(n->label);
6      printf("(");
7      printTree(n->left);
8      printf(",");
9      printTree(n->right);
10      printf(")");
11    }
12  }