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

これらのルールに基づいて、m *n2D文字列配列に二分木を表示する必要があるとします-

• 行番号mは、指定された二分木の高さと同じである必要があります。
• 列番号nは常に奇数である必要があります。
• ルートノードの値は、配置できる最初の行の真ん中に配置する必要があります。ルートノードが存在する列と行は、残りのスペースを2つの部分に分割します。これらは左下部分と右下部分です。左下の部分に左のサブツリーを印刷し、右下の部分に右のサブツリーを印刷する必要があります。ここで、左下部分と右下部分は同じサイズである必要があります。一方のサブツリーがnoneで、もう一方がnoneでない場合でも、noneサブツリーには何も出力する必要はありませんが、他のサブツリーと同じ大きさのスペースを残す必要があります。これで、2つのサブツリーがない場合は、両方のサブツリー用にスペースを残す必要はありません。
• 未使用の各スペースには空の文字列を含める必要があります。
• 同じルールに従ってサブツリーを表示します。

したがって、入力ツリーが次のような場合-

その場合、出力は-

これを解決するには、次の手順に従います-

• fill（）と呼ばれる別のメソッドを定義します。これにより、ノード、行列ret、lvl、l、およびrの値が取得されます
• ノードがnullの場合は、戻ります
• ret [lvl、（l + r）/ 2]：=文字列としてのノードval
• fill（ノードの左側、ret、lvl + 1、l、（l + r）/ 2）
• fill（ノードの右側、ret、lvl + 1、（l + r + 1）/ 2、r）
• メインの方法から次のようにします-
• h：=木の高さ
• 葉=2^ h – 1
• 次数hxの葉の行列を作成し、これを空白の文字列で埋めます
• fill（root、ret、0、0、leaves）
• return ret

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      } else {
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
         temp->right = new TreeNode(val);
      else
         temp->right = new TreeNode(0);
         return;
      } else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   int getHeight(TreeNode* node){
      if(!node)return 0;
      return 1 + max(getHeight(node->left), getHeight(node->right));
   }
   void fill(TreeNode* node, vector<vector<string>>& ret, int lvl, int l, int r){
      if(!node || node->val == 0)return;
      ret[lvl][(l + r) / 2] = to_string(node->val);
      fill(node->left, ret, lvl + 1, l, (l + r) / 2);
      fill(node->right, ret, lvl + 1, (l + r + 1) / 2, r);
   }
   vector<vector<string>> printTree(TreeNode* root) {
      int h = getHeight(root);
      int leaves = (1 << h) - 1;
      vector < vector <string> > ret(h, vector <string>(leaves, ""));
      fill(root, ret, 0, 0, leaves);
      return ret;
   }
};
main(){
   vector<int> v = {1,2,3,NULL,4};
   Solution ob;
   TreeNode *root = make_tree(v);
   print_vector(ob.printTree(root));
}

入力

[1,2,3,null,4]

出力

[[, , , 1, , , , ],
[, 2, , , , 3, , ],
[, , 4, , , , , ],]