1231. 중위순회

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: SW Expert Academy)

트리 순회 (in-order) 문제.
완전 이진 트리이므로, 배열로 트리 구현이 가능하다.
노드 번호와, 자식 노드의 번호는 예측 가능하므로 입력받지 않고 무시하였다. cin.ignore() 사용.

#include <string>
#include <iostream>
#define MAX_N 100

using namespace std;

int treeSize;
char tree[MAX_N + 1];

char answer[MAX_N + 1];
int answerPointer;

void in_order(int i)
{
	if (i > treeSize)
	{
		return;
	}
	in_order(i << 1);
	answer[answerPointer++] = tree[i];
	in_order((i << 1) + 1);
}

static void solve()
{
	int i;
	cin >> treeSize;
	cin.ignore();
	answer[treeSize] = '\0';
	answerPointer = 0;
	for (i = 1; i <= treeSize; i++)
	{
		cin.ignore(4, ' ');
		cin >> tree[i];
		cin.ignore(16, '\n');
	}
	in_order(1);
}

int main(int argc, char **argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	for (int test_case = 1; test_case <= 10; ++test_case)
	{
		solve();
		printf("#%d %s\n", test_case, answer);
	}
	return 0;
}