[File System] ::트리 구현만 해보자

트리구현.c

일단 트리 부터 구현해보자... (크기 상관 X)

출처 http://thrillfighter.tistory.com/225

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
}NODE;
 
NODE *root;
 
void initTree(int data) {
    NODE *New;
    New = (NODE*)(malloc(sizeof(NODE)));
    root = New;
    root->data = data;
    root->left = NULL;
    root->right = NULL;
}
 
void *AddChilde(NODE *parrent, int data) {
    if ((parrent->left != NULL) && (parrent->right != NULL)) {
        printf("It's already Full, can't add\n");
        return 0;
    }
 
    NODE *New;
    New = (NODE*)(malloc(sizeof(NODE)));
    New->left = NULL;
    New->right = NULL;
    New->data = data;
 
    if (parrent->left == NULL) {
        parrent->left = New;
    }
    else if (parrent->right == NULL) {
        parrent->right = New;
    }
 
    return New;
}
 
void PreOrder(NODE *r) {
    printf("Node Data : %d\n", r->data);
    if (r->left)PreOrder(r->left);
    if (r->right)PreOrder(r->right);
}
 
int main() {
    initTree(1);
    NODE *I = AddChilde(root, 2);
    NODE *r = AddChilde(root, 3);
    
 
    AddChilde(I, 4);
    AddChilde(I, 5);
    AddChilde(r, 6);
    AddChilde(r, 7);
 
    PreOrder(root);
 
    
}

1) 우선 노드의 모양을 구조체를 이용하여 선언한다.

     

2) root 노드를 설정하여 tree를 생성하고 초기화 시켜준다.

3) 부모노드를 확인하여

- 왼쪽 오른쪽이 모두 꽉 차있는 경우에는 꽉 찾다는 말을하고

- 그렇지 않은 경우에는 왼쪽 오른쪽중 비어있는 곳에 넣어준다. ( 왼쪽부터 넣어준다 )

4) 각 노드의 자식노드를 또 삽입한다.

5) 출력을 해본다 ( print문의 위치에 따라 변경 가능 )

1) 전위 순화

2) 중위 순회

3) 후위 순회

호오 잘된다.. 이진 트리로 변경해보자

2. 이진 트리

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
}NODE;
 
NODE *root;
 
void initTree(int data) {
    NODE *New;
    New = (NODE*)(malloc(sizeof(NODE)));
    root = New;
    root->data = data;
    root->left = NULL;
    root->right = NULL;
}
 
void *AddChilde(int data) {
    
    NODE *current = root;
    NODE *parrent = NULL;
 
    while (current != NULL) {
        if (data == current->data) {
            printf("존재하는 값입니다!!\n");
            return;
        }
        
        parrent = current;
 
        if (data < current->data) {
            current = current->left;
        }
        else if (data > current->data)
            current = current->right;
    }
 
    NODE *New;
    New = (NODE*)(malloc(sizeof(NODE)));
    New->left = New->right = NULL;
    New->data = data;
    
    if (parrent->data>data) {
        printf("%d를 %d 의 왼쪽 자식으로 삽입합니다.\n", New->data,parrent->data);
        parrent->left = New;
    }
    else {
        printf("%d를 %d 의 오른쪽 자식으로 삽입합니다.\n", New->data,parrent->data);
        parrent->right = New;
    }
 
    return New;
}
 
 
 
void PreOrder(NODE *r) {
    printf("Node Data : %d\n", r->data);
    if (r->left)PreOrder(r->left);
    if (r->right)PreOrder(r->right);
 
}
 
 
int main() {
    initTree(4);
    AddChilde(7);
    AddChilde(1);
    AddChilde(3);
    AddChilde(9);
    AddChilde(5);
    AddChilde(0);
 
    PreOrder(root);
 
    
}

우리가 얼마전에 알아본 이진트리를 구현해보자. 이때 규칙이 있었다.  2018/01/22 - [석사 1학기차 겨울방학/c언어,화일구조,자바] - B Tree

 - 또한 중복 값이 존재하지 않아야합니다.

위의 코드를 변경해보자.

1) 중복값이 존재하지 않아야하고 좌우 크기를 고려해야하므로 AddChilde라는 함수를 변경해보자

1-1) 중복 값을 검사하기 위해 root노드부터 차례대로 내려오면서 값을 비교한다.

