[C]이분탐색리스트(BinarySearchTree)_구현

주요 내용 요약

0. 이분탐색 리스트의 특징

  - 두개이하의 자식노드를 갖는 트리이며, 루트보다 작으면 왼쪽, 크면 오른쪽으로 자식을 갖는다. 

  - 따라서 inorder로 순회 하면 오름차순의 데이터를 갖게 된다. 

1. 삽입

  - 루트부터 key값의 대/소를 배교해 작은면 왼쪽, 크면 오른쪽으로 내려가면서 자리를 찾아 삽입

2. 삭제 

  - 가장 끝(nil)에 있는 노드를 삭제하면 NULL만 자식으로 붙히면 됨

  - 중간에 값을 삭제 한다면 두가지 케이스로 나눠진다. 

    1) 자식 노드가 모두 있을때.

      - 오른쪽 자식을 루트로 하여 그 자식들 중 최솟값을 갖는 루트의 데이터를 갖져온 후 삭제.

    2) 자식 노드가 하나 이하로 있을때.

      - 둘중에 있는 놈을 자식으로 할당

3. 입력 값 별 순회 데이터(7, 3, 9, 1, 2, 5, 8)

<preorder>
값: 8, 노드주소:  0x1226067d0
--------
값: 3, 노드주소:  0x1226067f0
--------
값: 1, 노드주소:  0x122606830
--------
값: 2, 노드주소:  0x122606850
--------
값: 5, 노드주소:  0x122606870
--------
값: 9, 노드주소:  0x122606810 

--------

<inorder>
값: 1, 노드주소:  0x122606830
--------
값: 2, 노드주소:  0x122606850
--------
값: 3, 노드주소:  0x1226067f0
--------
값: 5, 노드주소:  0x122606870
--------
값: 8, 노드주소:  0x1226067d0
--------
값: 9, 노드주소:  0x122606810
--------

<postorder>
값: 2, 노드주소:  0x122606850
--------
값: 1, 노드주소:  0x122606830
--------
값: 5, 노드주소:  0x122606870
--------
값: 3, 노드주소:  0x1226067f0
--------
값: 9, 노드주소:  0x122606810
--------
값: 8, 노드주소:  0x1226067d0

---

코드(c)

#include <stdio.h>
#include <stdlib.h>

typedef struct NodeStruct {             // 노드 스트럭트 생성
    struct NodeStruct *leftChild;
    struct NodeStruct *rightChild;
    int data;
}NODE;

NODE *root;

NODE *insert(NODE *root, int data){   
    if (root == NULL){                      // 노드가 하나도 없다면 바로 생성
        root = malloc(sizeof(NODE));
        root -> leftChild = root -> rightChild = NULL;
        root -> data = data;
        return root;
    }else{
        if (data < root -> data){           // 데이터의 대/소비교를 통해 재귀적으로 내려감
            root -> leftChild = insert(root->leftChild, data);
        }else{
            root -> rightChild = insert(root->rightChild, data);
        }
    }
    return root;
}

NODE *findMin(NODE *root){
    NODE *tmp = root;               // 최솟값은 기준 노드 좌측의 가장 끝 값
    while(tmp->leftChild != NULL){
        tmp = tmp -> leftChild;
    }
    return tmp;
}

NODE *delete(NODE *root, int data){
    NODE *tempNode = NULL;              // 임시 노드
    if (root == NULL){                  // 하나도 없을 경우
        return NULL;
    }

    if (root->data > data){                                  // 같은 값이 있는 노드가 있을때까지 찾음
        root->leftChild = delete(root->leftChild, data);
    }else if (root->data < data){                               
        root->rightChild = delete(root->rightChild, data);
    }else{                                                          // 같다면
        if (root->leftChild != NULL && root->rightChild != NULL){   // 양쪽의 노드가 모두 있을때
            tempNode = findMin(root->rightChild);                   // 최소값을 찾아 임시노드로 할당
            root->data = tempNode->data;                            // 최소값 노드의 값을 삭제하려는 노드에 할당
            root->rightChild = delete(root->rightChild, tempNode->data); // 오른쪽 자식의 최솟값을 찾으러 내려가서 삭제!
        }else{                                                           // 자식 노드가 하나라도 없을때
            tempNode = (root->leftChild == NULL) ? root->rightChild : root-> leftChild; // 왼쪽 자식이 없으면 오른쪽 자식, 있으면 왼쪽 자식 할당
            free(root);                                             // 삭제하려는 값은 삭제
        }
    }
    return root;

}

void preorder(NODE *root){
    if (root == NULL){
        return;
    }
    printf("값: %d, 노드주소:  %p\n", root->data, root);
    printf("--------\n");
    preorder(root->leftChild);
    preorder(root->rightChild);
}

void inorder(NODE *root){
    if (root == NULL){
        return;
    }
    inorder(root->leftChild);
    printf("값: %d, 노드주소:  %p\n", root->data, root);
    printf("--------\n");
    inorder(root->rightChild);
}

void postorder(NODE *root){
    if (root == NULL){
        return;
    }
    postorder(root->leftChild);
    postorder(root->rightChild);
    printf("값: %d, 노드주소:  %p\n", root->data, root);
    printf("--------\n");
}

int main(){
    root = insert(root, 7);
    root = insert(root, 3);
    root = insert(root, 9);
    root = insert(root, 1);
    root = insert(root, 2);
    root = insert(root, 5);
    root = insert(root, 8);

    root = delete(root, 7);
 
    printf("<preorder>\n");
    preorder(root);

    printf("<inorder>\n");
    inorder(root);

    printf("<postorder>\n");
    postorder(root);

}

 

---

배운 점, 배울 점

포인터에 대한 이해가 아직 부족하다. 좀더 큰 그림을 그려서 이해해야 겠다.