트리 순회(tree traversal) 프로그래밍

소개글

1. 배열을 이용한 Preorder
2. 재귀적인 방법을 이용한 Preorder
3. 비재귀적인 방법을 이용한 Preorder
4. 포인터를 이용한 BFS(breadth-first search)
5. 포인터를 이용한 DFS(depth-first serch)

+ 각 알고리즘의 비교 분석(HWP파일)

목차

1. 목적
2. 사용한 방법 및 알고리즘
3. 프로그램 실행 후의 각 알고리즘의 비교
4.이 assignment를 통해 이해한 사항

본문내용

2. 사용한 방법 및 알고리즘
- 각 프로그램에 입력은 gets를 이용하여 입력받아 입력받은 문자를 하나씩 뜯어내어 Binary Tree를 구성하였고, 각 요구사항에 맞춰 알고리즘을 적용하였다.
- 각 입력값에 따른 시간 복잡도의 변화를 알아보기 위해 입력한 노드의 개수를 500개, 1000개, 1500개, 2000개, 2500개, 3000개, 3500개, 4000개로 늘여가면서 linear하게 입력하였다. 초기 입력 노드값을 gets로 받도록 제작하였기 때문에 4000개 이상의 많은 경우에 대한 테스트를 하는데 어려움이 있고, 미리 여분의 텍스트에 입력할 값들을 미리 지정해 놓아 같은 값을 집어 넣을 수 있도록 했다.
- 출력은 입력받은 노드값들을 Binary Tree로 구성한 다음, Preorder로 변환하여 나온 결과를 차례대로 찍어내도록 만들어 내었다. 변환이 잘 되었는지를 확인하기 위해 우선 초기 입력 노드의 개수를 작게 하여, 직접 노드를 그려보아 맞게 되었는지를 확인하였다.
- 각 프로그램의 시간복잡성을 알아보기 위해서 각 프로그램의 실행 시간을 측정하여 비교하였다. QueryPerformanceCounter 함수를 사용하여, 밀리 초 단위로 측정하였으며, 소수점 아래 4자리까지 고려하여 시간을 출력하였다.
- 각 프로그램에서 사용된 알고리즘은 다음과 같다.

참고 자료

없음

압축파일 내 파일목록

bfs_pointer.c
dfs_pointer.c
preorder analysis.hwp
preorder 그래프 비교.xls
preorder_array.c
preorder_non.c
preorder_pointer.c
입력값.txt