아주대학교 자료구조 및 알고리즘 과제3 이진 트리 (전자공학과)

소개

2016년 1학기 자료구조 A+받았습니다.

목차

1. 문제분석
2. 배경지식
3. 자료구조/알고리즘의설명
4. 소스코드분석
5. 결과 화면에 대한 분석
6. 참고자료

본문내용

① 문제분석
- 요구사항
이번 과제는 자료구조 및 알고리즘의 이해 과목의 세 번째 과제로, 스택, 큐 그리고 트리 자료구조를 이용했다. 과제의 큰 맥락으로서 주어진 중위 표현을 이용해 후위 표현식을 생성하고 이를 이용해 수식트리를 생성한다. 생성된 수식트리를 이용해 preorder, inorder, postorder 그리고 levelorder 방식의 순회하여 순회에 따른 결과를 출력하고 최종적으로 수식 결과값을 출력하게 된다.

- 제약사항
이번 과제는 전적으로 한 자릿수 수식에 관련됐기 때문에 수식의 입력에 대한 사항이 큰 제약사항이다. 평소에 사용하는 중위 표현 수식에서 유효하지 않은 식이 제약사항이 된다. 우선, 의도한 연산자와 수 이외의 입력에 대해선 다루지 않는다. 입력은 사칙연산(+-*/)과 10진수(0~9)까지만이 유효하며 이외의 문자, 특수 문자 심지어 2자리 이상의 수도 유효하지 않다. 다음으로, 나누기(/)연산자 뒤에 0이 올 경우, 이는 pole이 되기 때문에 사칙연산에선 불가능하다. 마지막으로 소괄호만 사용하되, 괄호의 짝이 맞지 않는 표현 또한 제약사항이 된다.

② 배경지식
- 기능적 배경지식
이진 트리
이진 트리를 순회하는 표준적인 방식으로 전위(preorder), 중위(inorder), 후위(postorder)의 3가지 방법이 있다. 트리의 한 노드를 봤을 때 루트와 좌우 서브트리가 존재하게 된다. 루트를 방문하는 작업을 V, 좌측 서브트리를 L, 우측 서브트리를 R이라고 한다면 V 즉, 루트를 방문하는 순번에 따라 3가지로 분류하게 된다.
우선 전위 순회는 루트를 먼저 방문하고 왼쪽 서브트리, 오른쪽 서브트리를 방문한다. 따라서 기호로 나타낸다면 V.L.R순서가 된다.
중위 순회는 왼쪽 서브트리, 루트, 오른쪽 서브트리 순서로 방문하여 L.V.R로 표기 가능하다. 중위는 일반적으로 우리가 수식으로 표현하는 식이 해당된다. 예를 들면 4+5의 경우 V가 “+”에 해당하기 때문에 LVR 순으로 표기된다.

참고자료

· C언어로 쉽게 풀어쓴 자료구조, 천인국 외 2명, 생능출판, 2016년
· http://stackoverflow.com/questions/8375904/how-to-put-postfix-expressions-in-a-binary-tree