본문 바로가기
삽질/Com

트리

by 푸딩s 2009. 12. 6.

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

 

typedef struct _tree
{
    int key;
    struct _tree *left;
    struct _tree *right;
}TREE;

 

void insert(int, TREE**);
TREE* call_malloc(int);
void print(TREE*);
void preorder(TREE*);
void inorder(TREE*);
void postorder(TREE*);
void search(int, TREE*);
void tree_copy(TREE*, TREE**);
void mirror_copy(TREE*, TREE**);

 

void main()
{
    TREE *root = NULL;
    TREE *copy_root = NULL;
    TREE *mirror_root = NULL;
    int no;
   
    while(1)
    {
        system("cls");
        puts("*** MENU ***");
        puts("1. INSERT");
        puts("2. PRINT");
        puts("3. SEARCH");
        puts("4. TREE COPY");
        puts("5. MIRROR COPY");
        puts("6. END");
        printf("choice : ");
        scanf("%d", &no);
        fflush(stdin);
       
        switch(no)
        {
        case 1 : printf("\n\t삽입할 정수를 입력 : ");
            scanf("%d", &no); fflush(stdin);
            insert(no, &root);
            break;
        case 2 : print(root);
            print(copy_root);
            print(mirror_root);
            break;
        case 3 : printf("\n\t검색할 정수를 입력 : ");
            scanf("%d", &no); fflush(stdin);
            search(no, root);
            break;
        case 4 : tree_copy(root, &copy_root); break;
        case 5 : mirror_copy(root, &mirror_root); break;
        case 6 : exit(1);
        }
        getch();
    }
}

TREE* call_malloc(int k)
{
    TREE *newnode;
   
    newnode = (TREE*)malloc(sizeof(TREE));
    newnode->key = k;
    newnode->left = newnode->right = NULL;
   
    return newnode;
}

void insert(int k, TREE **r)
{
    if(*r == NULL)
        *r = call_malloc(k);
    else if((*r)->key > k)
        insert(k, &(*r)->left);
    else
        insert(k, &(*r)->right);
}

void print(TREE *root)
{
    printf("\n\t<< PREORDER >>\n");
    preorder(root);
   
    printf("\n\t<< INORDER >>\n");
    inorder(root);
   
    printf("\n\t<< POSTORDER >>\n");
    postorder(root);
    printf("\n");
}

void preorder(TREE *r)
{
    if(r != NULL)
    {
        printf("%5d", r->key);
        preorder(r->left);
        preorder(r->right);
    }
}

void inorder(TREE* r)
{
    if(r != NULL)
    {
        inorder(r->left);
        printf("%5d", r->key);
        inorder(r->right);
    }
}

void postorder(TREE* r)
{
    if(r != NULL)
    {
        postorder(r->left);
        postorder(r->right);
        printf("%5d", r->key);
    }
}

void search(int k, TREE *r)
{
    if(r == NULL)
        printf("\n\t입력하신 정수 [%d]는 존재하지 않습니다...\n", k);
    else if(r->key == k)
        printf("\n\t입력하신 정수 [%d]는 존재합니다...\n", k);
    else
        search(k, r->key > k ? r->left : r->right);
}

void tree_copy(TREE *r, TREE **cr)
{
    if(r != NULL)
    {
        *cr = call_malloc(r->key);
        tree_copy(r->left, &(*cr)->left);
        tree_copy(r->right, &(*cr)->right);
    }
}

void mirror_copy(TREE* r, TREE **mr)
{
    if(r != NULL)
    {
        *mr = call_malloc(r->key);
        mirror_copy(r->left, &(*mr)->right);
        mirror_copy(r->right, &(*mr)->left);
    }
}


 

'삽질 > Com' 카테고리의 다른 글

junk : 임시휴지통 만들기  (0) 2009.12.06
하위디렉토리의 종류 및 기능  (0) 2009.12.06
이중연결리스트  (0) 2009.12.06
빙고게임  (1) 2009.12.06
주석 삭제 프로그램  (0) 2009.12.06

댓글