[C++] SWEA 1231번: 중위순회

🔗 문제

SW Expert Academy

SW Expert Academy

 

🖍 풀이

입력을 받을 때 .. 자식 0~2개수에 따라 어떻게 파싱해야하나 고민을 하느라 1시간 이상 풀었다.

 

개인적으로 이 문제부터 먼저 풀길 권한다. 

https://viin.tistory.com/121?category=986375 

[C++] SWEA 1233번: 사칙연산 유효성 검사

 

 

 

이건 문제에 힌트가 있다. 주어질 트리는 완전 이진 트리다!

정점 번호에 따라 자식의 개수를 알 수 있는 완전 이진 트리의 특성을 사용하면 된다!

 

완전 이진 트리란?

리프 노드를 제외하고 모든 트리가 양 옆이 채워져 있다는 뜻이다.

• 트리 길이/2 == 정점
  • 자식 1명
• 트리 길이/2 < 정점
  • 자식 없다
• 트리 길이/2 > 정점
  • 자식 2

 

완전 이진트리는 배열로 풀어도 되지만 오랜만에 노드랑 이진 트리.

그리고 중위, 후위, 전위순위에 대해서 짚고 갈겸해서 아래처럼 풀었다.

 

 

💾  소스

#include <iostream>

class Node
{
public:
    Node()
    :left(nullptr), right(nullptr), data('\\0')
    {}
    
    Node* left;
    Node* right;
    char data;
};

void preorder(Node* cur)
{
    if(cur == nullptr) return;

    std::cout << cur->data;
    preorder(cur->left);
    preorder(cur->right);
}

void inorder(Node* cur)
{
    if(cur == nullptr) return;
    
    inorder(cur->left);
    std::cout << cur->data;
    inorder(cur->right);
}

void posorder(Node* cur)
{
    if(cur == nullptr) return;
    
    posorder(cur->left);
    posorder(cur->right);
    std::cout << cur->data;
}

int main()
{
    int T = 10;
    for(int tc=1 ; tc<=T; ++tc)
    {
        Node arr[101];
        int idx, left, right;
        char data;
        int N;

        std::cin >> N;
        for(int i=0; i<N; ++i)
        {
            std::cin >> idx >> data;
            arr[idx].data = data;
 
            if((double)N/2 > idx)
            {
                std::cin >> left >> right;
                arr[idx].left = &arr[left];
                arr[idx].right = &arr[right];
            }
            else if(N/2 == idx)
            {
                std::cin >> left;
                arr[idx].left = &arr[left];
            }
        }

        std::cout << '#' << tc << ' ';
        inorder(&arr[1]); // 루트는 정점 1부터니까
        std::cout<< '\\n';
    }

	return 0;
}