자료구조. 순회(전위 중위 후위)

트리의 순회

트리의 순회에는 3가지 방법이 존재한다.

1. 전위 순회

F->B->A->D->C->E->G->I->H

살펴보자면 Root 노드부터 왼쪽->오른쪽으로 탐색을 시작한다.

F를 방문 한 뒤, 왼쪽 자식인 B를 방문한다.

B의 왼쪽 자식인 A를 방문한 뒤, A는 자식이 없으므로 B의 오른쪽 자식 D를 방문한다.

D의 왼쪽 자식인 C를 방문 한 뒤, C는 자식이 없으므로 E로 넘어간다. E도 자식이 없으므로 

Root의 왼쪽 자식을 탐색한다.

2. 중위 순회

A->B->C->D->E->F->G->H->I

왼쪽 -> Root -> 오른쪽으로 탐색을 진행한다.

Root인 F의 왼쪽 자식인 B에는 또 왼쪽 자식이 존재하므로 A를 방문한다. 

A는 자식이 없으므로 A의 부모인 B를 방문. B의 오른쪽 자식인 D에는 왼쪽 자식 C가 존재한다.

C는 자식이 없으므로 C를 방문한 뒤, 부모인 D를 방문, 다음 E를 방문한다.

-반복

3. 후위 순회

A->C->E->D->B->H->I->G->F

왼쪽 -> 오른쪽 -> Root로 탐색을 진행한다.

귀찮다. 안적을래.