이진 트리
모든 노드의 차수(Degree)가 2 이하인,
즉 각 노드가 최대 두 개의 자식 노드(Left, Right)를 가지는 트리 구조
- 자식의 순서가 있는 순서 트리
- 공백(Null) 서브트리 가능
- 레벨 i에서 최대 노드 수 = 2^(i-1)
- Terminal Node수가 n₀, 차수가 2인 노드 수가 n₂라 할 때
트리 운행법
트리의 각 노드를 일정한 규칙에 따라 한 번씩 방문하는 방법
이진 트리의 순회는 산술식의 표기법과 직접적으로 관련됨
- 전위 운행(Preorder)
- Root → Left → Right
- 루트 노드를 먼저 방문한 후 왼쪽, 오른쪽 자식 순으로 탐색
- 중위 운행(Inorder)
- Left → Root → Right
- 왼쪽 서브트리를 먼저 방문, 그 다음 루트, 마지막 으로쪽 서브트리
- 후위 운행(Postorder)
- Left → Right → Root
- 왼쪽과 오른쪽 서브트리를 모두 방문한 후 루트 노드를 방문
수식의 표기법
이진 트리를 이용해 수식을 표현할 때,
트리를 순회하는 방식에 따라 세 가지 표기법이 만들어짐
- 전위 표기법(Prefix)
- 연산자 → Left → Right
- 연산자가 앞에 위치
- 중위 표기법(Infix)
- Left → 연산자 → Right
- 연산자가 피연산자 사이에 위치
- 후위 표기법(Postfix)
- Left → Right → 연산자
- 연산자가 뒤에 위치
