3-2. Tree Traversal

Tree의 노드들을 탐색하는 데에는 여러 가지 방법이 있다.

기본적으로 노드를 방문하는 순서에 따라 preorder, postorder, inorder traversal이 있고,

이 외에도 level-order traversal, Euler tour traversal 등 여러 가지 순회 방식이 있다.

하나씩 순회 과정을 살펴보자.

 

Preorder Traversal (전위 순회)

전위 순회는 현재 노드를 먼저 탐색하기 때문에 붙여진 이름이다.

따라서 1.현재 노드 2. 왼쪽 child 노드부터 차례대로 순으로 방문하게 된다.

 

실제 위 트리를 예시로 전위 순회를 실행해보자.

먼저 root 노드인 0번 노드를 방문하고, 그 다음으로 left child인 1번 노드를 방문하게 된다.

1번 노드를 방문했다면, 다음으로 또 1번 노드의 left child인 3번 노드를 방문한다.

이런 식으로 모두 방문하게 되면 0-1-3-6-7-2-4-5-8 순으로 방문하게 된다.

 

Postorder Traversal (후위 순회)

후위 순회는 전위 순회와 반대로 1.왼쪽 child 노드부터 차례대로 2. 현재 노드 순으로 방문하게 된다.

 

마찬가지로 위 트리를 예시로 후위 순회를 실행해보자.

root 노드인 0번 노드를 방문하기 전 child 노드가 있으므로 먼저 왼쪽 child 노드인 1번으로 이동한다.

1번도 마찬가지로 child 노드가 있으므로 3번 노드로, 3번에서도 child 노드인 6번으로 이동하게 된다.

6번 노드는 child 노드가 없으므로 방문하고 parent로 돌아가 다음 child인 7번 노드로 이동한다.

7번 노드도 child 노드가 없으므로 방문하고 parent로 돌아가면 3번 노드도 child를 모두 방문했으니 방문하게 된다.

이런 식으로 child 노드를 모두 방문한 뒤 현재 노드를 방문하면 6-7-3-1-4-8-5-2-0 순으로 방문하게 된다.

 

Inorder Traversal (중위 순회)

중위 순회는 1.왼쪽 child 노드 2.현재 노드 3.오른쪽 child 노드 순으로 방문하게 된다.

중위 순회는 child 노드 사이에 방문하기 때문에 non-binary tree에서는 명확한 정의가 없다.

따라서 non-binary tree에서는 원하는 순서에 방문하도록 정의하여 사용하면 된다.

 

같은 트리로 예를 들어 중위 순회를 통해 방문해보자.

먼저 root 노드인 0번 노드에서는 왼쪽 child 노드가 있으니 해당 노드인 1번 노드로 이동한다.

마찬가지로 1번에서 왼쪽 child인 3번, 3번에서 왼쪽 child인 6번 노드로 이동한다.

6번 노드는 왼쪽 child가 없으므로 방문하고 오른쪽 child도 없으니 parent로 다시 이동한다.

이제 3번 노드에서 왼쪽 child는 방문했으니 현재 노드인 3번 노드를 방문하고 오른쪽 child 노드로 이동한다.

이와 같은 순서로 방문하면 6-3-7-1-0-4-2-5-8 순으로 방문하게 된다.

 

Euler Tour Traversal (오일러 투어 순회)

오일러 투어 순회는 전위, 중위, 후위 순회를 모두 합친 형태이다.

1.현재 노드 2.왼쪽 child 노드 3.현재 노드 4.오른쪽 child 노드 5.현재 노드 순으로 방문하게 된다.

따라서 internal 노드의 경우 (child 수+1)번씩 방문하고 leaf 노드는 1번씩 방문하게 된다.

 

위 트리를 오일러 투어 순회를 통해 방문해보자.

먼저 root 노드인 0번 노드를 방문하고 왼쪽 child인 1번, 1번의 왼쪽 child인 3번, 3번의 왼쪽 child 6번 순으로 방문한다.

6번은 child가 없으므로 parent인 3번 노드를 방문한 뒤, 3번의 오른쪽 child인 7번 노드를 방문한다.

7번도 child가 없으므로 다시 parent인 3번을 방문한 뒤, 3번은 child를 모두 방문했으니 parent인 1번 노드를 방문한다.

이렇게 child 노드를 방문하기 전, 중, 후에 1번씩 방문하면 0-1-3-6-3-7-3-1-0-2-4-2-5-8-5-2-0 순으로 방문하게 된다.

 

Level-order Traversal (레벨 순서 순회)

레벨 순서 순회는 낮은 레벨의 노드부터 순서대로 방문하게 된다.

 

root 노드가 가장 레벨이 낮으므로 먼저 방문한다.

그 다음으로 레벨이 낮은 root의 child 노드 1번, 2번 노드를 방문한다.

이런 식으로 낮은 레벨부터 차례대로 방문하면 0-1-2-3-4-5-6-7-8 순으로 방문하게 된다.