Chapter 08. 이진 트리의 순회

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

 

앞서 트리의 노드를 삭제할 때, 그 후손 노드까지 전부 삭제해야 한다고 말했습니다. 그러기 위해서는 삭제하고자 하는 노드의 모든 후손 노드들에 접근하는 일을 수행해야 합니다. 이를 '순회'라고 합니다.

 

이진 트리의 순회가 필요한 이유는 앞서 설명했으니, 이진 트리의 순회 방법을 설명하겠습니다. 이진 트리를 대상으로 하는 대표적인 순회 방법은 다음과 같습니다.

• 전위 순회(Preorder Traversal)      루트 노드를 먼저
• 중위 순회(Inorder Traversal)        루트 노드를 중간에
• 후위 순회(Postorder Traversal)    루트 노드를 마지막에

 

전위 순회란 다음의 순서대로 순회하는 것을 말합니다.

루트 노드를 먼저 순회한 후, 왼쪽 노드에서 오른쪽 노드, 혹은 오른쪽 노드에서 왼쪽 노드 방향으로 순회합니다.

 

중위 순회란 다음의 순서대로 순회하는 것을 말합니다.

오른쪽 노드 - 루트 노드 - 왼쪽 노드 순서로 순회하거나, 그 반대 순서로 순회하면서 루트 노드가 순서상 중간에 위치하는 순회 방법입니다.

 

후위 순회란 다음의 순서대로 순회하는 것을 말합니다.

후위 순회란 왼쪽 노드 - 오른쪽 노드 - 루트 노드 순서대로 순회하거나, 오른쪽 노드 - 왼쪽 노드 - 루트 노드 순서로 순회하여 루트 노드가 순서상 가장 마지막에 위치하는 순회 방법입니다. 제가 앞서 구현했던 DeleteSubTree 함수가 후위 순회 방법을 따르고 있다고 볼 수 있습니다.