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); } |
