이진 트리 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)

클릭하면 색깔 표시 없는 이미지 원본 출처로 이동

 

 

이진 트리를 순회하는 방법은 보통 3가지로 나눈다

 

전위 순회(Preorder)

root - left - right 순서로 순회한다

 

위 그래프에선

1. A12

2. 1은 BD 순서로 순회하므로 ABD2

3. 2는 CE3 순서로 순회하므로 ABDCE3

4. 3은 FG 순서로 순회하므로 ABDCEFG

 

중위 순회(Inorder)

left - root - right 순서로 순회한다

 

위 그래프에선

1. 1A2

2. 1은 DB 순서로 순회하므로 DBA2

3. 2는 EC3 순서로 순회하므로 DBAEC3

4. 3은 FG 순서로 순회하므로 DBAECFG

 

후위 순회(Postorder)

left - right - root 순서로 순회한다

 

위 그래프에선

1. 12A

2. 1은 DB 순서로 순회하므로 DB2A

3. 2는 E3C 순서로 순회하므로 DBE3CA

4. 3은 GF 순서로 순회하므로 DBEGFCA