Binary Search Tree

소개글

C를 기반으로 binary search tree 작성

목차

1. C code
2. 결과 출력
3. 문제에 대한 설명 및 결과 분석

본문내용

(3) 코드 분석
Binary Search Tree는 한 노드에서 두 개 이하의 children을 갖는 Binary Tree의 특징을 가지고 있으면서, 한 노드의 왼쪽에 있는 subtree의 값은 그 노드의 값보다 작고 오른쪽에 있는 subtree의 값은 그 노드의 값보다 크다는 특징이 있다. 이런 특징을 살리기 위해서 각 노드는 구조체로 정의된 형태를 취하게 되며, 구조체 안에는 구체적 정보가 포함되어 있으며 pointer의 형태로 left와 right가 있어서 밑의 subtree를 가리키게 된다. 그래서 제일 먼저 구조체 data를 정의하고, 밑에 필요한 MakeEmpty와 Insert 함수를 각각 정의 한다. MakeEmpty는 Binary Search Tree를 비울 때 사용하는 함수 이며, Insert는 Tree에 데이터를 추가할 때 사용하는 함수이다. MakeEmpty 함수는 recursive한 성격을 갖게끔 하여 구현한다. Binary Search Tree T의 왼쪽 Subtree를 모두 지우고 오른쪽 subtree를 지운다음 마지막으로 root를 지우는 recursive한 형태로 구현한다.

참고 자료

없음