[C/C++]C를 이용한 이진탐색트리 라이브러리
BSTError.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
이진탐색트리에 관한 소스이다. 이진탐색트리의 노드와 삽입, 삭제, 순회에 관한 코드들이 구현되어 있다.
//트리 노드
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);
}
}