[C언어 #70] 이진탐색트리 (Binary Search Tree) - 구현 (1) - 노드 생성, 노드 삽입

c언어 이진탐색트리 (Binary Search Tree) - 구현 (1) - 노드 생성 및 삽입

 

 

구현 함수 정리

#include <stdbool.h>
 
// 트리(Tree)를 구성하는 노드 구조체
struct node;
typedef struct node node;
 
// 숫자 k를 가지는 노드를 생성
node *newNode(int k);
 
// 트리의 데이터 제거 및 메모리 해제
void freenode(node *p);
 
// 숫자 k를 가지는 노드를 트리에 삽입
node *insert(node *p, int k);
 
// 트리에서 k를 탐색
node *search(node *p, int k);
 
// k값을 가진 노드 존재 여부 확인
bool find(node *p, int k);
 
// 트리에서 최소값을 가진 노드 반환 (노드 삭제시 활용)
node *minnode(node *p);
 
// k값을 가진 노드를 트리에서 제거
node *deletenode(node *p, int k);

 

 

트리(Tree)를 구성하는 노드 구조체

struct node {
    struct node *left;
    int value;
    struct node *right;
};
 
typedef struct node node;

 

 

숫자 k를 가지는 노드를 생성

node *newNode(int k) {
    node *p = malloc(sizeof(node));
    *p = (node) { NULL, k, NULL };
    return p;
}

 

 

트리의 데이터 제거 및 메모리 해제

void freenode(node *p) {
    if (p == NULL) return;
 
    freenode(p->left);
    freenode(p->right);
    free(p);
}

 

 

테스트 - 노드 구조체 생성 및 해제 테스트

void testNewNode() {
    node *p = newNode(7);
    assert(p->value == 7);
    freenode(p);
}

 

 

숫자 k를 가지는 노드를 트리에 삽입

node *insert(node *p, int k) {
    if (p == NULL) return newNode(k);
 
    if (k == p->value) {
        printf("p->value = %d    k = %d ---- Already exists.\n", p->value, k);
    } else if (k < p->value) {
        p->left = insert(p->left, k);
    } else if (k > p->value) {
        p->right = insert(p->right, k);
    }
    return p;
}

 

 

테스트 - 트리에 숫자 k를 가진 노드 삽입 테스트

void testInsert() {
    node *p = newNode(7);
    assert(p->value == 7);
    p = insert(p, 3);
    assert(p->left->value == 3);
    p = insert(p, 11);
    assert(p->right->value == 11);
    p = insert(p, 5);
    assert(p->left->right->value == 5);
    p = insert(p, 2);
    assert(p->left->left->value == 2);
    p = insert(p, 19);
    assert(p->right->right->value == 19);
    p = insert(p, 17);
    assert(p->right->right->left->value == 17);
    p = insert(p, 13);
    assert(p->right->right->left->left->value == 13);
    freenode(p);
}