Binary Tree Search 삽입, 삭제, 균형잡기

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