[Data Structure] Tree 전위, 중위, 후위 순회

트리 기본 개념에 대해서 보려면 아래의 글을 먼저 확인하자.

2022.08.27 - [Data Structure/Tree] - [Data Structure] Tree 기본

[Data Structure] Tree 기본

 

트리의 순회

트리의 순회 방법에는 대표적으로 세가지 방법이 존재한다.

 

전위 순회

전위 순회는 루트 > 왼쪽 서브트리 > 오른쪽 서브트리 순서로 탐색이 재귀적으로 이루어지는 순회 방법이다.

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

 

마지막으로, 이진 탐색 트리와 순회에 대한 내용을 코드로 구현해보려고 한다.