이 문제에서는 이진 트리가 주어지고 이를 2차원 평면으로 인쇄해야 합니다.
이진 트리는 모든 노드에 최대 두 개의 자식 노드가 있는 특수 트리입니다. 따라서 모든 노드는 리프 노드이거나 하나 또는 두 개의 하위 노드가 있습니다.
예
주제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -
출력 -
7 4 5 1 3 8
이제 예제에서 보았듯이 트리의 노드는 2차원 출력 화면에서 가로로 인쇄됩니다.
여기에서 나무를 90o 뒤집었습니다.
새로운 수평 트리가 무엇으로 구성되어 있는지 살펴보겠습니다.
-
트리 데이터 구조는 다음을 포함하는 수평 방식으로 저장됩니다.
-
수평 보기에서 시작 라인 아래 n줄의 첫 번째 위치에 있는 루트. 즉, 루트는 n번째 줄의 시작 부분에 있습니다.
-
트리의 새 레벨은 n+i 및 n-i 행에 있습니다. 그리고 i에서 줄의 시작 부분에서 공백을 탭합니다.
-
그리고 트리의 맨 오른쪽 리프 노드가 첫 번째 줄에 인쇄됩니다. 반면 트리의 가장 왼쪽 노드는 마지막 줄에 인쇄됩니다.
-
예시
이 논리를 기반으로 프로그램을 만들어 봅시다 -
#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