중복 검사가 잘되는 확인해봅시다. 1을 넣고 1을 또 넣으려 해보자

아주 잘되네요

1-2) 부모모다 작은 친구들은 왼쪽에 부모보다 큰 친구들은 오른쪽에 넣어보자. 전체 코드는 아래와 같다.

- 부모를 가르키는 포인터를 생성한다.

- 위의 중복 검사에서 아무 이상 없는 경우, 새로운 노드를 생성한다.

- 새롭게 들어온 데이터와 부모의 데이터를 비교하여 삽입할 데이터의 위치를 선정한다.

그 결과 다음과 같습니다.

        

마지막에 확실하게 잘 되는지 0을 한번 입력해볼까요?

역시나 잘됩니다.

2) 삭제를 해보자

삭제에는 아래의 3가지 경우가 있다. 부모노드를 따로 가르키는 포인터를 지정하여 지우려는 값과 일치하는 자식의 값을 NULL로 표기한다.

1. 자식노드가 2개인 경우 : 왼쪽 서브트리의 가장 큰 값 , 오른쪽 서브트리의 가장 작은 값을 부모노드와 연결

2. 자식노드가 1개인 경우 : 1개의 자식노드와 부모노드를 연결

3. 리프노드인 경우  : 걍삭제

   

너무나 허접한 코드... 눈물이 핑 돌아..

void delNode(int data) {
 
    NODE *current = root;
    NODE *parent=NULL;
    NODE *child = NULL;
 
    while (current !=NULL && current->data !=data) {
        parent = current;
        if (data < current->data) 
            current = current->left;
        
        else if (data > current->data) 
            current = current->right;
    }
    if (current == NULL) {
        printf("\n ※ %d는 존재하지 않습니다. 삭제할 수 없습니다. \n",data);
        return;
    }
 
 
    if (current->left == NULL && current->right == NULL) {
        printf(" 삭제하려는 %d노드의 자식이 하나도 없습니다. \n..[삭제후]..\n",current->data);
        if (parent == NULL) {
            root = NULL;
            return;
        }
        if (parent->left != current) 
            parent->right = NULL; 
        else
            parent->left = NULL;
    }
    else if (current->right == NULL|| current->left == NULL) {
        printf(" 삭제하려는 %d노드의 자식이 한개 존재합니다. \n..[삭제후]..\n",current->data);
 
        (current->left == NULL) ? ( child = current->right) : (child = current->left);
        
        if (parent == NULL) {
            root = child;
            return;
        }
 
        if (parent->left == current) 
            parent->left = child;
        else
            parent->right = child;
 
        current->data = NULL;
    }
    else if(current->right !=NULL && current->left !=NULL) {
        printf(" 삭제하려는 %d노드의 자식이 모두 존재합니다. \n..[삭제후]..\n",current->data);
        
        if (parent == NULL) {
            parent = current;
        }
 
        child = current->right;
 
        while (child->left != NULL) {
            child = child->left;
        }
            
        current->data = child->data;
 
        child->data = NULL;
        free(child);
    }
}

1. 삭제하려는 노드의 자식이 하나도 없는 경우에는 바로 아래의 값을 null로 해줍니다.

+ 83번째 줄은 부모가 없는경우=root이기때문에..

if문을 이용해서 삭제하려는 current 포인터가 가르키는 노드가 왼쪽에 있는지 오른쪽에 있는지 확인한 뒤 해당 노드를 NULL로 만들어줍니다

2.삭제하려는 노드의 자식이 한개만 있는 경우

포인터를 하나더 사용해서 삭제할노드의 자식노드와 삭제할 노드의 부모노드를 연결해준다.

3.삭제하려는 노드의 자식이 모두(2개) 있는 경우

이상황에서 이제 child의 value를 current value로 지정합니다.

실행 결과

노드를 rand함수로 무작위로 생성하고 삭제하는 값 또한 rand로 무작위로 삭제하게 하였다.

아래와 같은 트리가 생겼다.

그 후 삭제 결과는 아래와 같다. 2가 사라졌고 13이 사라지자 13의 자리에는 오른쪽 서브트리의 최소 값인 14가 와있다.

근데 null로 해버리기로 해서 그런지 0으로 표시되어있다...free하면 에러가나고 아직 이유를 모르겠다 ㅠ_ㅠ.. 하읍 c어렵다.

일단 요까지만 해놓고 요부분은 다시 수정해봐야겠다.