개요
코딩테스트에서는 다양한 자료구조와 알고리즘 문제가 출제됩니다. 그 중 트리는 자주 등장하는 자료구조입니다.
트리 구조는 컴퓨터 과학에서 매우 중요한 역할을 하며, 파일 시스템, 데이터베이스 등의 다양한 분야에서 활용됩니다.
이 강좌에서는 자바스크립트를 이용하여 트리를 순회하는 방법에 대해 배워보겠습니다.
트리 구조란?
트리(Tree)란 노드(Node)와 엣지(Edge)로 구성된 비선형 데이터 구조로, 계층적인 관계를 표현하는 데 최적화되어 있습니다.
트리는 루트 노드(root node)와 자식 노드(child node), 부모 노드(parent node), 잎 노드(leaf node) 등의 개념을 가지고 있습니다.
트리의 주요 특징은 다음과 같습니다:
- 트리는 하나의 루트를 가지고 있으며, 자식 노드들이 이 루트로부터 연결됩니다.
- 노드는 0개 이상의 자식 노드를 가질 수 있습니다.
- 리프 노드는 자식이 없는 노드입니다.
트리의 순회 방법
트리를 순회하는 방법에는 여러 가지가 있으며, 가장 일반적으로 사용되는 방식은 다음과 같습니다:
- 전위 순회(Pre-order Traversal)
- 중위 순회(In-order Traversal)
- 후위 순회(Post-order Traversal)
- 레벨 순회(Level-order Traversal)
각각의 순회 방법은 노드를 방문하는 순서가 다릅니다. 각 방법에 대해 자세히 살펴보겠습니다.
전위 순회(Pre-order Traversal)
전위 순회의 방식은 다음과 같습니다:
- 현재 노드를 방문한다.
- 왼쪽 서브트리를 전위 순회한다.
- 오른쪽 서브트리를 전위 순회한다.
예를 들어, 다음과 같은 트리 구조가 있다고 가정해봅시다.
공공
├── 사용자 1
│ ├── 사용자 1.1
│ └── 사용자 1.2
└── 사용자 2
├── 사용자 2.1
└── 사용자 2.2
전위 순회 결과는 “공공, 사용자 1, 사용자 1.1, 사용자 1.2, 사용자 2, 사용자 2.1, 사용자 2.2″입니다.
중위 순회(In-order Traversal)
중위 순회의 방식은 다음과 같습니다:
- 왼쪽 서브트리를 중위 순회한다.
- 현재 노드를 방문한다.
- 오른쪽 서브트리를 중위 순회한다.
예를 들어, 같은 트리 구조에서 중위 순회 결과는 “사용자 1.1, 사용자 1, 사용자 1.2, 공공, 사용자 2.1, 사용자 2, 사용자 2.2″입니다.
후위 순회(Post-order Traversal)
후위 순회의 방식은 다음과 같습니다:
- 왼쪽 서브트리를 후위 순회한다.
- 오른쪽 서브트리를 후위 순회한다.
- 현재 노드를 방문한다.
같은 트리 구조에서 후위 순회 결과는 “사용자 1.1, 사용자 1.2, 사용자 1, 사용자 2.1, 사용자 2.2, 사용자 2, 공공”입니다.
레벨 순회(Level-order Traversal)
레벨 순회의 방식은 다음과 같습니다:
- 루트 노드를 방문한다.
- 현재 노드의 자식 노드들을 방문한다.
- 모든 자식 노드를 방문한 후, 다음 깊이로 이동한다.
같은 트리 구조에서 레벨 순회 결과는 “공공, 사용자 1, 사용자 2, 사용자 1.1, 사용자 1.2, 사용자 2.1, 사용자 2.2″입니다.
프로그래밍 문제: 이진 트리 순회
다음과 같은 이진 트리 구조가 주어졌을 때, 다양한 순회 방법을 이용하여 트리를 순회하는 함수를 작성하시오.
이진 트리는 다음과 같은 노드로 구성됩니다:
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
입력 예시:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
문제
위의 트리를 전위 순회, 중위 순회, 후위 순회, 레벨 순회하는 함수를 각각 작성하시오.
문제 풀이 과정
1. 전위 순회 구현
전위 순회를 수행하기 위해서는 재귀적 접근이 필요합니다. 아래는 이를 구현한 코드입니다:
function preOrderTraversal(node) {
if (node === null) return;
console.log(node.value); // 현재 노드 방문
preOrderTraversal(node.left); // 왼쪽 서브트리 방문
preOrderTraversal(node.right); // 오른쪽 서브트리 방문
}
위 코드는 노드를 순회하면서 현재 노드를 먼저 방문한 후 왼쪽과 오른쪽 노드를 순회합니다.
2. 중위 순회 구현
중위 순회도 재귀적으로 구현합니다. 아래는 중위 순회 코드입니다:
function inOrderTraversal(node) {
if (node === null) return;
inOrderTraversal(node.left); // 왼쪽 서브트리 방문
console.log(node.value); // 현재 노드 방문
inOrderTraversal(node.right); // 오른쪽 서브트리 방문
}
이 코드는 왼쪽 서브트리를 먼저 방문한 후 현재 노드를 방문합니다.
3. 후위 순회 구현
후위 순회 역시 재귀적으로 구현합니다. 다음은 구현된 코드입니다:
function postOrderTraversal(node) {
if (node === null) return;
postOrderTraversal(node.left); // 왼쪽 서브트리 방문
postOrderTraversal(node.right); // 오른쪽 서브트리 방문
console.log(node.value); // 현재 노드 방문
}
후위 순회에서는 두 자식 서브트리를 방문한 후에 현재 노드를 방문합니다.
4. 레벨 순회 구현
레벨 순회는 큐 자료구조를 이용하여 구현합니다. 큐를 사용하면 각 노드를 층층이 방문할 수 있습니다. 다음은 레벨 순회 코드입니다:
function levelOrderTraversal(root) {
if (root === null) return;
const queue = [root]; // 큐 초기화
while (queue.length > 0) {
const current = queue.shift(); // 큐에서 노드 제거
console.log(current.value); // 현재 노드 방문
if (current.left) queue.push(current.left); // 왼쪽 자식 추가
if (current.right) queue.push(current.right); // 오른쪽 자식 추가
}
}
큐를 통해 각 노드를 레벨별로 차례대로 방문할 수 있습니다.
결론
이 강좌에서는 자바스크립트를 활용하여 트리를 순회하는 다양한 방법에 대해 알아보았습니다.
트리 순회는 많은 프로그래밍 문제에서 기본적인 부분을 차지하므로, 충분히 연습하는 것이 중요합니다.
위에서 다룬 전위, 중위, 후위, 레벨 순회 알고리즘을 잘 이해하고 구현하는 것이 코딩테스트에서 좋은 성과를 낼 수 있는 방법입니다.
앞으로도 연습을 통해 다양한 알고리즘 문제를 해결해보세요. 연습과 반복은 최고의 스승입니다!