Algorithm #2. Search algorithm. - 2.4 Binary Tree Search (2).

#include <stdio.h> #include <string.h> #include <stdlib.h> /* Binary search tree 구현에 사용할 NODE 구조체. */ typedef struct node{ char dat; struct node *lLink; struct node *rLink; } bTree_node; /* Binary search tree의 구성을 위한 함수의 prototype. */ void bTreeInsert(char data, bTree_node **root); /* Tree 구성에 필요한 함수의 prototype. */ bTree_node *TreeConstruct(void); /* Binary tree searching 에 필요한 함수의 prototype. */ int bTreeSearch(char key, bTree_node *root); /* 검색할 레코드*/ char input[] = "SEARCHALGORITHM"; /* main 함수. */ int main(void) { int i, length; char key; /* 우선 구현에 필요한 node 선언. */ bTree_node *root = NULL; length = strlen(input); /* 검색할 레코드, input 이라는 배열로부터 Binary search tree 를 구성한다. */ for(i=0 ; i<length ; i++) { bTreeInsert(input[i], &root); } /* 검색할 값을 입력받는다. */ scanf("%c", &key); /* Binary tree searching 을 위해 bTreeSerch() 함수를 호출한다. 1 이 리턴된다면 Find it, 0 이 리턴되다면 Can't find it.*/ if(bTreeSearch(key, root) == 1) { printf("Find it.\n"); } else { printf("Can't find it.\n"); } return 0; } void bTreeInsert(char data, bTree_node **root) { /* 만약 root에 NULL값이 들어가 있다면 - 즉, 초기화되지 않은 tree 라면. */ if(*root == NULL) { /* tree 의 기본 구성을 위해 TreeConstruct() 함수를 호출. 그리고 root node 에 값을 대입.*/ *root = TreeConstruct(); ((*root) -> dat) = data; } /* tree 의 root node 가 생성되어 있다면, Binary search tree 의 전제 조건을 만족하기 위해 다음 과정을 행한다. */ if( ((*root)->dat) < data) { bTreeInsert(data ,&((*root) -> rLink) ); } else if( ((*root) -> dat) > data) { bTreeInsert(data, &((*root) -> lLink)); } } bTree_node *TreeConstruct(void) { bTree_node *tempNode; /* 우선 tempNode의 메모리를 할당한다. */ tempNode = (bTree_node*)malloc(sizeof(bTree_node)); /* 좌, 우측 Link 를 NULL 로 초기화. */ tempNode -> lLink = NULL; tempNode -> rLink = NULL; /* tempNode 를 반환한다. */ return tempNode; } int bTreeSearch(char key, bTree_node *root) { /* 각 sub tree 의 root node 값을 저장할 check 변수 선언. */ char check = root -> dat; /* sub tree 의 좌, 우측 link 가 NULL 인 경우, 즉 tree 의 leaf 에서의 값을 검색한다. */ if((root -> lLink == NULL) && (root -> rLink == NULL)) { if(check == key) { return 1; } /* 만약 leaf 에서 key 값과 root node 의 값이 다르다면, Can't find it. */ else { return 0; } } /* 만약 key 값보다 root node 의 값이 크다면 좌측 sub tree 를 운행한다. */ if(check > key) { bTreeSearch(key, (root -> lLink)); } /* 만약 key 값보다 root node 의 값이 작다면 우측 sub tree 를 운행한다. */ else if(check < key) { bTreeSearch(key, (root -> rLink)); } /* 만약 key 값과 root node 의 값이 같다면 Find it. */ else if(check == key) { return 1; } }

Binary tree search 의 구현입니다.

시간에 쫓기면서 구현했심다 ㄱ-... 오류가 있을지도 모르겠네요.



덧)
소스코드의 설명은 주석을 달아놨으니 이해하실 수 있으리라 봅니다.
다음 포스트는 Red-Black tree 에 관한 것입니다만 -_-...

알아야 할 것들이 너무 많더군요. 더군다나 요새도 시간에 쫓기는 지라 오늘 포스팅하긴 무리일 것 같습니다.
따라서 Red-Black tree 포스트는 내일 오전중으로 올라가게 될 것 같네요. 죄송합니다.