[백준] 9934 - 완전 이진 트리

블로그 시작하고 첫 포스팅...

 

요즘 TRIE에 빠져서 문제를 찾아서 풀어보는중에 좀 쉬운문제를 만났습니다 ㅎㅎ

 

이진트리를 구현하는거라 TRIE라고 하기도 뭐하고, 그냥 이분탐색과 재귀로 할 수 있는 문제지만

 

연습을 위해 트리를 구현해서 풀어보았습니다.

 

그냥 트리를 구현하면서, 각각 깊이에 도착할 때, 선언한 2차원 배열에 차례대로 각 깊이에 대한 숫자를 입력해놀고

 

탐색이 끝나면 출력하면 끝!

 

#include <iostream>
#include <malloc.h>
#include <cmath>
#define MX 1030
using namespace std;
 
typedef struct NODE {
    int d, num;
    int end;
    NODE *L;
    NODE *R;
}node;
 
NODE *makenewnode()
{
    node*tmp = (node*)malloc(sizeof(node));
    tmp->d = 0;
    tmp->end = 0;
    tmp->num = 0;
    tmp->L = NULL;
    tmp->R = NULL;
    return tmp;
}
 
int arr[MX], dab[12][MX];
int K;
 
void insert(node *root, int d, int l, int m, int r)
{
    node*tmp = root;
    if (d == K) { tmp->end = 1; return; }
    tmp->d = d;
    tmp->num = arr[m];
    dab[d][++dab[d][0]] = tmp->num;
    tmp->L = makenewnode();
    tmp->R = makenewnode();
    insert(tmp->L, d + 1, l, (l + m - 1) / 2, m - 1);
    insert(tmp->R, d + 1, m + 1, (m + 1 + r) / 2, r);
}
 
int main(void)
{
    cin >> K;
    for (int i = 0; i < pow(2, K) - 1; i++)
        cin >> arr[i];
    node *root = makenewnode();
    insert(root, 0, 0, (0 + pow(2,K)-2)/2, pow(2, K) - 2);
    for (int i = 0; i < K; i++)
    {
        for (int j = 1; j <= dab[i][0]; j++)
            cout << dab[i][j] << " ";
        cout << endl;
    }
    return 0;
}