코딩 테스트 대비: 이진 트리 순회 알고리즘 (C#)

안녕하세요, GameLabMaster입니다! 오늘의 포스팅에서는 이진 트리의 순회 알고리즘에 대해 알아보고 C#으로 구현하는 방법을 살펴보겠습니다. 트리 순회 알고리즘은 트리의 모든 노드를 방문하는 방법으로, 주로 전위(preorder), 중위(inorder), 후위(postorder) 순회 방법이 사용됩니다.

 

문제
주어진 이진 트리의 전위, 중위, 후위 순회 결과를 출력하는 프로그램을 작성하세요.

 

입력

• 이진 트리를 구성하는 노드들

출력

• 전위 순회 결과
• 중위 순회 결과
• 후위 순회 결과

풀이

이진 트리의 순회는 재귀 함수를 활용해 구현할 수 있습니다. 각 순회 방법은 노드 방문의 순서만 다르며, 방문 순서에 따라 전위, 중위, 후위 순회가 결정됩니다.

다음은 C#으로 작성한 이진 트리 순회 알고리즘의 예시 코드입니다.

using System;

public class Node
{
    public int data;
    public Node left, right;

    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}

public class BinaryTree
{
    public Node root;

    void PrintPreorder(Node node)
    {
        if (node == null)
            return;

        Console.Write(node.data + " ");
        PrintPreorder(node.left);
        PrintPreorder(node.right);
    }

    void PrintInorder(Node node)
    {
        if (node == null)
            return;

        PrintInorder(node.left);
        Console.Write(node.data + " ");
        PrintInorder(node.right);
    }

    void PrintPostorder(Node node)
    {
        if (node == null)
            return;

        PrintPostorder(node.left);
        PrintPostorder(node.right);
        Console.Write(node.data + " ");
    }

    public void PrintPreorder() { PrintPreorder(root); }
    public void PrintInorder() { PrintInorder(root); }
    public void PrintPostorder() { PrintPostorder(root); }
}

 

이 코드는 간단한 이진 트리를 구현하고, 각각의 순회 알고리즘을 구현한 것입니다. 이진 트리의 각 노드를 순회하며 출력하는 방법을 살펴보았습니다.

 

다음 포스팅에서는 더 다양한 트리와 관련된 문제와 풀이를 다루어 보도록 하겠습니다. 트리 구조를 이해하고 이를 활용한 알고리즘 문제 해결 능력은 코딩 테스트에서 매우 중요하기 때문에, 트리와 관련된 문제를 많이 풀어보는 것을 추천드립니다.

 

각 순회 방법에 대해 조금 더 상세히 살펴보겠습니다.

 

전위 순회 (Preorder Traversal) : 노드 방문 → 왼쪽 하위 트리 방문 → 오른쪽 하위 트리 방문
중위 순회 (Inorder Traversal) : 왼쪽 하위 트리 방문 → 노드 방문 → 오른쪽 하위 트리 방문
후위 순회 (Postorder Traversal) : 왼쪽 하위 트리 방문 → 오른쪽 하위 트리 방문 → 노드 방문

각 순회 방법은 노드 방문의 순서만 다르다는 것을 기억하시면 됩니다.

 

이렇게 트리 순회 알고리즘을 이해하고 적용하면, 트리 구조를 사용하는 다양한 문제를 효율적으로 해결할 수 있습니다. 다음 시간에는 트리의 응용 문제를 풀이해 보겠습니다. 트리 구조에 대한 이해가 부족하다면, 트리와 관련된 기본 개념을 다시 한 번 살펴보는 것도 좋습니다.