[C언어 #70] 이진탐색트리 (Binary Search Tree) - 구현

c언어 이진탐색트리 (Binary Search Tree) - 구현

 

[C언어 #69] 이진탐색트리 (Binary Search Tree)

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

[C언어 #70] 이진탐색트리 (Binary Search Tree) - 구현 (2) - 노드 탐색

[C언어 #70] 이진탐색트리 (Binary Search Tree) - 구현 (3) - 노드 삭제

 

 

이진탐색트리 (Binary Search Tree) - 구현

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
 
struct node {
    struct node *left;
    int value;
    struct node *right;
};
 
typedef struct node node;
 
// Create new node
node *newNode(int k) {
    node *p = malloc(sizeof(node));
    *p = (node){ NULL, k, NULL };
    return p;
}
 
// Free node
void freenode(node *p) {
    if (p == NULL) return;
 
    freenode(p->left);
    freenode(p->right);
    free(p);
}
 
// Insert node
node *insert(node *p, int k) {
    if (p == NULL) return newNode(k);
 
 
    if (p->value == k) {
        printf("p->value = %d \t 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;
}
 
// Search node
node *search(node *p, int k) {
    if (p == NULL)     return p;
    if (k == p->value) return p;
    if (k < p->value)  return search(p->left, k);
    if (k > p->value)  return search(p->right, k);
}
 
// Confirm search node
bool find(node *p, int k) {
    return search(p, k) != NULL;
}
 
// Get node with minimum node
node *minnode(node *p) {
    node *min = p;
    while (min->left != NULL) min = min->left;
    return min;
}
 
// Delete node with value k
node *deletenode(node *p, int k) {
    if (p == NULL) return p;
 
    if (k < p->value) {
        p->left = deletenode(p->left, k);
    } else if (k > p->value) {
        p->right = deletenode(p->right, k);
    } else {
        if (p->left == NULL) {
            node *tmp = p->right;
            free(p);
            return tmp;
        } else if (p->right == NULL) {
            node *tmp = p->left;
            free(p);
            return tmp;
        }
        node *tmp = minnode(p->right);
        p->value = tmp->value;
        p->right = deletenode(p->right, tmp->value);
    }
    return p;
}
 
// ----------------------------------------------------------------------------------------
// Testing
 
void testNewNode() {
    node *p = newNode(7);
    assert(p->value == 7);
    freenode(p);
}
 
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);
}
 
void testSearch() {
    node *p = newNode(7);
    assert(find(p, 7) == true);
    p = insert(p, 3);
    assert(find(p, 3) == true);
    assert(find(p, 11) == false);
    p = insert(p, 11);
    assert(find(p, 11) == true);
    assert(find(p, 3) == true);
    assert(find(p, 7) == true);
    p = insert(p, 5);
    assert(find(p, 11) == true);
    assert(find(p, 3) == true);
    assert(find(p, 7) == true);
    assert(find(p, 5) == true);
    freenode(p);
}
 
void testMinnode() {
    node *p = newNode(7);
    p = insert(p, 3);
    p = insert(p, 11);
    p = insert(p, 5);
    p = insert(p, 2);
    p = insert(p, 19);
    p = insert(p, 17);
    p = insert(p, 13);
    node *min = minnode(p);
    assert(min->value == 2);
    freenode(p);    
}
 
void testDelete() {
    node *n = newNode(7);
    n = insert(n, 3);
    n = insert(n, 13);
    n = insert(n, 2);
    n = insert(n, 11);
    n = insert(n, 17);
    n = deletenode(n, 7);
    assert(n->value == 11);
    assert(n->right->value == 13);
    freenode(n);    
}
 
void test() {
    testNewNode();
    printf("Test new node pass.\n");
    testInsert();
    printf("Test insert pass.\n");
    testSearch();
    printf("Test search pass.\n");
    testMinnode();
    printf("Test minnode pass.\n");
    testDelete();
    printf("Test delete pass.\n");
    printf("All tests pass.\n");
}
 
// ----------------------------------------------------------------------------------------
 
int main() {
    test();
    return 0;
}