[C언어]배열을 이용한 이진탐색트리 삽입, 삭제, 탐색 연산 프로그램

소개

배열을 이용하여 이진탐색트리를 구현.
삽입, 삭제, 탐색 연산 수행

1) 이진탐색트리의 삽입 연산은 현재 트리의 리프노드에서만 이루어진다. 따라서 삽입하려는 데이터의 크기 비교를 통하여 빈 노드가 있는 위치까지 찾아가 삽입이 이루어지는 방식으로 구현되어야 한다. 이번 프로그램에서는 배열로 트리가 구현되므로 인덱스 1이 루트노드에 해당하게 된다. 따라서 인덱스 1부터 탐색을 하며 왼쪽 자식의 경우 2를 곱하고, 오른쪽 자식의 경우 2를 곱한 후 1을 더하면서 저장될 위치를 찾으면 될 것이다.

2) 삽입 연산은 insert_Element, insert 함수가 담당한다. 여기서 insert는 삽입할 데이터를 받아오는 역할만 하며 실제적인 삽입 연산은 insert_Element에서 실행된다. insert_Element는 탐색함수를 이용하여 삽입할 위치를 결정하고 해당 위치에 입력된 데이터를 저장하여 준다. 이때 트리에 저장할 공간이 없는 경우 또는 이미 삽입된 레코드를 삽입하려는 경우는 삽입 실패 메시지를 띄워주고 함수를 종료한다. 삽입 연산은 insert에서 더 이상 삽입을 안 하겠다는 선택을 하기 전까지 이루어지게 된다. 삽입 할 데이터 및 삭제, 탐색 시 이용할 모든 데이터를 받아오는 역할을 담당하는 함수는 Get_Element이다.


typedef struct entry{ // 트리의 노드로 쓰일 구조체
int id;
char name[10];
char value;
}element;

element *BST[MAXSIZE+1]; // 이진탐색트리의 선언

void initSet_BST(){
int i = 0;
for(; i <= MAXSIZE; i++) { BST[i] = (element *)malloc(sizeof(element)); BST[i] = 0; }
} // 이진탐색트리 초기화

void delete_BST(){
int i = 0;
for(; i <= MAXSIZE; i++) free(BST[i]);
} // 이진탐색트리 삭제

int delete_Element(element *a); // 지정된 노드를 삭제하고 트리를 재구성하는 함수
int insert_Element(element *a); // 지정된 노드를 삭입하고 트리를 재구성하는 함수
int search_Element(element *a); // 지정된 노드를 찾아 그 위치를 반환하는 함수

void _insert(); // 삽입함수
void _delete(); // 삭제함수
void _search(); // 탐색함수
void reconstruct_BST(int i); // 트리 재구성 함수

void Get_Element(element *a); // 트리의 노드로 쓰일 정보를 받아오는 함수
void Get_String(char *strtemp); // 문자열을 받아오는 함수
int Get_intData(); // 정수를 받아오는 함수
void _strcpy(char *a, char *b); // 문자열 복사 함수
int _strcmp(char a[], char b[]); // 문자열 비교 함수
int _strlen(char a[]); // 문자열의 길이를 구하는 함수

int main()
{
int select;
initSet_BST();
while(1){
printf("======================================================n");
printf("1.INSERT 2.DELETE 3.SEARCH 4.EXITn");
printf("======================================================n");
select = Get_intData();

컴파일 실행환경

c

참고자료

· 없음