자료구조 이진 트리(Binary tree)의 순회(Traversal)

이진 트리의 순회

 

트리의 순회란?

• 트리의 모든 노드를 한 번씩 방문하는 것을 말한다.
• 트리 순회 방식은 노드를 방문하는 순서에 따라서 달라진다.

트리 순회에 필요한 용어

• V - 노드를 방문
• L - 왼쪽 서브 트리로 이동
• R - 오른쪽 서브 트리로 이동

이진 트리의 순회 방법

전위 순회 (Preorder)

1. 노드를 방문한다.
2. 왼쪽 서브 트리로 이동한다.
3. 오른쪽 서브 트리로 이동한다.

노드 A를 방문

노드 A의 왼쪽 서브 트리로 이동 -> 노드 B를 방문

노드 B의 왼쪽 서브 트리로 이동 -> 노드 D를 방문 

노드 D는 단말 노드이기 때문에 서브 트리로 이동 불가 -> B로 돌아간다 -> B의 오른쪽 서브 트리로 이동-> 노드 E를 방문

노드 E는 단말 노드이기 때문에 서브 트리로 이동 불가 -> A로 돌아간다. -> A의 오른쪽 서브 트리로 이동-> 노드 C를 방문

노드 C의 왼쪽 서브 트리로 이동 -> 노드 F를 방문하게 된다.

노드 F는 단말 노드이기 때문에 서브 트리로 이동 불가 -> C로 돌아간다 -> C의 오른쪽 서브 트리로 이동 -> 노드 G를 방문

노드 G가 마지막 노드로 모든 노드의 방문이 끝났다.

따라서 A->B->D->E->C->F->G

 

중위 순회 (Inorder)

1. 왼쪽 서브 트리로 이동한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리로 이동한다.

노드 A의 왼쪽 서브 트리로 이동-> 노드 B로 이동 -> 노드 B의 서브 트리로 이동 -> 노드 D를 방문

노드 D는 단말 노드 -> 노드 B로 돌아간다 -> 노드 B의 왼쪽 서브 트리의 방문이 끝났기 때문에 노드 B를 방문

노드 B의 오른쪽 서브 트리로 이동-> 노드 E를 방문

노드 E는 단말 노드 -> B로 이동 -> A로 이동, A의 왼쪽 서브 트리 방문 완료 -> 노드 A를 방문

A의 오른쪽 서브 트리로 이동 -> 노드 C로 이동 -> 노드 C의 왼쪽 서브 트리로 이동 -> 노드 F를 방문

노드 F는 단말 노드 -> C로 돌아간다 -> 노드 C의 왼쪽 서브 트리의 방문이 끝났기 때문에 노드 C를 방문

노드 C의 오른쪽 서브 트리로 이동 -> 노드 G를 방문

노드 G가 마지막 노드로 모든 노드의 방문이 끝났다.

따라서 D->B->E->A->F->C->G

 

후위 순회 (Postorder)

1. 왼쪽 서브 트리로 이동한다.
2. 오른쪽 서브 트리로 이동한다.
3. 노드를 방문한다.

노드 A의 왼쪽 서브 트리로 이동 -> 노드 B로 이동-> B의 왼쪽 서브 트리로 이동-> 노드 D를 방문

노드 D는 단말노드 -> 노드 B로 돌아간다 -> 노드 B의 오른쪽 서브 트리로 이동 -> 노드 E를 방문

노드 E는 단말노드 -> 노드 B로 돌아간다 -> 노드 B를 방문

노드 B의 서브 트리의 방문이 끝났기 때문에 노드 A로 돌아간다 -> 노드 A의 오른쪽 서브 트리로 이동 -> 노드 C로 이동 -> 노드 C의 왼쪽 서브 트리로 이동 -> 노드 F를 방문

노드 F는 단말 노드 -> 노드 C로 돌아간다 -> 노드 C의 오른쪽 서브 트리로 이동 -> 노드 G를 방문

노드 G는 단말 노드 -> 노드 C로 돌아간다. -> 노드 C를 방문

노드 C의 서브 트리의 방문이 끝났기 때문에 노드 A로 돌아간다 -> 노드 A의 서브 트리의 방문이 끝났기 때문에 노드 A를 방문

노드 A가 마지막 노드로 모든 노드의 방문이 끝났다.

따라서 D->E->B->F->G->C->A

 

 

레벨 순서 순회 (level-order) aka 너비 우선 순회(breadth-first traversal)

• 노드를 낮은 레벨부터 순서대로 순회한다.

가장 낮은 레벨 1 의 노드 A를 방문

그 다음으로 낮은 레벨인 레벨 2의 노드 B 와 C를 차례대로 방문

마지막 레벨 3 의 노드 D, E, F, G를 차례대로 방문

노드 G가 마지막 노드로 모든 노드의 방문이 끝났다.

따라서 A->B->C->D->E->F->G