이진 탐색 트리

탐색에 대표적인 것으로  이진탐색이 있습니다.

이분화 하여 탐색하는 것이기에 시간과 자원의 효율이 극대화 됩니다.

함수로는....

tsearch(const void *key,void **rootp,int(*compare)(const void *,const void *));

이진트리에서 데이터를 탐색하는 함수입니다.  발견치 못할시 트리에 추가합니다.

tdelete(const void *key,void **rootp,int(*compare)(const void *,const void *));

이진트리에서 데이터를 삭제 합니다.

twalk(const void*root,void(*action)(const void *nodep,const VISIT which,const int depth));

이진트리를 방문합니다.

key:찾고자 하는 데이터

rootp,root:이진트리에 대한 포인터

compare:두 데이터를 비교하는 함수 같으면 0, 다르면 0이 아닌값을 반환..

action:구체적인 동작을 하는 함수

이외에 tfind()라는 함수가 있으나 이 함수는 데이터를 찾지 못할시에 트리에 추가 되지않습니다.

그외엔 다 같은 기능을 가지고 있죠..

약간의 예를 들면..

int compare(const void *a,const void *b);

void printtree(void **node,VISIT order,int depth);

main()

{

void *root;

root=NULL;

tsearch("Hello",&root,compare);

tsearch("C",&root,compare);

twalk(root,printtree);//위의 tsearch함수에서 Hello와 C가 추가 되었고 그내용들을 출력

tdelete("C",&root,compare);

twalk(root,printtree);//위의 tdelete함수에서 C를 삭제후 그내용들을 출력

}

int compare(const void *a, const void *b)

{

return strcmp((char*)a,(char*)b);

}

void printtree(void **node,VISIT order,int depth)

{

char *str;

str=*(char**)node;

if(order==postorder || order==leaf)

printf("string:%s\n",str);

}

VISIT은 enum으로 열거형 자료타입 입니다.

typedef enum{preorder,postorder,endorder,leaf}VISIT;