트리 순회 (Tree traversal)

트리순회란? 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것이다.
예를 들어 1에서 10까지의 정수로 구성된 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리 순회의 한 예시입니다.

트리 순회 3 가지 방법

트리 구조는 계층적 구조라는 특별한 특징 때문에, 모든 노드를 순회하는 방법으로 전위 순회, 중위 순회, 후위 순회가 있다.
이 순회 방식과는 논외로, 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽입니다.

전위 순회 (preorder traverse)

가장 먼저 방문할 노드는 루트입니다. 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 합니다.

중위 순회 (inorder traverse)

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

후위 순회 (postorder traverse)

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

출처 코드스테이츠