이 문제에서는 하나의 이진 트리(Binary Tree)가 주어지며, 이를 2차원 평면 위에 출력해야 합니다.
이진 트리는 모든 노드가 최대 두 개의 자식 노드만 가질 수 있는 특수한 트리 구조입니다. 즉, 각 노드는 리프(leaf) 노드이거나 한 개 또는 두 개의 자식 노드를 갖습니다.
예시
아래 그림과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.
주어진 트리를 90도 회전하여 가로 방향으로 출력하면 다음과 같은 결과를 얻습니다.
출력 결과 -
7
4
5
1
3
8
출력 형태의 이해
예시에서 볼 수 있듯이, 트리의 노드들은 2차원 출력 화면에 가로 방향으로 배치되어 나타납니다. 여기서 우리는 트리를 90도 회전시킨 형태로 출력한 것입니다.
회전된 가로 형태의 트리는 다음과 같은 규칙으로 구성됩니다.
트리 자료구조가 가로 방향으로 저장되며, 세부 규칙은 다음과 같습니다.
루트(root)는 시작 줄에서 n번째 아래 줄의 첫 번째 위치에 출력됩니다. 즉, 루트는 n번째 줄의 맨 앞에 위치합니다.
트리의 새로운 레벨(level)은 n+i번째 줄과 n-i번째 줄에 배치되며, 각 줄의 시작점에서 i개의 탭(tab) 공간만큼 떨어진 위치에 출력됩니다.
트리의 가장 오른쪽 리프 노드는 첫 번째 줄에 출력되고, 가장 왼쪽 노드는 마지막 줄에 출력됩니다.
C++ 구현 코드
위 로직을 바탕으로 프로그램을 작성해 보겠습니다.
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define COUNT 10
class Node{
public:
int data;
Node* left, *right;
Node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
void printTree(Node *root, int space){
if (root == NULL)
return;
space += COUNT;
printTree(root->right, space);
for (int i = COUNT; i < space; i++)
cout<<"\t";
cout<<root->data<<"\n";
printTree(root->left, space);
}
int main(){
Node *root = new Node(43);
root->left = new Node(25);
root->right = new Node(67);
root->left->left = new Node(14);
root->left->right = new Node(51);
root->right->left = new Node(26);
root->right->right = new Node(97);
root->left->left->left = new Node(81);
root->left->left->right = new Node(49);
root->left->right->left = new Node(07);
root->left->right->right = new Node(31);
root->right->left->left = new Node(29);
root->right->left->right = new Node(13);
root->right->right->left = new Node(59);
root->right->right->right = new Node(16);
printTree(root, 0);
return 0;
}
실행 결과
16
97
59
67
13
26
29
43
31
51
7
25
49
14
81
이 코드는 역중위 순회(reverse inorder traversal) 방식을 활용합니다. 먼저 오른쪽 서브트리를 재귀적으로 처리하고, 현재 노드를 탭 간격에 맞춰 출력한 뒤 왼쪽 서브트리를 처리함으로써, 트리를 90도 회전한 듯한 2차원 출력을 얻을 수 있습니다. 공백 간격은 COUNT 상수 값을 조정하여 손쉽게 변경할 수 있습니다.