이진트리 탐색 운행법

이진트리(Binary Tree)

부모와 자식으로 나뉘어 있는 트리 그래프

노드의 최대 차수가 2이며, 각각 왼쪽 자식(left child), 와 오른쪽 자식(right child)으로 나뉩니다.

 

이진트리의 순회

이진트리의 순회에는 크게 아래의 세 가지 방법이 있습니다. 기본적으로 DFS는 전위 순회를 가장 많이 사용합니다.

• 전위 식(Preorder) : Root -> Left -> Right
• 중위 식(Inorder) : Left -> Root -> Right
• 후위 식(Postorder): Left -> Righjt-> Root

전위 순회
전위 순회는 루트 노드가 가장 먼저 나오는 순회 방식입니다.

중위 순회
중위 순회는 각 루트 노드가 자식노드의 사이에 위치합니다.

후위 순회
후위 순회는 루트노드가 가장 마지막에 출력됩니다.
순서는 왼쪽 노드 -> 오른쪽 노드 -> 부모 노드 순으로 갑니다.

예시 이진 트리

• 전위 식(Preorder) 운행 순서: A, B, D, E, F, C, F, G, I
• 중위 식(Inorder) 운행 순서: D, B, E, H, A, F, C, I, G
• 후위 식(Postorder) 운행 순서: D, H, E, B, F, I, G, C, A

 

이진 트리의 Left, Root, Right 구별법

위 이미지와 같이 빨간색 -> 파란색 -> 초록색 순으로 Left, Root, Right 그룹을 각각 나뉘어서 생각하면 조금 더 편하게 운행 순서를 도출해 낼 수 있습니다.