1. data가 char형인 binary search tree의 자료구조를 작성하라.
2. 위 binary search tree의 preorder, inorder, postorder traverse를 프로그램하라.
3. swap_tree를 하나의 binary search tree에 대해 대칭이 되는 tree라고 정의할 때, 위 자료구조를 이용해서
swap_tree를 프로그램하라.
4. 위 자료구조를 이용해서 tree를 복사하는 프로그램
5. 위 자료구조를 이용하여 tree의 max depth를 구하는 프로그램을 작성하라.
typedef struct BTREE {
char data;
struct BTREE *left, *right;
} 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);
}
}
{
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;
}
}
{
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;
}
}
{
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;
}
}
{
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;
}
}
'IT > 알고리즘' 카테고리의 다른 글
| 힙 (heap) (0) | 2008.07.18 |
|---|---|
| 타 변수 없이 서로의 값을 치환하는 방법 (0) | 2008.07.16 |
| + integer 값을 - integer 값으로 바꾸는 가장 간단한 방법 (0) | 2008.07.16 |
| 하나의 소수(솟수)가 주어졌을때, 다음 소수(솟수)를 찾는 알고리즘 (0) | 2008.07.15 |
| qsort (퀵 정렬) - 재귀, 비재귀, 삽입정렬, 난수발생 (1) | 2008.07.15 |
쩐의시대
나답게 살아가고 나답게 살아가자