[알고리즘 문제 풀기] 트리 순회(1991)

1. 문제 풀이 아이디어

• 트리를 배열에 저장한 후, 재귀 함수를 사용하여 전위 순회, 중위 순회, 후위 순회를 수행하여 문제를 해결한다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder();

using (StreamReader sr = new(Console.OpenStandardInput()))
using (StreamWriter sw = new(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    int[,] arr = new int[26, 2];
    for (int i = 0; i < n; i++)
    {
        string[] split = sr.ReadLine().Split();
        int p = split[0][0] - 'A';
        for (int j = 1; j < 3; j++)
        {
            if (split[j][0] == '.')
            {
                arr[p, j - 1] = -1;
            }
            else
            {
                int c = split[j][0] - 'A';
                arr[p, j - 1] = c;
            }
        }
    }
    for (int i = 0; i < 3; i++)
    {
        Solve(0, i);
        sb.AppendLine();
    }
    sw.Write(sb);

    void Solve(int n,int opt)
    {
        if (n == -1)
            return;
        if(opt==0)
            sb.Append((char)(n + 'A'));
        Solve(arr[n, 0], opt);
        if(opt==1)
            sb.Append((char)(n + 'A'));
        Solve(arr[n, 1], opt);
        if (opt == 2)
            sb.Append((char)(n + 'A'));
    }
}

3. 정리

• int[,] arr = new int[26, 2];를 사용하여 각 노드의 왼쪽 자식과 오른쪽 자식을 저장할 2차원 배열을 생성한다.

• for 루프를 사용하여 입력을 받아 트리를 배열에 저장한다.
• 부모 노드를 인덱스로 사용하고, 왼쪽과 오른쪽 자식 노드를 저장한다.
• 자식이 없는 경우 -1로 저장한다.

• for (int i = 0; i < 3; i++)를 사용하여 전위 순회, 중위 순회, 후위 순회를 수행한다.
• Solve(0, i);를 호출하여 루트 노드부터 탐색을 시작한다.

• Solve(int n, int opt) 함수에서 opt 값을 기준으로 다른 순회 방식을 적용한다.
• opt == 0이면 전위 순회(루트 → 왼쪽 → 오른쪽)를 수행한다.
• opt == 1이면 중위 순회(왼쪽 → 루트 → 오른쪽)를 수행한다.
• opt == 2이면 후위 순회(왼쪽 → 오른쪽 → 루트)를 수행한다.