자료구조 레포트 (이진 탐색 트리를 중순위, 레벨 순위로 방문) - 입력 파일, 출력 결과 및 코드 포함

소개

연결리스트를 사용하여 이진 탐색 트리를 구성하고, 구성된 이진 탐색 트리에 대해서 중순위, 레벨 순위로 방문한 결과를 출력하는 과제입니다.
입력 파일(.txt), 출력 결과 캡쳐(.jpg) 및 전체 코드(보고서 내에 포함)가 포함되어 있습니다.

목차

1. 문제 해석

2. 입출력의 예
(1) 입력 파일의 예
(2) 출력의 예

3. 문제풀이 방법 (알고리즘)

4. 소스 코드

5. 수행 결과

6. 결과값 비교
(1) BST1.TXT
(2) BST2.TXT
(3) BST3.TXT
(4) BST4.TXT

7. 결과 분석 및 토의

본문내용

1. 문제 해석
입력 파일에서 데이터를 입력 받아 연결리스트(Linked List)를 사용하여 이진 탐색 트리를 구성한 다음, 구성된 이진 탐색 트리에 대해서 중순위(in-order)로 방문한 결과와 레벨 순위(level order)로 방문한 결과를 각각 출력하는 문제이다. 조건으로는 1. 각 노드의 데이터 필드는 시험 점수(정수형)와 이름(문자열로 최대 길이는 5)으로 구성된다. 2. 이진 탐색 트리 구성 시의 key 값은 시험 점수이다. 3. 중순위(in-order) 방문은 재귀 또는 반복문(스택 사용)을 이용할 수 있다. 4. 레벨 순위(level order) 방문은 큐(환형큐/배열 또는 연결리스트)를 이용한다. 5. 방문한 노드는 두 개의 필드(시험 점수, 이름)를 모두 출력한다.

2. 입출력의 예
(1) 입력 파일의 예
7
50 CHOI
31 LEE
67 PARK
88 JUNG
35 KIM
21 AHN
48 SUNG

(2) 출력의 예
(1) In-order Traversal – 중순위 운행 결과
21 AHN
31 LEE
35 KIM
48 SUNG
50 CHOI
67 PARK
88 JUNG

(2) Level-order Traversal – 레벨순위 운행 결과
50 CHOI
31 LEE
67 PARK
21 AHN
35 KIM
88 JUNG
48 SUNG
위 출력 방식은 문제에서 주어진 방식이 아니라 임의적으로 포맷을 변경한 방식으로, 위와 같은 방식으로 출력하였다.

3. 문제풀이 방법(알고리즘)
이진 탐색 트리를 구성하기 위해 연결 리스트(Linked List)를 구현하였다. nd라는 struct를 생성하여 데이터 필드로 score와 name을 가지고, treePointer인 leftChild와 rightChild를 가지도록 하였다. 또, treePointer는 nd의 포인터로 하여 구현하였다. 먼저 이진 탐색 트리를 구성하기 위해 하나의 노드를 트리에 추가하려면 새로운 노드를 삽입할 위치를 찾아야 한다.

참고자료

· 없음