[트리 순회] 알고리즘 - 트리 순회

트리 순회

트리 구조에서 각각의 노드를 정확히 한 번만 체계적인 방법으로 방문하는 과정을 말한다.

 

 

순회의 종류

전위 순회(preorder) : 뿌리(root)를 먼저 방문한다.

중위 순회(inorder) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문한다.

후위 순회(postorder) : 하위 트리를 모두 방문 후 뿌리(root)를 방문한다.

레벨(층별) 순서 순회(level-order, 너비 우선 순회) : 위쪽 node부터 아래방향으로 차례로 방문한다.

 

 

 

ex)

전위 순회

순서

1. 노드를 방문한다.
2. 왼쪽 서브트리를 전위 순회한다.
3. 오른쪽 서브트리를 전위 순회한다.

 

방문 순서 

A, B, D, G, H, E, C, F, I

 

---

중위 순회 

순서

1. 왼쪽 서브트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브트리를 중위 순회한다.

 

방문 순서

G, D, H, B, E, A, C, I, F

 

---

후위 순회

순서

1. 왼쪽 서브트리를 후위 순회한다.
2. 오른쪽 서브트리를 후위 순회한다.
3. 노드를 방문한다.

 

방문 순서

G, H, D, E, B, I, F, C, A

---

 

레벨 순서 순회

낮은 레벨부터 차례로 순회한다.

 

방문 순서

A, B, C, D, E, F, G, H, I

 

---