/*=======================================================================*
 * 2分木を扱う再帰関数の例                            2023.8.10 山田俊行 *
 *=======================================================================*/

/*
 * このファイルは，tree.h や (実装済みの) tree.c のあるディレクトリに保存し，
 * 次のコマンドでコンパイル・実行する．
 *
 *      gcc tree.c recursion.c -o recursion
 *      ./recursion
 */

#include <stdio.h>
#include "tree.h"

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

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

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

int compute_size(const Tree *t, int depth) {
  int i, size;

  /* 関数の開始直後，節情報を表示 */
  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 = compute_size(t->left,  depth + 1)
		      + compute_size(t->right, depth + 1)
		      + 1;

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

  return size;
}

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

int main(void) {
  Tree *t = branch('+',   /*  a*b + c/d を表す木  */
                   branch('*',leaf('a'),leaf('b')),
                   branch('/',leaf('c'),leaf('d'))
                   );

  printf("t = "); show_tree(t);
  printf("size(t) = %d\n", size(t));
  printf("computation of size(t) :\n"); compute_size(t, 0);

  free_tree(t); t = NULL;
  return 0;
}