라이브스마트

개요

코딩테스트에서는 다양한 자료구조와 알고리즘 문제가 출제됩니다. 그 중 트리는 자주 등장하는 자료구조입니다.
트리 구조는 컴퓨터 과학에서 매우 중요한 역할을 하며, 파일 시스템, 데이터베이스 등의 다양한 분야에서 활용됩니다.
이 강좌에서는 자바스크립트를 이용하여 트리를 순회하는 방법에 대해 배워보겠습니다.

트리 구조란?

트리(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. 현재 노드를 방문한다.
2. 왼쪽 서브트리를 전위 순회한다.
3. 오른쪽 서브트리를 전위 순회한다.

예를 들어, 다음과 같은 트리 구조가 있다고 가정해봅시다.

                공공
                ├── 사용자 1
                │   ├── 사용자 1.1
                │   └── 사용자 1.2
                └── 사용자 2
                    ├── 사용자 2.1
                    └── 사용자 2.2
                

전위 순회 결과는 “공공, 사용자 1, 사용자 1.1, 사용자 1.2, 사용자 2, 사용자 2.1, 사용자 2.2″입니다.

중위 순회(In-order Traversal)

중위 순회의 방식은 다음과 같습니다:

1. 왼쪽 서브트리를 중위 순회한다.
2. 현재 노드를 방문한다.
3. 오른쪽 서브트리를 중위 순회한다.

예를 들어, 같은 트리 구조에서 중위 순회 결과는 “사용자 1.1, 사용자 1, 사용자 1.2, 공공, 사용자 2.1, 사용자 2, 사용자 2.2″입니다.

후위 순회(Post-order Traversal)

후위 순회의 방식은 다음과 같습니다:

1. 왼쪽 서브트리를 후위 순회한다.
2. 오른쪽 서브트리를 후위 순회한다.
3. 현재 노드를 방문한다.

같은 트리 구조에서 후위 순회 결과는 “사용자 1.1, 사용자 1.2, 사용자 1, 사용자 2.1, 사용자 2.2, 사용자 2, 공공”입니다.

레벨 순회(Level-order Traversal)

레벨 순회의 방식은 다음과 같습니다:

1. 루트 노드를 방문한다.
2. 현재 노드의 자식 노드들을 방문한다.
3. 모든 자식 노드를 방문한 후, 다음 깊이로 이동한다.

같은 트리 구조에서 레벨 순회 결과는 “공공, 사용자 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); // 오른쪽 자식 추가
                }
            }
            

큐를 통해 각 노드를 레벨별로 차례대로 방문할 수 있습니다.

결론

이 강좌에서는 자바스크립트를 활용하여 트리를 순회하는 다양한 방법에 대해 알아보았습니다.
트리 순회는 많은 프로그래밍 문제에서 기본적인 부분을 차지하므로, 충분히 연습하는 것이 중요합니다.
위에서 다룬 전위, 중위, 후위, 레벨 순회 알고리즘을 잘 이해하고 구현하는 것이 코딩테스트에서 좋은 성과를 낼 수 있는 방법입니다.

앞으로도 연습을 통해 다양한 알고리즘 문제를 해결해보세요. 연습과 반복은 최고의 스승입니다!