2008. 12. 15. 11:46
#include <stdio.h>
#include <malloc.h>

typedef struct { int key; } element;
typedef struct tree_node* tree_pointer;
enum {FALSE, TRUE};
struct tree_node {
        tree_pointer left_child;
        element data;
        short int bf;
        tree_pointer right_child;
};

struct stack {
        tree_pointer data;
        struct stack* node;
};

struct stack* top =NULL;
int unbalanced = FALSE;
tree_pointer root = NULL;

int x = 40 , y = 1;                          // X , Y 좌표

void avl_insert(tree_pointer* , element, int*);
void left_rotation(tree_pointer* ,int* );
void right_rotation(tree_pointer* ,int* );
void push(tree_pointer );
tree_pointer pop();
bool isempty();
void avl_tree_print();

void main()
{
        element data;
        for(int i = 0 ; i< 12; i++)
        {
                scanf("%d",&data.key);
                avl_insert(&root,data,&unbalanced);
        }
        avl_tree_print();
        

}

void avl_insert(tree_pointer* parent, element x, int* unbalanced)
{
        if(!*parent)
        {
                *unbalanced = TRUE;
                *parent = (tree_pointer)malloc(sizeof(tree_node));
                
                (*parent)->left_child = (*parent)->right_child = NULL;
                (*parent)->data = x;
                (*parent)->bf = 0;
        }
        else if(x.key < (*parent)->data.key)
        {
                avl_insert(&(*parent)->left_child,x,unbalanced);
                if(*unbalanced)
                {
                        switch((*parent)->bf)
                        {
                        case -1:
                                (*parent)->bf = 0;
                                break;
                        case 0:
                                (*parent)->bf = 1;
                                break;
                        case 1:
                                left_rotation(parent,unbalanced);
                                
                        }
                }
        }
        else if(x.key > (*parent)->data.key)
        {
                avl_insert(&(*parent)->right_child,x,unbalanced);
                if(*unbalanced)
                {
                        switch((*parent)->bf)
                        {
                        case 1:
                                (*parent)->bf = 0;
                                break;
                        case 0:
                                (*parent)->bf = -1;
                                break;
                        case -1:
                                right_rotation(parent,unbalanced);
                        }
                }
        }
        else
        {
                *unbalanced = FALSE;
                printf("The key is already in the tree");
        }
}

void left_rotation(tree_pointer* parent,int* unbalanced)
{
        tree_pointer grand_child, child;
        child = (*parent)->left_child;
        if(child->bf == 1)                  // LL 회전
        {
                (*parent)->right_child = child->right_child;
                child->right_child = *parent;
                (*parent)->bf = 0;
                *parent = child;                
        }
        else                               // LR 회전
        {
                grand_child = child->right_child;
                child->right_child = grand_child->left_child;
                grand_child->left_child = child;
                (*parent)->left_child = grand_child->right_child;
                grand_child->right_child = *parent;
                switch(grand_child->bf)
                {
                case 1:
                        (*parent)->bf = -1;
                        child->bf = 0;
                        break;
                case 0:
                        (*parent)->bf = child->bf = 0;
                        break;
                case -1:
                        (*parent)->bf = 0;
                        child->bf = 1;
                }
                *parent = grand_child;
        }
        (*parent)->bf = 0;
        *unbalanced = FALSE;
}




void right_rotation(tree_pointer* parent ,int* unbalanced)
{
        tree_pointer grand_child, child;
        child = (*parent)->right_child;
        if((*parent)->bf == -1 )             // RR 회전
        {
                (*parent)->right_child = child->left_child;
                child->left_child = *parent;
                (*parent)->bf = 0;
                (*parent) = child;
        }
        else                                 // RL회전
        {
                grand_child = child->left_child;
                child->left_child = grand_child->right_child;
                grand_child->right_child = child;
                (*parent)->right_child = grand_child->left_child;
                grand_child->left_child = (*parent);
                switch(grand_child->bf)
                {
                case -1:
                        (*parent)->bf = 1;
                        child->bf = 0;
                        break;
                case 0:
                        (*parent)->bf = child->bf = 0;
                        break;
                case 1:
                        (*parent)->bf = 0;
                        child->bf = -1;
                }
                (*parent) = grand_child;
        }
        (*parent)->bf = 0;
        *unbalanced = FALSE;
}

void push(tree_pointer data)
{
        if(top == NULL)
        {
                top = (struct stack*)malloc(sizeof(struct stack));
                top->data = data;
                top->node = NULL;
        }
        else
        {
                struct stack* new_node;
                new_node = (struct stack*)malloc(sizeof(struct stack));
                new_node->data = data;
                new_node->node = top;
                top = new_node;
        }
}

tree_pointer pop()
{
                tree_pointer data;
                struct stack* del_node;
                data = top->data;
                del_node = top;
                top = top->node;
                delete del_node;

                return data;
}
                
bool isempty()
{
        if(top == NULL)
                return TRUE;
        else
                return FALSE;
}

void avl_tree_print()
{
        tree_pointer current_node;
        current_node = root;
        bool done = TRUE;

        do
        {
                while(current_node != NULL)
                {
                        push(current_node);
                        current_node =current_node->left_child;
                        x-= 5;                // X 좌표 감소 좌측으로 이동
                        y+= 1;                // Y 좌표 증가 아래로 이동
                }

                if(top != NULL)
                {
                        current_node = pop();
                        y--;                  // Y 좌표 감소 위쪽으로 이동
                        
                        printf("%d",current_node->data.key);
                        current_node = current_node->right_child;

                        if(current_node != NULL)
                        {
                                x+=5;
                                y+=1;
                        }
                }
                else
                        done = FALSE;
        } while(done);

}
Posted by 두장