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

Question

![![イメージ説明](63174e70e9d23796c134424b9fc54277.gif)]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
typedef struct node {
  char *label;
  struct node *left;
  struct node *right;
} Node;
```
と定義してあります。

再帰関数で実装できそうだなというところまでしか思いつかず,うまくいきません。

実装の考え方を教えて頂きたいです。よろしくお願いします。

Accepted Answer

まずは再帰を考えず、データが無いツリーを表示すると考えてみます。

ご提示されている例にはありませんが、恐らく "NULL" とだけ表示されることでしょう。
つまり(関数名はテキトウです)
```c
  void printTree(Node *n) {
    printf("NULL");
  }
```
これだけです。

次に "15" だけが入ったツリーとしましょう。
先の root=NULL を壊さずに実装するとして、
```c
  void printTree(Node *n) {
    if(n == NULL) {
      printf("NULL");
    } else {
      printf("15(NULL,NULL)");
    }
  }
```
が一番簡単でしょうか。ズルイ？　でも、結果は想定通りです。
このコードから始めます。

もちろんこのままでは実際のデータに関係無く "15" や "NULL" になってしまいますので、表示の各部分を置き換えていきます。

まず、 else の表示部分を固定部分と可変部分に分けます。
(以降、else の中だけ表記します。)
```c
      printf("15"); //可変
      printf("("); //固定
      printf("NULL"); //可変
      printf(","); //固定
      printf("NULL"); //可変
      printf(")"); //固定
```
"15" は引数 n からの label に入っていますので置き換えます。
```c
      printf(n->label);
      printf("(");
      printf("NULL");
      printf(",");
      printf("NULL");
      printf(")");
```
最初の "NULL" は同じく n からの left の値で、その次は right です。
```c
      printf(n->label);
      printf("(");
      if(n->left == NULL) {
        printf("NULL");
      }
      printf(",");
      if(n->right == NULL) {
        printf("NULL");
      }
      printf(")");
```
・・・これでは left も right もそれぞれ NULL じゃない場合に何も出力されません。
では、例えば left が NULL では無い場合、何を表示するのでしょうか。

"left をルートとしたツリー" を表示すれば良いはずです。
恐らくはココが一番のキモと思います。

ここで、「ツリーの一部はまたツリー」を処理する為に再帰を使うことになります。
```c
      printf(n->label);
      printf("(");
      if(n->left == NULL) {
        printf("NULL");
      } else {
        printTree(n->left);
      }
      printf(",");
      if(n->right == NULL) {
        printf("NULL");
      } else {
        printTree(n->right);
      }
      printf(")");
```
これで完成・・・ではあるのですが、コードを注意してみると、left や right が NULL の場合の処理は printTree に既に「if(n == NULL) {}」としてあります。
ですのでそれぞれの if 文は省くことが出来ます。(関数全体を表記します。)
```c
  void printTree(Node *n) {
    if(n == NULL) {
      printf("NULL");
    } else {
      printf(n->label);
      printf("(");
      printTree(n->left);
      printf(",");
      printTree(n->right);
      printf(")");
    }
  }
```
もし left が NULL だったら、一番上の "n == NULL" に引っかかって "NULL" が表示されるはずで、 NULL で無かったら else に入って label 等が表示されるはずです。

時には全体(構造)を見("ツリー")、時には目の前のコードだけに集中("printf の分解")してみたりという臨機応変(?)な視点から考えるのも、必要になるかと思います。

Answer

自分自身を再起関数として機能させます。

1.　 ノードがnullであれば、"NULL"を出力し復帰する。
2.　nullでなければ、labelと、"("を出力する。
3.　左ノードを持って自分自身を呼び出す。
4.　"," を出力
5.　右ノードを持って自分自身を呼び出す。
6.　")"
7.　復帰

以上でどうでしょう。

関連した質問