C Data Structure - 이진 탐색 트리 4 (마지막)

C Data Structure - 이진 탐색 트리 1

C Data Structure - 이진 탐색 트리 2

C Data Structure - 이진 탐색 트리 3

자 드디어 마지막이다. 지긋지긋하다 정말 ㅋ

코드와 실행결과이다.

 

#include <stdio.h>
#include <stdlib.h>
 
 
#define TRUE 1
#define FALSE 0
#define STACK_LEN 20
#define QUEUE_LEN 20
 
struct binary_tree_node
{
    int data;
    struct binary_tree_node* left;
    struct binary_tree_node* right;
};
typedef struct binary_tree_node tree;
 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 스택으로 메모리 관리.
struct array_stack
{
    struct binary_tree_node* stack_array[STACK_LEN];
    int top_index;
};
typedef array_stack stack;
 
// 배열 기반 원형 큐 -> 레벨 순회를 위해서;
struct array_queue
{
    int front;
    int rear;
    struct binary_tree_node* queue_array[QUEUE_LEN];
    int count;
};
typedef struct array_queue queue;
 
/* 스택 함수 모음 */
void StackInit(stack* s);
int SIsEmpty(stack* s);
int SIsFull(stack* s); // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
void SPush(stack* s, struct node* data); // 증가시키고 대입.
struct binary_tree_node* SPop(stack* s);
struct binary_tree_node* SPeek(stack* s);
void ShowStack(stack* s);
 
struct binary_tree_node* CreateNodeAuto(stack* s);
void RemoveAllNodeAuto(stack* s);
 
/* 큐 함수 모음 */
void QueueInit(queue* q);
int QIsEmpty(queue* s);
tree* Dequeue(queue* q);
tree* Enqueue(queue* q, tree* data);
void ShowQueue(queue* q);
 
 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
// 트리 관련 함수
// 생성 및 삽입
tree* AutoCreateBinaryTreeNode(tree* r, stack* s, int data)
{
    // 조회를 위한 포인터 생성
    tree* index = r;
    // 새로운 노드 생성
    tree* newnode = CreateNodeAuto(s);
    // 새로운 노드 초기화
    newnode->data = data;
    newnode->left = NULL;
    newnode->right = NULL;
 
    // 순회 index가 NULL이 될 때까지 계속 돌린다.
    if (index == NULL)
        return newnode;
    else
    {
        while (index != NULL) // TRUE
        {
            if (data < index->data)
            {
                if (index->left == NULL)
                {
                    index->left = newnode; // 니가 있어야 할 곳은 여기야.
                    break;
                }
                // 현재 노드의 자식 중 left node로 간다.
                else
                {
                    index = index->left;
                }
            }
            else if (data > index->data)
            {
                if (index->right == NULL)
                {
                    index->right = newnode; // 니가 있어야 할 곳은 여기야.
                    break;
                }
                else
                {
                    index = index->right;
                }
            }
        }
        return r;
    }
}
// 전체 순회(전위, 중위, 후위)
void ShowPreOrderPath(tree* sub_root)
{
    if (sub_root != NULL)
    {
        printf("[%d] - ", sub_root->data);
        ShowPreOrderPath(sub_root->left);
        ShowPreOrderPath(sub_root->right);
    }
    return;
}
void ShowInOrderPath(tree* sub_root)
{
    if (sub_root != NULL)
    {
        ShowInOrderPath(sub_root->left);
        printf("[%d] - ", sub_root->data);
        ShowInOrderPath(sub_root->right);
    }
    return;
}
void ShowPostOrderPath(tree* sub_root)
{
    if (sub_root != NULL)
    {
        ShowPostOrderPath(sub_root->left);
        ShowPostOrderPath(sub_root->right);
        printf("[%d] - ", sub_root->data);
    }
    return;
}
void ShowLevelOrderPath(tree* sub_root, queue* q)
{
    tree* node = NULL;
    Enqueue(q, sub_root);
    while (!QIsEmpty(q))
    {
        node = Dequeue(q);
        printf("[%d] - ", node->data);
 
        if (node->left != NULL)
            Enqueue(q, node->left);
        if (node->right != NULL)
            Enqueue(q, node->right);
    }
    printf("QIsEmpty(q) : %d\n", QIsEmpty(q));
    return;
}
// 탐색
tree* SearchNode(tree* sub_root, int search_data)
{
    if (sub_root == NULL)
        return NULL;
    else if (search_data == sub_root->data)
        return sub_root;
    else if (search_data < sub_root->data)
        return SearchNode(sub_root->left, search_data);
    else if (search_data >= sub_root->data)
        return SearchNode(sub_root->right, search_data);
}
 
