//Binary Tree Search 삽입, 삭제, 균형잡기
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
typedef struct _node
{
char data;
struct _node* left;
struct _node* right;
}node;
int index;
char array[MAX];
void print(node*);
void print2(node*);
node* insert(node**, char);
node* del(node**, char);
void bti_balance(node**);
node* balance(int);
void bti_deleteall(node**);
void bti_sort(node**);
void main()
{
node* root = NULL;
insert(&root, 'F');
insert(&root, 'B');
insert(&root, 'O');
insert(&root, 'L');
insert(&root, 'A');
insert(&root, 'D');
insert(&root, 'C');
insert(&root, 'M');
insert(&root, 'G');
insert(&root, 'H');
insert(&root, 'N');
insert(&root, 'K');
print2(root); printf("\n"); print(root); printf("\n\n");
del(&root, 'F'); print2(root); printf("\n"); print(root); printf("\n\n");
bti_balance(&root);
print2(root); printf("\n"); print(root); printf("\n");
}
void bti_balance(node** base)
{
int i;
index = 0;
bti_sort(&(*base));
i = index;
bti_deleteall(&(*base));
index = 0;
*base = balance(i);
}
// 이진 트리 균형잡는 함수
node* balance(int n)
{
int n_left, n_right;
node* temp;
if(n > 0)
{
n_left = (n-1)/2;
n_right = n - n_left - 1;
temp = (node*)malloc(sizeof(node));
temp->left = balance(n_left);
temp->data = array[index++];
temp->right = balance(n_right);
return temp;
}
else
return NULL;
}
// 이진 트리 모든 노드 삭제 함수
void bti_deleteall(node** p)
{
if(*p != NULL)
{
bti_deleteall(&(*p)->left);
bti_deleteall(&(*p)->right);
free(*p);
}
}
// 이진 트리를 순회 하면서 값을 배열에 저장하는 함수
void bti_sort(node** p)
{
if(*p != NULL)
{
bti_sort(&(*p)->left);
array[index++] = (*p)->data;
bti_sort(&(*p)->right);
}
}
node* del(node** base, char key)
{
node *temp, *son, *nexth, *parent;
int flag = 0;
temp = *base;
while(temp->data != key && temp != NULL)
{
flag = 1;
parent = temp;
if(temp->data > key)
temp = temp->left;
else
temp = temp->right;
}
if(temp == NULL)
return NULL;
if(temp->left == NULL && temp->right == NULL) // 노드의 자식이 없는 경우
son = NULL;
else if(temp->left != NULL && temp->right != NULL) // 노드의 자식이 둘인 경우
{
nexth = temp->right;
if(nexth->left != NULL) // 노드의 오른쪽 자식의 왼쪽 자식이 있는 경우
{
while(nexth->left->left != NULL)
nexth = nexth->left;
son = nexth->left;
nexth->left = son->right;
son->left = temp->left;
son->right = temp->right;
}
else // 노드의 오른쪽 자식의 왼쪽 자식이 없는 경우
{
son = nexth;
son->left = temp->left;
}
}
else // 노드의 자식이 하나인 경우
{
if(temp->left != NULL)
son = temp->left;
else
son = temp->right;
}
if(flag)
{
if(parent->data > key)
parent->left = son;
else
parent->right = son;
}
else
*base = son;
free(temp);
return son;
}
void print(node* base)
{
node* temp = base;
if(temp != NULL)
{
print(temp->left);
printf("%3c",temp->data);
print(temp->right);
}
}
void print2(node* base)
{
node* temp = base;
if(temp != NULL)
{
printf("%3c",temp->data);
print2(temp->left);
print2(temp->right);
}
}
node* insert(node** base, char key)
{
if((*base) == NULL)
{
(*base) = (node*)malloc(sizeof(node));
(*base)->data = key;
(*base)->left = NULL;
(*base)->right = NULL;
}
else if((*base)->data > key)
(*base)->left = insert(&(*base)->left, key);
else
(*base)->right = insert(&(*base)->right, key);
return *base;
}
