코딩 테스트 대비: 이진 트리 순회하기(C#)

안녕하세요, GameLabMaster입니다! 오늘의 코딩 테스트 대비 포스팅에서는 이진 트리를 순회하는 문제를 다루겠습니다. 이진 트리는 최대 두 개의 자식 노드를 가질 수 있는 트리 자료구조입니다. 이진 트리 순회는 트리의 모든 노드를 방문하는 방법입니다. 주요 순회 방식에는 전위 순회(preorder), 중위 순회(inorder) 및 후위 순회(postorder)가 있습니다.

먼저 이진 트리의 노드 클래스를 정의해보겠습니다.

 

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

 

이제 이진 트리 순회 메서드를 작성해보겠습니다.

 

public class BinaryTreeTraversal {
    public void Preorder(TreeNode node) {
        if (node == null) return;
        Console.Write(node.val + " ");
        Preorder(node.left);
        Preorder(node.right);
    }

    public void Inorder(TreeNode node) {
        if (node == null) return;
        Inorder(node.left);
        Console.Write(node.val + " ");
        Inorder(node.right);
    }

    public void Postorder(TreeNode node) {
        if (node == null) return;
        Postorder(node.left);
        Postorder(node.right);
        Console.Write(node.val + " ");
    }
}

 

위 코드에서는 이진 트리를 전위, 중위, 후위 순회하는 메서드를 정의하였습니다.

이제 주어진 이진 트리를 생성하고 순회 메서드를 호출하여 결과를 출력해보겠습니다.

 

public static void Main(string[] args) {
    TreeNode 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);

    BinaryTreeTraversal traversal = new BinaryTreeTraversal();

    Console.WriteLine("전위 순회: ");
    traversal.Preorder(root);
    Console.WriteLine();

    Console.WriteLine("중위 순회: ");
    traversal.Inorder(root);
    Console.WriteLine();

    Console.WriteLine("후위 순회: ");
    traversal.Postorder(root);
    Console.WriteLine();
}

 

위 예제에서는 주어진 이진 트리를 생성하고 BinaryTreeTraversal 클래스의 순회 메서드를 호출하여 전위, 중위, 후위 순회 결과를 출력하였습니다. 실행 결과, 주어진 이진 트리를 올바르게 순회한 결과가 출력됩니다.

 

이상으로 오늘의 코딩 테스트 대비 포스팅을 마치겠습니다. 이진 트리 순회는 알고리즘의 기본이자 코딩 테스트에서 자주 출제되는 문제 유형 중 하나이므로, 꼭 숙지하시기 바랍니다. 다음 포스팅에서도 더 유용한 정보를 드릴 것입니다. 그럼, 즐거운 코딩 되세요!