이진 검색 트리 (binary search tree)

1. data가 char형인 binary search tree의 자료구조를 작성하라.

typedef struct BTREE {
     char data;
     struct BTREE *left, *right;
} BTREE;

2. 위 binary search tree의 preorder, inorder, postorder traverse를 프로그램하라.

int preorder(BTREE *t)
{
     if ( t != NULL) {
         printf("%c", t->data);
         preorder(t->left);
         preorder(t->right);
     }
}

int inorder(BTREE *t)
{
     if ( t != NULL) {
         inorder(t->left);
         printf("%c", t->data);
         inorder(t->right);
     }
}

int postorder(BTREE *t)
{
     if ( t != NULL) {
         postorder(t->left);
         postorder(t->right);
         printf("%c", t->data);
     }
}

3. swap_tree를 하나의 binary search tree에 대해 대칭이 되는 tree라고 정의할 때, 위 자료구조를 이용해서
   swap_tree를 프로그램하라.

int swap_tree(BTREE *t)
{
    BTREE *p;

    if( t == NULL)
        return NULL;
    else {
        p = (BTREE *) malloc(sizeof(BTREE));
        p->left = swap_tree(t->right);
        p->right = swap_tree(t->left);
        p->data = t->data;
        return p;
    }
}

4. 위 자료구조를 이용해서 tree를 복사하는 프로그램

int tree_copy(BTREE *t)
{
    BTREE *p;

    if( t == NULL)
        return NULL;
    else {
        p = (BTREE *) malloc(sizeof(BTREE));
        p->left = tree_copy(t->left);
        p->right = tree_copy(t->right);
        p->data = t->data;
        return p;
    }
}

5. 위 자료구조를 이용하여 tree의 max depth를 구하는 프로그램을 작성하라.

int max_depth(BTREE *t)
{
    int max = 0, depth;

    if( t == NULL)
        return 0;
    else {
         depth = max_depth(t->left) + 1;
         if( depth > max)
              max = depth;
         depth = max_depth(t->right) + 1;
         if( depth > max)
              max = depth;
         return max;
    }


}