// 삭제
void RemoveNode(tree** root, int search_data)
{
    tree* target = NULL, * target_parent = NULL;
    tree* succ = NULL, * succ_parent = NULL;
 
    // 타겟 탐색
    target = *root;
    while (target != NULL)
    {
        if (target->data == search_data)
        {
            break;
        }
        else if (search_data < target->data)
        {
            target_parent = target;
            target = target->left;
        }
        else if (search_data > target->data)
        {
            target_parent = target;
            target = target->right;
        }
    }
 
    // 타겟의 유형 파악
    if (target->left == NULL && target->right == NULL) // 타겟이 leaf node인 경우
    {
        if (target_parent == NULL && target == *root) // 노드가 루트 하나만 달랑 있는 경우
            *root = NULL;
        else if (target == target_parent->left)
            target_parent->left = NULL;
        else if (target == target_parent->right)
            target_parent->right = NULL;
    }
    else if (target->left == NULL || target->right == NULL)
    {
        if (target_parent == NULL && target == *root)
            *root = (target->left != NULL) ? target->left : target->right;
        else if (target == target_parent->left)
            target_parent->left = (target->left != NULL) ? target->left : target->right;
        else if (target == target_parent->right)
            target_parent->right = (target->left != NULL) ? target->left : target->right;
 
    }
    else if (target->left != NULL && target->right != NULL)
    {
        succ = target->right, succ_parent = target;
        while (succ->left != NULL)
        {
            succ_parent = succ;
            succ = succ->left;
        }
        target->data = succ->data;
 
        if (succ_parent->left == succ)
            succ_parent->left = succ->right;
        else if (succ_parent->right == succ)
            succ_parent->right = succ->right;
    }
    return;
}
 
 
int main(void)
{
    tree* root = NULL;
    tree* target = NULL;
    stack s;
    queue q;
 
    StackInit(&s);
    QueueInit(&q);
 
    //삽입
    /*root = AutoCreateBinaryTreeNode(root, &s, 15);
    root = AutoCreateBinaryTreeNode(root, &s, 7);
    root = AutoCreateBinaryTreeNode(root, &s, 20);
    root = AutoCreateBinaryTreeNode(root, &s, 3);
    root = AutoCreateBinaryTreeNode(root, &s, 10);
    root = AutoCreateBinaryTreeNode(root, &s, 17);
    root = AutoCreateBinaryTreeNode(root, &s, 27);
    root = AutoCreateBinaryTreeNode(root, &s, 1);
    root = AutoCreateBinaryTreeNode(root, &s, 2);
    root = AutoCreateBinaryTreeNode(root, &s, 9);
    root = AutoCreateBinaryTreeNode(root, &s, 13);*/
 
    root = AutoCreateBinaryTreeNode(root, &s, 10);
    root = AutoCreateBinaryTreeNode(root, &s, 4);
    root = AutoCreateBinaryTreeNode(root, &s, 12);
    root = AutoCreateBinaryTreeNode(root, &s, 2);
    root = AutoCreateBinaryTreeNode(root, &s, 5);
    root = AutoCreateBinaryTreeNode(root, &s, 20);
 
 
    // 전위 순회
    ShowPreOrderPath(root);
    fputc('\n', stdout);
 
    // 중위 순회
    ShowInOrderPath(root);
    fputc('\n', stdout);
 
    // 후위 순회
    ShowPostOrderPath(root);
    fputc('\n', stdout);
 
    // 레벨 순회
    ShowLevelOrderPath(root, &q);
    fputc('\n', stdout);
 
    // 4와 12를 각각 탐색
    target = SearchNode(root, 4);
    if (target != NULL)
        printf("%p 주소에서 %d 값을 찾았습니다.\n", target, target->data);
    else
        printf("해당 값이 트리에 존재하지 않습니다\n");
 
    target = SearchNode(root, 12);
    if (target != NULL)
        printf("%p 주소에서 %d 값을 찾았습니다.\n", target, target->data);
    else
        printf("해당 값이 트리에 존재하지 않습니다\n");
 
    // 노드 삭제
    RemoveNode(&root, 10);
 
    // 레벨 순회
    ShowLevelOrderPath(root, &q);
    fputc('\n', stdout);
 
    // 메모리 관리
    RemoveAllNodeAuto(&s);
 
    return 0;
}
 
 
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 메모리 관리 스택 관련 함수 모음
 
