Tree traversal(트리 순회) - 전위 순회, 중위 순회, 후위 순회

Tree traversal

트리 순회
: 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것

1에서 10까지의 정수로 구성된 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리 순회의 한 예시이다. 모든 노드를 순회하는 방법엔 크게 세 가지가 있다.

트리 순회의 종류

트리 순회의 종류에 관계없이 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽이다.

1. 전위 순회

루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 한다.
A->B->D->H->I->E->J->K->C->F->L->M->G->N->O

2. 중위 순회

루트를 가운데에 두고 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.

H->D->I-> B-> J->E->K-> A-> L->F->M-> C-> N->G->O

3. 후위 순회

루트를 가장 마지막에 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.

H->I->D-> J->K->E-> B-> L->M->F-> N->O->G-> C->A