특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다. 1에서 10까지의 정수로 구성된 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리 순회의 한 예시이다. 트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 있다.
트리를 순회할 수 있는 세 가지 방법은 전위 순회, 중위 순회, 후위 순회이다. 이 순회 방식과는 논외로, 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽이다.
❤️🔥 전위 순회 (preorder traverse)
전위 순회에서 가장 먼저 방문하는 노드는 루트이다. 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 한다. 즉 부모 노드가 제일 먼저 방문되는 순회 방식이다. 전위 순회는 주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용하게 된다.
❤️🔥 중위 순회 (inorder traverse)
중위 순회는 루트를 가운데에 두고 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다. 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식이다. 중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.
❤️🔥 후위 순회 (postorder traverse)
후위 순회는 루트를 가장 마지막에 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다. 후위 순회는 트리를 삭제할 때 사용한다. 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문이다.
순회 방식을 나누는 이유
앞서 배운 이진 트리 탐색의 경우는 간단한 편이지만 순회 방법은 조금 복잡한 편이다. 일정 조건에 의해 설계된 트리 구조는 자식 노드에 대한 조건이 명확하다면 원하는 값을 쉽게 찾아낼 수 있게 되지만, 트리 구조 전체를 탐색할 때는 이야기가 조금 달라지기 때문이다. 모든 노드를 방문하기 위해서는 일정한 조건이 필요하고, 트리 구조를 유지보수하거나 특정 목적을 위해서도 순회 방법에 대한 정의는 필수적으로 필요한다.
