[오늘의 지식] 트리의 순회

1. 트리의 순회란?

트리 구조 내의 모든 노드를 방문하기 위한 과정을 말한다.

종류로는 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)가 있다.

 

이러한 순회를 사용하는 이유는

트리 구조에서 데이터 탐색과 출력이 용이해지기 때문이다.

 

2. 순회 방법

노드 예시

 

전위 순회

Root - Left - Right

(ABDCEFG)

 

중위 순회

Left - Root - Right

(DBAECFG)

 

후위 순회

Left - Right - Root

(DBEGFCA)

 

전위 순회(Root - Left - Right)를 예시를 들어서 설명하자면

 

1. Root A노드 시작 (A)

2. Root : A - 왼쪽 자식 노드 B 탐색 (AB)

3. Root : B - 왼쪽 자식 노드 D 탐색 (ABD)

4. B의 오른쪽 자식 노드가 없기 때문에 노드 C(A노드의 오른쪽)로 이동 (ABDC)

4. Root : C - 왼쪽 자식 노드 E 탐색 (ABDCE)

5. Root : C - 오른쪽 자식 노드 F 탐색 (ABDCEF)

6. Root : F - 오른쪽 자식 노드 G 탐색 (ABDCEFG)