[트리, Tree] 트리의 순회(Traversal)와 수식 트리에 대하여.

둘 이상의 노드로 이뤄져 있는 서브 트리를 완전히 삭제하고자 할 때, 서브 트리를 구성하는 모든 노드를 방문해야 한다.

순회란, 이렇듯 모든 노드를 방문하는 것을 뜻한다.

이진 트리의 순회는 연결 리스트의 순회와 달리 별도의 방법이 필요하다.

이번에는 트리의 순회와 이를 활용하는 수식 트리에 대해 설명하도록 하겠다.

---

 

1. 순회의 세 가지 방법

• 전위 순회(Preorder Traversal) : Root -> left -> right
• 중위 순회(Inorder Traversal) : Left -> root -> Right
• 후위 순회(Postorder Traversal) : Left -> RIght -> Root

• 전위 순회(Preorder Traversal) : A -> B -> C
• 중위 순회(Inorder Traversal) : B -> A -> C
• 후위 순회(Postorder Traversal) : B -> C -> A

 

---

 

2. 수식 트리(Expression Tree)

 : 트리를 도구로 활용한 것으로 이진 트리를 이용해서 수식을 표현해 놓은 것을 수식트리라 한다.

수식 트리를 사용하는 이유는 수식을 수식 트리로 표현하면 컴파일러의 수식 해석이 좋아진다. 따라서 컴파일러는 수식의 이해를 위해 수식을 수식 트리로 재표현한다.

우리가 보통 생각하는 수식은 6 + 2 * 2 - 1 = 9 인데, 이것은 수식 트리에서 중위 표기법의 수식이라 한다.

6 + 2 * 2 - 1 = 9 수식 트리

6 + 2 * 2 - 1 = 9의 계산

수식 트리의 표시법은 순회 종류에 따라 나뉘어 지므로 이 역시 3가지이다.

• 전위 표기법(Prefix) : 전위 순회하여 데이터를 출력, 연산자 -> Left -> Right, - + 6 * 2 2 1
• 중위 표기법(Infix) : 중위 순회하여 데이터를 출력, Left -> 연산자 -> Right, 6 + 2 * 2 - 1
• 후위 표기법(Postix) : 후위 순회하여 데이터를 출력, Left -> Right -> 연산자, 6 2 2 * + 1 -

 

X = A / B * (C + D) + E를 기준으로 표기법 바꾸기

• 중위 -> 후위 : 중위로 표기된 수식에서 연산자를 해당 피연산자의 2개의 뒤(오른쪽)에 오도록 이동한다.
  X = A / B * (C + D) + E ---> XAB/CD+*E+=

1. 연산 우선순위에 따라 괄호로 묶는다
2. 연산자를 해당 괄호의 뒤로 옮긴다
3. 괄호를 제거한다

• 중위 -> 전위 : 중위로 표기된 수식에서 연산자를 해당 피연산자 2개의 앞(왼쪽)에 오도록 이동하면 된다.
  = X + * / A B + C D E

1. 연산 우선순위에 따라 괄호로 묶는다.
2. 연산자를 해당 괄호의 앞으로 옮긴다.
3. 괄호를 제거한다.

• 후위 -> 중위 : 후위는 중위 표기법에서 연산자를 해당 피연산자 2개의 뒤(오른쪽)로 이동한 것으로 연산자를 다시 해당 피연산자 2개의 가운데로 옮기면 된다.

1. 먼저 인접한 피연산자 2개의 오른쪽의 연산자를 괄호로 묶는다.
2. 연산자를 해당 피연산자의 가운데로 이동시킨다.
3. 필요없는 괄호를 제거한다.