Programming/C, C++

[C/C++]C를 이용한 이진탐색트리 라이브러리

MB Brad KWON 2012. 9. 26. 18:52



BSTError.h

BST.h



 과제로 이진탐색트리를 구현하였다. 이진탐색트리를 다음에 이용할 때는 이 라이브러리를 이용하여 구현한다면 다음부터 이진탐색트리의 구현이 매우 편리해질 것같다.


1. BSTError.h

 이진탐색트리에서 발생하는 에러 중에 필자가 직접 확인한 에러들에 관한 에러코드들을 규정했다.


//에러 코드

#define BST_OK                                          0x00000000

#define BST_MALLOC_FAIL                       0xff000001

#define BST_KEY_ALREADY_EXIST         0xff000002

#define BST_KEY_NOT_EXIST                  0xff000003

#define BST_NODE_IS_NULL                    0xff000004



2. BST.h

 이진탐색트리에 관한 소스이다. 이진탐색트리의 노드와 삽입, 삭제, 순회에 관한 코드들이 구현되어 있다.


//트리 노드

typedef struct TreeNode{

    int key;

    struct TreeNode *left, *right;

} TreeNode;



//노드 삽입

int insertNode(TreeNode **root, int key){

    TreeNode *p, *t;

    TreeNode *n;

    

    t = *root;

    p = NULL;

    

    while(t != NULL){

        if(key == t->key){

            return BST_KEY_ALREADY_EXIST;

        }

        

        p = t;

        

        if(key < t->key){

            t = t->left;

        }

        

        else {

            t = t->right;

        }

    }

    

    n = (TreeNode *)malloc(sizeof(TreeNode));

    

    if(n == NULL)

        return BST_MALLOC_FAIL;

    

    n->key = key;

    n->left = NULL;

    n->right = NULL;

    

    if(p != NULL){

        if(key < p->key)

            p->left = n;

        else

            p->right = n;

    }

    else

        *root = n;

    

    return BST_OK;

}



//노드 삭제

int deleteNode(TreeNode **root, int key){

    TreeNode *p, *child, *succ, *succ_p, *t;

    

    p = NULL;

    t = *root;

    

    while(t != NULL && t->key != key){

        p = t;

        t = (key < t->key) ? t->left : t->right;

    }

    

    if(t == NULL){

        return BST_KEY_NOT_EXIST;

    }

    

    if(t->left == NULL && t->right==NULL){

        if(p != NULL){

            if(p->left == t)

                p->left = NULL;

            else

                p->right = NULL;

        }

        

        else

            *root = NULL;

    }

    

    else if (t->left == NULL || t->right == NULL){

        child = (t->left == NULL) ? t->left:t->right;

        

        if(p != NULL){

            if(p->left == t)

                p->left = child;

            else

                p->right = child;

        }

        

        else

            *root = child;

    }

    

    else{

        succ_p = t;

        succ = t->right;

        

        while (succ->left != NULL) {

            succ_p = succ;

            succ = succ->left;

        }

        

        if(succ_p->left == succ)

            succ_p->left = succ_p->right;

        else

            succ_p->right = succ->right;

        

        t->key = succ->key;

        t=succ;

    }

    

    free(t);

    

    return BST_OK;

}



//전위 순회

void preOrder(TreeNode *root){

    if(root){

        printf("%d  ", root->key);

        preOrder(root->left);

        preOrder(root->right);

    }

}


//중위 순회

void inOrder(TreeNode *root){

    if(root){

        inOrder(root->left);

        printf("%d  ", root->key);

        inOrder(root->right);

    }


}


//후위 순회

void postOrder(TreeNode *root){

    if(root){

        postOrder(root->left);

        postOrder(root->right);

        printf("%d  ", root->key);

    }


}


//반복 탐색

int searchLoof(TreeNode * node, int *key){

    

    while (node != NULL) {

        if(*key == node->key){

            *key = node->key;

            printf("%d\n", node->key);

            return BST_OK;

        }

        else if(*key < node->key){

            printf("%d -> ", node->key);

            node = node->left;

        }

        else{

            printf("%d -> ", node->key);

            node = node->right;

        }

    }

    

    return BST_KEY_NOT_EXIST;

}



//순환 탐색

int searchRecurcive(TreeNode * node, int *key){

    

    if(node == NULL)

        return BST_NODE_IS_NULL;

    if(*key == node->key){

        *key = node->key;

        printf("%d\n", node->key);

        return BST_OK;

    }

    else if(*key < node->key){

        printf("%d -> ", node->key);

        return searchRecurcive(node->left, key);

    }

    else{

        printf("%d -> ", node->key);

        return searchRecurcive(node->right, key);

    }

}


'Programming > C, C++' 카테고리의 다른 글

[C/C++]함수 포인터  (0) 2013.04.18
[C/C++]전처리기 Pre-Processor  (0) 2013.04.18
[C/C++]연결 큐(Linked Queue)  (0) 2012.10.14
[C/C++]최대 히프, 최소 히프  (0) 2012.10.14
[C/C++]MySQL을 C로 연동하는 소스  (0) 2012.08.05