C++의 2차원 이진 트리 인쇄

<시간/>

이 문제에서는 이진 트리가 주어지고 이를 2차원 평면으로 인쇄해야 합니다.

이진 트리는 모든 노드에 최대 두 개의 자식 노드가 있는 특수 트리입니다. 따라서 모든 노드는 리프 노드이거나 하나 또는 두 개의 하위 노드가 있습니다.

예

C++의 2차원 이진 트리 인쇄

주제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -

C++의 2차원 이진 트리 인쇄

출력 -

이제 예제에서 보았듯이 트리의 노드는 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;
}

출력