[C/C++, Data Structure] Binary Search Tree를 이용한 단어 빈도 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <ctype.h>
#include <time.h>

#define MAX_FNAME 100
#define MAX_WORDS 10000
#define MAX_WORD_SIZE 100
#define TRUE 1
#define FALSE 0

//  데이터 형식
typedef struct {
    char word[MAX_WORD_SIZE]; // 단어
    int count;
} element;
//  노드의 구조
typedef struct TreeNode {
    element key;
    struct TreeNode *left, *right;
} TreeNode;

// 문자열 비교 strcmp 함수
// 만약 e1 < e2 -> 음수 반환 (시스템에 따라: -1)
// 만약 e1 == e2 -> 0 반환
// 만약 e1 > e2 -> 양수 반환 (시스템에 따라: 1)
int compare(element e1, element e2)
{
    return strcmp(e1.word, e2.word);
}

// 디스크 파일로부터 한 개 단어를 읽어 배열 word에 저장
// 성공적으로 읽었으면 TRUE, 그렇지 않으면(파일 끝) FALSE 리턴
int getword(FILE *fd, char *word)
{
    char ch;
    int i;
    
    do {
        ch = getc(fd);
        if (ch == EOF)
            return FALSE;
    } while (!isalpha(ch)); // 첫번째 알파벳 문자가 나올때까지 읽는다.
    i = 0;
    do { // 단어 1개를 읽는다.
        ch = tolower(ch); // 소문자로 변환
        word[i++] = ch;
        ch = getc(fd);
    } while (isalpha(ch)); // 알파벳 문자이면 계속 읽는다.
    word[i] = '\0';
    return TRUE;
}

TreeNode * new_node(element elem)
{
    TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
    temp->key = elem;
    temp->left = temp->right = NULL;
    return temp;
}

// Binary Search Tree에 삽입하려는 단어가 없는 경우 추가, 이미 있는 경우에는 빈도(count)만 증가
TreeNode * update_BST(TreeNode *root, element key)
{
    // 교재 프로그램 insert_node() 참고하여 작성
    // 트리가 공백이라면 새로운 노드를 반환
    if (root == NULL) return new_node(key);
    
    // 순환적으로 트리 순회
    if (compare(key, root->key) == 0){ //key == root->key, 삽입하려는 단어가 이미 있는 경우
        root->key.count++;
        return root;
    }
    if (compare(key, root->key) < 0 ){ // key < root->key
        root->left = update_BST(root->left, key);
    } else if (compare(key, root->key) > 0){ // key > root->key 
        root->right = update_BST(root->right, key);
    }
    
    return root;
}

// inorder traversal
void inorder(TreeNode *t)
{
    // 방문한 노드의 단어와 count 출력
    if (t != NULL){
        inorder(t->left);
        printf("%s %d ", t->key.word,t->key.count);
        inorder(t->right);
    }
}

// 노드 개수 세기
int get_node_count(TreeNode *node)
{
    int count = 0;
    
    if (node != NULL){
        count = 1 + get_node_count(node->left) + get_node_count(node->right);
    }
    
    return count;
}

// 최대값 return
int max(int a, int b)
{
    return (a>b)?a:b; // a>b면 a 아니면 b
}
// 트리 높이 계산
int get_height(TreeNode *node)
{
    int height = 0;
    if (node != NULL){
        height = 1+ max(get_height(node->left), get_height(node->right));
    }
    return height;
}

// Binary Search Tree를 사용하여 단어 빈도 파악
int main()
{
    FILE *fd;
    element e;
    TreeNode *root=NULL;
    TreeNode *tmp;
    char fname[MAX_FNAME]; // 파일 이름
    char w[MAX_WORD_SIZE]; // 읽어들인 단어
    int flag; // 파일 끝이 아닌지 여부
    clock_t start, finish;
    double duration;
    
    printf("파일 이름: ");
    scanf("%s", fname);
    if( (fd = fopen(fname,"r")) == NULL ) {
        fprintf(stderr, "파일을 열수없습니다.\n");
        return;
    }

    start = clock(); // 시간 측정 시작
    do {
        flag = getword(fd, w); // 단어 1개 읽기
        strcpy(e.word, w);
        e.count = 1;
        // printf("%s, %d", e.word, e.count);
        if (flag == FALSE) //파일의 끝이면
            break;
        root = update_BST(root, e);
        // printf(" %s %d", tmp->key.word, tmp->key.count);
    } while(1);
    finish = clock(); // 시간 측정 종료
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    
    inorder(root);
    printf("\n노드 개수 = %d\n", get_node_count(root));
    printf("트리 높이 = %d\n", get_height(root));
    
    printf("\n%.6f 초입니다.\n", duration);
}

실행결과