void StackInit(stack* s)
{
    int i = 0;
    s->top_index = -1;
    for (i = 0; i < STACK_LEN; i++) // 순회를 위해서 모두 초기화
        s->stack_array[i] = NULL;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1)
        return TRUE;
    else
        return FALSE;
}
int SIsFull(stack* s) // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
{
    if ((s->top_index) + 1 < STACK_LEN)
        return FALSE;
    else
        return TRUE;
}
void SPush(stack* s, struct binary_tree_node* data) // 증가시키고 대입임 (top_index가 -1부터 시작하기 때문에)
{
    if (SIsFull(s))
    {
        printf("스택이 가득찼습니다\n");
        return;
    }
    s->stack_array[++(s->top_index)] = data;
    return;
}
struct binary_tree_node* SPop(stack* s)
{
    struct binary_tree_node* rtarget = NULL;
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    rtarget = s->stack_array[s->top_index];
    s->stack_array[s->top_index--] = NULL;
    return rtarget;
}
struct binary_tree_node* SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    return s->stack_array[s->top_index];
}
 
void ShowStack(stack* s)
{
    int i = 0;
    printf("{(top:%d)} : ", s->top_index);
    for (i = 0; i <= s->top_index; i++)
        printf("[%p](%d)", s->stack_array[i], s->stack_array[i]->data), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 
binary_tree_node* CreateNodeAuto(stack* s)
{
    struct binary_tree_node* tmp = (struct binary_tree_node*)malloc(sizeof(struct binary_tree_node));
    // 초기화
    tmp->data = 0;
    tmp->left = NULL;
    tmp->right = NULL;
    // 메모리 스택에 추가
    SPush(s, tmp);
 
    return tmp;
}
 
void RemoveAllNodeAuto(stack* s)
{
    binary_tree_node* rtarget = NULL;
    ShowStack(s);
    while (!SIsEmpty(s))
    {
        rtarget = SPop(s);
        free(rtarget);
        ShowStack(s);
    }
    return;
}
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 큐 함수 모음
void QueueInit(queue* q)
{
    int i = 0;
 
    q->front = q->rear = 0;
 
    for (i = 0; i < QUEUE_LEN; i++)
        q->queue_array[i] = NULL; // 큐 출력을 위한 초기화
 
    q->count = 0;
    return;
}
int QIsEmpty(queue* q)
{
    if (q->front == q->rear)
        return true;
    else
        return false;
}
tree* Dequeue(queue* q)
{
    tree* rval = NULL;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (q->front == q->rear)
    {
        printf("Queue가 이미 비었습니다.\n");
        return 0;
    }
    rval = q->queue_array[q->front];
 
    q->queue_array[q->front] = NULL;
    q->front = (q->front + 1) % QUEUE_LEN;
 
    q->count--;
 
    return rval;
}
tree* Enqueue(queue* q, tree* data)
{
    tree* rval = NULL;
    // 기본 동작 - 꽉 찼는가 확인 -> 삽입 -> 인덱스 변경
    // 2.
    if ((q->rear + 1) % QUEUE_LEN == q->front) // 가득 찬 경우,
    {
        printf("Queue가 가득 찼습니다.\n");
        return 0;
    }
    // 1.
    q->queue_array[q->rear] = data;
    rval = q->queue_array[q->rear];
    q->rear = (q->rear + 1) % QUEUE_LEN;
 
    q->count++;
 
    return rval;
}
 
void ShowQueue(queue* q)
{
    int i = 0;
    printf("{(r:%2d/f:%2d)} : ", q->rear, q->front);
    for (i = 0; i < q->count; i++)
        printf("[%p]", q->queue_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}