C++で2次元でバイナリツリーを印刷する

この問題では、二分木が与えられ、それを2次元平面で印刷する必要があります。

二分木は、すべてのノードに最大2つの子ノードがある特別なツリーです。したがって、すべてのノードはリーフノードであるか、1つまたは2つの子ノードを持っています。

例

トピックをよりよく理解するために例を見てみましょう-

出力-

      7
   4
5
      1
   3
      8

例で見たように、ツリーのノードは2D出力画面に水平に印刷されます。

ここでは、ツリーを90°反転しました。

新しい水平ツリーが何で構成されているか見てみましょう。

• ツリーデータ構造は、以下を含む水平方向に保存されます

  • 開始線からn行下の水平方向のビューの1番目の位置にあるルート。つまり、ルートは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