/*=======================================================================*
 * ２分木の基本関数                                                      *
 *=======================================================================*/

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

/*----- 枝と葉の生成 -----*/

/* この行と次の行は課題 1a が完成したら消す */
#define NOT_IMPLEMENTED  NULL

Tree *branch(char x, Tree *l, Tree *r) {
  /* 課題 1a */
  return NOT_IMPLEMENTED;   /* 適切に変える */
}

Tree *leaf(char x) {
  /* 課題 1a */
  return NOT_IMPLEMENTED;   /* 適切に変える */
}

/*----- ２分木の表示 -----*/

static void show_tree_sub(const Tree *t) {
  if (t == NULL) {
    putchar('#');
  } else {
    putchar(isprint(t->node) ? t->node : '?');
    putchar('(');
    show_tree_sub(t->left);
    putchar(',');
    show_tree_sub(t->right);
    putchar(')');
  }
}

void show_tree(const Tree *t) {
  show_tree_sub(t);
  putchar('\n');
}

/*----- 節の詳細表示 -----*/

void show_node(const Tree *t) {
  if (t != NULL) {
    /* 値の表示 */
    printf("  t        = %-10p\n", (void*)t);
    printf(" (t->node) = %-10c  (t->left) = %-10p  (t->right) = %-10p\n",
              t->node,   (void*)(t->left),  (void*)(t->right));
    /* 番地の表示 */
    printf("&(t->node) = %-10p &(t->left) = %-10p &(t->right) = %-10p\n",
    (void*)&(t->node),  (void*)&(t->left), (void*)&(t->right));
  }
}

/*----- ２分木の等しさの判定 -----*/

int equal_tree(const Tree *t1, const Tree *t2) {
  if (t1 == NULL) {
    return (t2 == NULL);
  } else {
    return (t2 != NULL  &&
            t1->node == t2->node  &&
            equal_tree(t1->left,  t2->left)  &&
            equal_tree(t1->right, t2->right));
  }
}

/*----- ２分木の複製と消去 -----*/

Tree *copy_tree(const Tree *t) {
  if (t == NULL) {
    return NULL;
  } else {
    return branch(t->node, copy_tree(t->left), copy_tree(t->right));
  }
}

void free_tree(Tree *t) {
  if (t != NULL) {
    free_tree(t->left);
    free_tree(t->right);
    t->left = t->right = NULL;
    free(t);
  }
}