// recursion.c -- 2分木を扱う再帰関数の例

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// 2分木のデータ構造

typedef struct _tree {
  char           node;     // 節のデータ (1文字)
  struct _tree  *left;     // 左の子へのポインタ
  struct _tree  *right;    // 右の子へのポインタ
} Tree;

// 2分木の節の生成

Tree *node(char c, Tree *l, Tree *r) {
  Tree *t = (Tree *) malloc(sizeof(Tree));
  if (t == NULL) {
    perror("malloc() failed in node()");
    exit(EXIT_FAILURE);
  }
  t->node  = c;
  t->left  = l;
  t->right = r;
  return t;
}

// 2分木の葉の生成

Tree *leaf(char c) {
  return node(c, NULL, NULL);
}

// 木を再帰的に表示

void show(const Tree *t) {
  if (t == NULL) {
    putchar('#');
  } else {
    putchar(t->node);
    putchar('(');
    show(t->left);
    putchar(',');
    show(t->right);
    putchar(')');
  }
}

// 木の大きさ(節の総数)を再帰的に計算

int size(const Tree *t) {
  if (t == NULL) return 0;
  else           return (size(t->left) + size(t->right) + 1);
}

// 木の大きさの再帰計算の様子を表示

int display(const Tree *t) {
  static int depth = -1;
  int i, size;
  depth++;

  // 関数の開始直後，節情報を表示
  for (i = 1; i <= depth; i++) printf(">       ");
  if (t == NULL) printf("#\n");
  else           printf("'%c'\n", t->node);

  // 節数の計算本体
  if (t == NULL) size = 0;
  else           size = display(t->left) + display(t->right) + 1;

  // 関数の終了直前，部分木の大きさを表示
  for (i = 1; i <= depth; i++) printf(">       ");
  printf("size = %d\n", size);

  depth--;
  return size;
}

// 木を表す文字列，木の節数，節数の再帰計算の過程 を順に表示

int main(void) {

  Tree *t = node('+',   // 算術式 a*b + c/d を表す木
                 node('*', leaf('a'), leaf('b')),
                 node('/', leaf('c'), leaf('d'))
                 );

  printf("t = "); show(t); putchar('\n');
  printf("size(t) = %d\n", size(t));
  printf("computation of size(t) :\n"); display(t);
  // 処理を続けるなら t が指す木の記憶域を開放する

  return EXIT_SUCCESS;
}