트리의 순회

이진 트리의 순회에 대한 개념을 알 필요가 있어 적어 둘려고 한다. 대학교 2학년 자료구조 수업에서 다룬것이었는데 거의 다 까먹었다. 뭐라는 것 정도만 알고 있는 정도다. 

트리의 순회를 이용하여 4칙연산과 같은 구현을 할 수 있다고 한다. 스택을 이용한 계산기 연산과 같은 부분에서 활용해봐야겠다. 

트리에는 전위 순회, 중위 순회, 후위 순회가 있다. 

- Pre order(전위)   : Root -> Left -> Right

=> Root로부터 왼쪽 모든 노드 탐색 후 오른쪽

24 15 2 19 28 27 30

- In order(중위) : Left -> Root -> Right

=> 맨 왼쪽 아래 노드부터 Root, 오른쪽 

2 15 19 24 27 28 30

- Post order(후위) : Left -> Right -> Root

=> 맨 왼쪽 아래노드부터 오른쪽 탐색 후 Root

2 19 15 27 30 28 24

완전이진트리의 순회를 이해하였다고 다 이해 한 것은 아니다. 

불균형 이진트리의 순회에 대해서 이해하는 것도 필요하다. 

- Pre Order(전위 순회)

A B D H E I C F G J K

- In Order(중위 순회)

H D I E B A F C J G K

- Post Order(후위 순회)

H D I E B F J K G C A

재귀적으로 호출하는 코드를 작성해보면서 더 정확하게 이해 할 필요가 있을 듯 싶다.