/****************************
* file : bstree.c
****************************/
#include "search.h"
static int bst_total_cnt = 0; /* 총 데이터의 수 */
static int bst_dup_cnt = 0; /* 중복된 데이터를 제외한 데이터의 수 */
static LINT bst_cmp_cnt = 0; /* 알고리즘 효율을 알아보기 위해 비교횟수를 셈 */
LINT bst_cmp_count(){ /* 비교 횟수 */
return bst_cmp_cnt;
}
int bst_total_count(){
return bst_total_cnt;
}
int bst_dup_count(){
return bst_dup_cnt;
}
/*****************************
* 트리정보 초기화 및 생성
*****************************/
bst_t *newNode(char *data){
bst_t *tmp;
char *str_tmp;
bst_dup_cnt++;/* 노드는 중복되어 생성 안되기 때문에 */
if((tmp = (bst_t*)malloc(sizeof(bst_t))) == NULL){
fprintf(stderr, "Memory allocate fail\n");
return NULL;
}
str_tmp = (char *)malloc(strlen(data)+1); /* string len + NULL */
strcpy(str_tmp, data);
tmp->left = NULL;
tmp->right = NULL;
tmp->data.data = str_tmp;
tmp->data.cnt = 1;
bst_total_cnt++; /* 총 데이터 수 */
return tmp;
}
/*************************************************************************
* #include <string.h>
* int strcmp(const char *s1, const char *s2);
* s2 < s1 => -
* s2 > s1 => +
* s2 == s1 => 0
*************************************************************************/
void addBST(bst_t **root, char *data){
int datacmp;
if((*root) == NULL){
bst_cmp_cnt++;
(*root) = newNode(data);
}else {
datacmp = strcmp((*root)->data.data,data);
bst_cmp_cnt++; /* 데이터 총 비교 횟수 */
if(datacmp == 0) {
((*root)->data.cnt)++;
bst_total_cnt++; /* 총 데이터 수 */
}
else if(datacmp > 0)
addBST(&((*root)->left), data);
else
addBST(&((*root)->right), data);
}
return ;
}
/**********************************************
* 트리에 저장된 값을 출력 해주는 함수
* "책제목, 저자명, 중복된 책수"를
* 표 형식으로 출력 해줌
**********************************************/
void printBST(bst_t *root){
if(root){
printBST(root->left);
printTable(&(root->data));/* 표 형식으로 출력 해주는 함수 */
printBST(root->right);
}
return;
}
void algoBST(bst_t *root, int level){
int i;
if(root){
algoBST(root->left, level+1);
for(i = 0; i < level; i++) printf(" ");
printf("%s\n", "P");
algoBST(root->right, level+1);
}
}
/* Memory allocate free function */
void freeBST(bst_t *root){
if(root){
printBST(root->left);
printBST(root->right);
free(root->data.data);
free(root);
}
}
[이 게시물은 에렐리안님에 의해 2017-06-13 19:35:54 멤버게시판에서 이동 됨]