트리의 개요
정점과 선분을 이용하여 사이클을 이루지 않도록 구성한 그래프
- 가족의 계보, 조직도 등을 표현하기에 적합함
용어
-
노드(Node)
: 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것 -
근노드(Root Node)
: 맨 위에 있는 노드 -
디그리(Degree, 차수)
: 각 노드에서 뻗어 나온 가지의 수 -
단말 노드(Terminal Node) = 잎 노드(Leaf Node)
: 자식이 하나도 없는 노드
: 디그리가 0인 노드 -
자식 노드(Son Node)
: 어떤 노드에 연결된 다음 레벨의 노드 -
부모 노드(Parent Node)
: 어떤 노드에 연결된 이전 레벨의 노드 -
형제 노드(Brother Node, Sibling)
: 동일한 부모를 갖는 노드 -
트리의 디그리
: 노드들의 디그리 중에서 가장 많은 수
트리의 운행법
운행법(Traversal): 각 노드들을 찾아가는 방법
-
Preorder 운행
: Root→Left→Right -
Inorder 운행
: Left→Root→Right -
Postorder 운행
: Left→Right→Root
서브트리 단위로 묶어서 보기
수식의 표기법
산술식을 계산하기 위해 기억 공간에 기억시키는 방법으로 이진 트리를 많이 사용함
-
전위 표기법(PreFix) : 인오더
: 연산자→Left→Right -
중위 표기법(InFix) : 프리오더
: Left→연산자→Right -
후위 표기법(PostFix) : 포스트오더
: Left→Right→연산자
수식 변환
PostFix나 PreFix는 스택으로 처리함
→ InFix는 변환시켜서 처리
X = A / B * (C+D) + E
PreFix
1. 우선순위에 따라 괄호 묶기
2. 연산자를 괄호 앞으로 옮기기
→ X +((/AB +CD)E)
3. 괄호 제거
→ X+/AB+CDE
PostFix
위 방법에서 연산자를 뒤로 옮기기
InFix로 변환하기
연산자를 피연산자 두 개 가운데로 옮기기
ABC-/DEF++
→ A/(B-C)+D(E+F)
