이진트리검색

#include
#include
#include

typedef struct node {

struct node* left;
char* word;
int count; // 추가 1
struct node* right;
} NODETYPE;

int insert_node(NODETYPE* root, char* str);
NODETYPE* search(NODETYPE* root, char* key);

void inorder(NODETYPE* root);

int main()
{

NODETYPE* tree = NULL;
NODETYPE* ptr;
char wbuf[30];

printf(" 검색 트리에 저장할 단어를 입력하세요.\n 입력의 끝에는 quit를 입력하세요.\n");

while( strcmp(gets(wbuf), "quit") ) {

if(!tree) { // 트리가 비었을 때

tree = (NODETYPE*)malloc(sizeof(NODETYPE));
tree -> word = (char*)malloc(strlen(wbuf)+1);
strcpy(tree->word, wbuf);
tree->left = tree->right = NULL;
tree->count = 1; // 추가 2
}
else
insert_node(tree, wbuf);

} // end while

printf("\n\nEnter a key to search : ");
gets(wbuf);

ptr = search(tree, wbuf);

if(ptr)
printf("%s is in this tree.\n\n", ptr->word);
else
printf("%s is not exist.\n\n", wbuf);

printf("---트리안의 단어들 (사전식 순서)----------------\n\n");
inorder(tree);

return 0;
}

NODETYPE* search(NODETYPE* root, char* key) {

NODETYPE* tptr = root;
int cmp;

while(tptr) {

cmp = strcmp(key, tptr->word);
if(cmp < 0)
tptr = tptr->left;
else if(cmp > 0)
tptr = tptr->right;
else // found
return tptr;

} // end while

return NULL; // not found
}

int insert_node(NODETYPE* root, char* word)
{
NODETYPE* tptr = root, *before;
int cmp = 0;

while(tptr) {
cmp = strcmp(word, tptr->word);
if(cmp < 0) {
before = tptr;
tptr = tptr->left;
}
else if(cmp > 0) {
before = tptr;
tptr = tptr->right;
}
else
(tptr->count)++; // 추가 3 빈도수

return 0;
} // end while

tptr = (NODETYPE*)malloc(sizeof(NODETYPE));
tptr->word = (char*)malloc(strlen(word)+1);

strcpy(tptr->word, word);
tptr->left = tptr->right = NULL;

tptr->count = 1; // 추가 4

if(cmp < 0)
before->left = tptr;
else
before->right = tptr;

return 1;

}

void inorder(NODETYPE* ptr)
{
if(ptr) {

inorder(ptr->left);
printf("%s \t %d\n", ptr->word, ptr->count); // 추가 5
inorder(ptr->right);
}
}

[출처] C언어 이진트리 검색|작성자 sangtakeg