[자료구조] 이진 트리의 순회

이진 트리의 순회 종류

• 전위 순회 (PreOrder)
• 중위 순회 (InoOrder)
• 후위 순회 (PostOrder)

 

전위 순회

전위 순회는 뿌리 노드부터 시작하여 아래쪽으로 내려오고 왼쪽 하위 노드를 방문하고 오른쪽 하위 노드를 방문한다.

그림의 전위 순회를 수행하면 뿌리 노드인 1부터 방문하고 왼쪽 하위 노드 2-4-5를 방문한뒤

오른쪽 하위 노드 3-6-7을 방문 하게 된다. 그럼 1-2-4-5-3-6-7 순서가 된다.

 

중위 순회

중위 순회는 왼쪽 하위 노드부터 시작해서 뿌리 노드를 거쳐 오른쪽 하위 노드를 방문하게 된다.

그림의 중위 순회를 수행하면 왼쪽 하위 트리인 4부터 방문하고 뿌리 노드인 2를 방문한뒤

오른쪽 하위 노드 5를 방문하게 된다. 다시 뿌리 노드인 1를 방문하며 뿌리 노드1의 오른쪽 하위 노드의

왼쪽 하위 노드인 6을 방문하고 뿌리 노드의 3을 방문한 뒤 오른쪽 하위 노드 7를 방문한다.

그럼 4-2-5-1-6-3-7이 된다.

후위 순회

후위 순회는 전위 순회와 반대되는 규칙이 적용된다.

후위 순회의 방문 순서는 왼쪽 하위 노드부터 오른쪽 하위 노드 뿌리 노드 순서이다.

그림의 후위 순회를 수행하면 왼쪽 하위 노드인 4를 방문하고 오른쪽 하위 노드인 5를 방문 후 뿌리 노드인 2를 방문한다.

1의 뿌리도 노드로 올라가 오른쪽 하위 노드의 왼쪽 하위 노드 6을 방문하고 오른쪽 하위 노드 7를 방문한뒤

뿌리 노드 3을 방문하고 마지막으로 1의 뿌리 노드를 방문하게 된다.

그럼 4-5-2-6-7-3-1이 된다.