백준 9934:완전 이진 트리

<queue>를 이용해 완전 이진 트리를 만들 수 있다.

또한, queue를 이용해 완전 이진 트리를 층마다 순회할 수 있다.

 

 

 

 

 

#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int arr[1025], t=0;
typedef struct Node {
int num;
int data;
Node* left = NULL;
Node* right = NULL;
}Node;

void inorder(Node* node) {
if (node == NULL)
return;
inorder(node->left);
node->data = arr[t++];
inorder(node->right);
}

int main(void)
{
int K,i,num,a;
Node* root = new Node();
root->num = 1;
cin >> K;
a = pow(2, K);
for (i = 0; i < a - 1; i++) {
cin >> arr[i];
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {

num = q.front()->num;
if (num >= pow(2,K-1))
break;

if (q.front()->left == NULL) {
Node* node = new Node();
node->num = num * 2;
q.front()->left = node;
q.push(node);
}
else {
Node* node = new Node();
node->num = num * 2 + 1;
q.front()->right = node;
q.push(node);
q.pop();
}
}
inorder(root);
num = 0;
while (!q.empty())
q.pop();
q.push(root);
i = 1;
while (!q.empty()) {
if (q.front()->left != NULL) {
q.push(q.front()->left);
q.push(q.front()->right);
}
printf("%d ", q.front()->data);
num++;
if (num == pow(2, i) - 1)
{
printf("\n");
i++;
}

q.pop();
}


}