[자료구조] 이진 트리의 운행법(Traversal)

1. 트리의 운행법

- 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.

- 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.

- 이진트리의 운행법은 세 가지가 있따

- Preorder 운행 : Root -> Left -> Right 

- Inorder 운행 : Left -> Root -> Right

- Postorder 운행 : Left -> Right -> Root

- 예제)

- Preorder : A B D H I E C F G

- Inorder : H D I B E A F C G

- Postorder : H I D E B F G C A

2. 수식의 표기법

- 산술을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리를 많이 사용한다. 이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 된다.

- 전위 표기법(PreFix) : 연산자 -> Left -> Right (+AB)

- 중위 표기법(InFix) : Left -> 연산자 -> Right (A+B)

- 후위 표기법(PostFix) : Left -> Right -> 연산자 (AB+)

1) Infix 표기를 Prefix로 변환하기

X = A / B * (C + D) + E

(X = (((A / B) * (C + D))+E)) : 연산 우선순위에 따라 괄호로 묶는다.

=(X+(*(/(A B)+(C D))E)) : 연산자를 해당 괄호 앞으로 옮긴다.

=X+*/AB+CDE : 필요없는 괄호를 제거한다

2) Infix 표기를 Postfix로 변환하기

X = A / B * (C + D) + E

(X = (((A / B) * (C + D))+E)) : 연산 우선순위에 따라 괄호로 묶는다.

(X(((A B)/(C D)+)*E)+)= : 연산자를 해당 괄호의 뒤로 옮긴다.

XAB/CD+*E+= : 필요없는 괄호를 제거한다.

3) Postfix 표기를 Infix로 변환하기

A B C - / D E F + * +

((A (B C -) /) (D (E F +) *) +) : 먼저 인접한 피연산자 두 개와 오른쪽 연산자를 괄호로 묶는다.

((A / (B - C)) + (D * (E + F))) : 연산자를 해당 피연산자의 가운데로 이동시킨다

A / (B - C) + D * (E + F) : 필요 없는 괄호를 제거한다.

4) Prefix 표기를 Infix로 변환하기

+ / A - B C * D + E F

(+ (/ A (- B C)) (* D (+ E F))) : 먼저 인접한 피연산자 두 개와 왼쪽 연산자를 괄호로 묶는다.

((A / (B - C)) + (D * (E + F))) : 연산자를 해당 피연산자의 가운데로 이동시킨다

A / (B - C) + D * (E + F) : 필요 없는 괄호를 제거한다.

3. 스레드 이진트리(Threaded Binary Tree)

- 스레드 이진 트리는 이진 트리(Binary Tree)에서 발생하는 널(Null) 링크를 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 트리를 말한다.

- 이진 트리를 이중 연결 리스트(Doubly Linked List)로 표현할 때 임의의 노드에 대한 자식 노드가 없는 부분의 링크 포인터로 Nil Pointer를 기억시키게 된다.

- 스레드 이진 트리 표현 방법

- 어떤 노드의 왼쪽 링크 포인터가 Nil이면 그 노드의 직전에 검사된 노드를 가리키는 포인터로 사용하고, 오른쪽 링크 포인터가 Nil이면 그 노드의 직후에 검사될 노드를 가리키는 포인터로 사용한다.

- 해당 노드의 직전, 직후 노드는 트리의 운행봅(Traversal)에 따라 방문한 노드의 순서대로 결정한다.