Winwoo's Story

수식 트리

1. 수식 트리의 이해

- 중위 표기법은 사람이 보기에는 좋으나 컴퓨터가 인식하기 어려운 표기법이다.

- 후위 표기법을 이용한 수식 트리를 이용하면 쉽게 수식 연산을 할 수 있다.

(중위 표기법 -> 후위 표기법 -> 수식 트리 순)

*후위 표기법 이란 7+4*2-1 -> 74+2*1- 처럼 연산자를 숫자 뒤에 표현하는 것을 말한다.

2. 수식 트리 구현

이진 트리의 순회

1. 순회의 세 가지 방법

- 기준 : root node를 언제 방문 하는지

- 재귀적 형태로 구성하면 높이 상관없이 순회 가능

※ VisitFuncPtr 함수 포인터를 사용하여 트리 구조를 이용한 원하는 행동을 할 수 있음

이진 트리

1. 이진 트리의 조건

- root node를 중심으로 두 개의 sub tree로 나뉘어진다.

- 나누어진 두 sub tree도 모두 이진 트리이어야 한다.

※ 트리 그리고 이진 트리는 그 구조가 재귀적이다. 따라서 트리와 관련된 연산은 재귀적 사고와 구현을 할 필요가 있다.

2. 이진 트리와 공집합 노드

- 하나의 노드에 두 개의 노드가 달리는 형태의 트리는 모두 이진 트리이다

- 공집합(Empty set)도 이진 트리에서는 노드로 간주한다.

 -> 그러므로 형제 노드가 비어 있다고 해도 공집합으로 간주하여 이진 트리      가 성립 된다.

3. 이진 트리의 레벨과 높이

- root 노드 부터 0레벨로 시작하고, 아래로 갈수록 레벨이 증가한다.

- 레벨의 최대값과 트리의 높이는 같다.

3. 완전 트리와 포화 트리

- 완전 이진 트리는 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리를 의미한다.

- 따라서 포화 이진 트리는 동시에 완전 이진 트리이다.

- 하지만 와전 이진 트리는 포화 이진 트리가 될 수 없다.

4. 이진 트리 구현의 두 가지 방법

4_1 배열을 이용한 표현

- 노드에 번호를 부여하고 그 번호를 배열의 인덱스 값으로 활용

- 편의상 배열의 첫 번째 요소는 사용하지 않음

- 트리가 완성 된 이후부터 탐색이 자주 일어날 경우 효율적

4_2 연결리스트를 이용한 표현

- 트리의 구조와 리스트의 연결 구조가 일치한다.

- 구현과 관련된 직관적인 이해가 더 좋은 편

5. 이진 트리 구현 - 노드 구조체 정의