Master Tree

/***************************************************************************
*
*        Date        : 2005-05-25
*        Copyright    : aucd29
*        E-mail        : aucd29@daum.net
*
*        Tree를 이용한 프로그램 작성
*
***************************************************************************/

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

#define MAXWORD 100
typedef enum {ADD=1, DEL, SWAP, PRINT, EXIT} MENU;

//
// tree node
//
typedef struct tnode
{
    int word;            // pointers to the text
    tnode *left;        // left child
    tnode *right;        // right child
} tnode;

//
// Prototype
//
void treeprint(tnode *);
void pre_treeprint(tnode *);
tnode* talloc(void);
tnode* treeswap(tnode *);
tnode* Del(tnode *);
tnode* AddTree(tnode *, int);
void PrintTree(tnode *);
void ProgramExit(void);

tnode* Find(tnode* root, int v)
{
    int x;

    while(1)
    {
        printf("Find node this->%d \n", root->word);
        if(root->word == v)
        {
            if(root->left)
                printf("Left : %d\n", root->left->word);
            if(root->right)
                printf("Right : %d\n", root->right->word);            
        }
        else
        {
            scanf("%d",&x);
            if(x == 0)
            {
                if(root->left)
                    root = root->left;
                else
                    puts("null node");
            }
            else
            {
                if(root->right)
                    root = root->right;
                else
                    puts("null node");
            }
        }
    }
}

void main(int argc, char *argv[])
{
    tnode *root;
    int iInput;
    short imnu=0;

    //
    // Initialize
    //
    root = NULL;
    root = AddTree(root, 70);
    root = AddTree(root, 30);
    root = AddTree(root, 90);
    root = AddTree(root, 80);

    //
    // Selected menu
    //
    while(1)
    {
        puts("Select Menu : 1.add 2.del 3.swap 4.print 5.exit");
        scanf("%d", &imnu);

        switch(imnu)
        {
        case ADD:
            while(1)
            {
                scanf("%d",&iInput);
                if(!iInput) break;
                root = AddTree(root, iInput);
            }
            break;
        case DEL:
            root = Del(root);
            break;
        case SWAP:
            root = treeswap(root);
            break;
        case PRINT:
            PrintTree(root);
            break;
        case EXIT:
            ProgramExit();            
            break;
        case 6:
            scanf("%d",&iInput);
            if(!iInput) break;
            Find(root, iInput);
            break;
        default:
            puts("Error : ");
            exit(1);
            break;
        }
    }
}

//
// 윈쪽 트리와 오른쪽 트리를 교환 한다.
//
tnode* treeswap(tnode *root)
{
    tnode *rtn;

    if(root)
    {
        rtn = (tnode*)malloc(sizeof(tnode));
        if(rtn == NULL)
        {
            printf("error:");
            exit(1);
        }
        rtn->right = treeswap(root->left);
        rtn->left = treeswap(root->right);        
        rtn->word = root->word;
        root = rtn;
    }

    return root;
}

//
// 중위 순위로 트리 출력
//
void treeprint(tnode* p)
{
    if(p != NULL)
    {
        treeprint(p->left);
        printf("%d ", p->word);
        treeprint(p->right);
    }
}

//
// 전위 순위로 트리 출력
//
void pre_treeprint(tnode* p)
{
    if(p != NULL)
    {
        printf("%d ", p->word);
        pre_treeprint(p->left);        
        pre_treeprint(p->right);
    }
}

//
// 메모리 할당
//
tnode *talloc(void)
{
    tnode *p;

    if(p = (tnode *)malloc(sizeof(tnode)))
        return p;
    else
    {
        printf("Error : 메모리 할당 불가");
        exit(1);
    }
}

//
// 트리 추가
//
tnode* AddTree(tnode *p, int d)
{
    if(p == NULL)
    {
        p = talloc();
        p->word = d;
        p->left = p->right = NULL;
    }
    else if(d == p->word)
        printf("Impossible is insert data");
    else if(d < p->word)
        p->left = AddTree(p->left, d);
    else
        p->right = AddTree(p->right, d);

    return p;
}

//
// 트리 삭제
//
tnode* Del(tnode *root)
{
    int del;
    tnode *p, *pRightLast;
    tnode *pPrev = (tnode*)malloc(sizeof(tnode));    // Dumy node

    //
    // init
    //
    p = pPrev->left = pPrev->right = root;

    puts("del number : ");
    scanf("%d", &del);
    
    while(p)
    {
        if(p->word < del)
        {
            //puts("right");
            pPrev = p;
            p = p->right;
        }
        else if(p->word > del)
        {
            //puts("left");
            pPrev = p;
            p = p->left;
        }
        else
        {    
        //    puts("Find");
            if(p->left)
            {
                if(pPrev->left == p)
                    pPrev->left = p->left;
                else
                    pPrev->right = p->left;

                pRightLast = p->left;

                while(pRightLast->right)
                    pRightLast = pRightLast->right;
                pRightLast->right = p->right;
            }
            else
                if(pPrev->left == p)
                    pPrev->left = p->right;
                else
                    pPrev->right = p->right;

            // root remove
            if(p == root)
                if(p->left)
                    root = p->left;
                else
                    root = p->right;
            
            free(p);
            return root;
        }
    }

    puts("not find of same word");
    return root;
}

//
// 트리 출력
//
void PrintTree(tnode *root)
{
    // Inorder
    system("cls");
    puts("========================================");
    puts("Inorder");
    treeprint(root);
    
    puts(" ");
    // preorder
    puts("Preorder");
    pre_treeprint(root);
    puts(" ");
    puts("========================================");
}

//
// 프로그램 종료
//
void ProgramExit(void)
{
    system("cls");
    puts("Good bye~~!");
    exit(1);
}