C++で二分木を見やすい形式で2次元配列に出力する方法

本記事では、二分木（バイナリツリー）を m×n の2次元文字列配列として整形して出力する方法を解説します。出力には以下のルールが適用されます。

• 行数 m は、与えられた二分木の高さと一致すること。
• 列数 n は、必ず奇数になること。
• ルートノードの値は、最初の行のちょうど中央に配置する。ルートノードが存在する行と列によって、残りの領域は「左下」と「右下」の2つの部分に分割される。左側の部分木は左下の領域へ、右側の部分木は右下の領域へそれぞれ出力する。左右の領域は同じサイズとする。片方の部分木が存在しない場合でも、何も出力はしないものの、もう一方の部分木と同じサイズの領域は確保しておく必要がある。ただし、両方の部分木が存在しない場合は、領域を確保する必要はない。
• 未使用のスペースにはすべて空文字列（"")を格納すること。
• 各部分木についても、同じルールに従って表示を行うこと。

たとえば、以下のような入力木が与えられたとします。

ルート「1」、その子に「2」「3」、さらに「2」の子として右側だけに「4」を持つ構造です。

このとき、期待される出力は次のようになります。

解決のアプローチ

この問題を解くためには、以下の手順に従います。

• まず fill() という補助メソッドを定義します。このメソッドは、ノード・行列 ret・現在のレベル lvl・範囲 l と r を引数として受け取ります。
• ノードが null の場合は処理を終了して return します。
• ret[lvl][(l + r) / 2] にノードの値を文字列として格納します。
• 左部分木に対して fill(node->left, ret, lvl + 1, l, (l + r) / 2) を呼び出します。
• 右部分木に対して fill(node->right, ret, lvl + 1, (l + r + 1) / 2, r) を呼び出します。
• メインの処理では以下を行います。
• 変数 h に木の高さを求めて代入します。
• leaves = 2^h − 1 を計算します。
• h × leaves のサイズの行列を作成し、すべての要素を空文字列で初期化します。
• fill(root, ret, 0, 0, leaves) を呼び出して値を配置します。
• 最後に ret を返します。

C++での実装例

より理解を深めるために、実際の実装を見てみましょう。

#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, , , , ]]

この実装では、まず getHeight() 関数で木の高さを再帰的に求め、その高さから必要な列数（2^h − 1）を計算しています。fill() 関数は再帰的に呼び出され、各区間の中点にノードの値を配置していくことで、ルールに沿った整形表示を実現しています。