트리는 자료구조 중 하나로, 계층적으로 데이터를 저장하는 데 사용됩니다. 본 강좌에서는 트리에 대한 기본 개념을 살펴보고, 자바스크립트를 사용하여 트리 관련 알고리즘 문제를 푸는 방법을 배웁니다.
트리란?
트리는 노드(node)로 구성된 비선형 자료구조입니다. 각 노드는 데이터와 자식 노드의 연결(엣지)을 가집니다. 한 개의 루트 노드(root node)에서 시작하여 그 아래에 여러 자식 노드(child node)가 있을 수 있으며, 각 자식 노드는 다시 자식 노드를 가질 수 있습니다. 트리의 주요 용도는 다음과 같습니다:
- 계층적 데이터 표현 (예: 가계도, 조직도)
- 데이터 검색 (예: 이진 탐색 트리)
- 여러가지 문제 해결 (예: 최단 경로 문제)
트리의 구성 요소
- 루트 노드 (Root Node): 트리의 최상단 노드, 다른 모든 노드의 조상입니다.
- 엣지 (Edge): 노드를 연결하는 선, 부모 노드와 자식 노드를 연결합니다.
- 리프 노드 (Leaf Node): 자식 노드가 없는 노드, 더 이상 확장되지 않는 노드입니다.
- 서브트리 (Subtree): 특정 노드의 자식 노드들로 구성된 트리.
트리 문제: 주어진 이진 트리의 깊이를 계산하라
다음 문제를 해결해봅시다. 주어진 이진 트리의 깊이를 계산하는 함수를 작성하세요.
문제 설명
이진 트리가 주어질 때, 이진 트리의 최대 깊이를 반환하는 함수를 작성하세요. 깊이는 루트 노드에서 가장 깊은 리프 노드까지의 거리로 정의됩니다.
입력 예시
입력:
3
/ \
9 20
/ \
15 7
출력 예시
출력: 3
문제 풀이 방법
이 문제는 깊이 우선 탐색(DFS, Depth First Search) 또는 너비 우선 탐색(BFS, Breadth First Search) 방법을 사용하여 해결할 수 있습니다. 여기서는 DFS를 사용한 방법을 설명하겠습니다.
1. 재귀적 접근
트리의 각 노드에서 왼쪽과 오른쪽 자식 노드를 재귀적으로 방문하여 깊이를 계산할 수 있습니다. 기본 아이디어는 다음과 같습니다:
- 노드가
null이면, 0을 반환합니다. - 현재 노드의 왼쪽 및 오른쪽 자식의 깊이를 계산합니다.
- 왼쪽과 오른쪽 깊이 중 큰 값을 구하고 1을 더하여 부모 노드의 깊이를 반환합니다.
2. 코드 구현
아래는 자바스크립트로 구현한 코드입니다.
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
function maxDepth(root) {
if (root === null) {
return 0;
}
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
3. 코드 설명
- TreeNode: 이 클래스는 트리의 노드를 정의합니다. 각 노드는 값을 가지고 있으며 왼쪽과 오른쪽 자식을 가집니다.
- maxDepth: 이 함수는 재귀적으로 깊이를 계산합니다.
root가null일 경우 0을 반환하고, 그렇지 않으면 왼쪽 및 오른쪽 자식 깊이를 계산하여 큰 값을 반환합니다.
4. 테스트
주어진 예제를 사용하여 `maxDepth` 함수를 테스트해봅시다. 다음 코드를 추가하면 됩니다.
// 이진 트리 생성
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
// 깊이 계산
console.log(maxDepth(root)); // 출력: 3
결론
자바스크립트를 사용하여 트리의 최대 깊이를 계산하는 방법과 알고리즘 문제를 해결하는 과정을 살펴보았습니다. 트리에 대한 이해는 많은 프로그래밍 문제를 해결하는 데 도움이 됩니다. 다양한 트리 문제를 연습하여 트리 구조에 대한 깊은 이해를 쌓아보세요.