C++で二分木を2次元平面上に出力する方法

この記事では、与えられた二分木（バイナリツリー）を2次元平面上に整形して出力する方法について解説します。

二分木とは、すべてのノードが最大2つの子ノードを持つ特殊な木構造です。つまり、各ノードは葉ノードであるか、1つまたは2つの子ノードを持つことになります。

出力イメージ

まず、具体例を見ながら内容を理解していきましょう。

      7
    4
5
      1
    3
      8

この出力例からわかるように、木の各ノードは2次元の出力画面上に水平方向へ展開されて表示されます。

ポイントは、木構造を90度回転させて表示しているという点です。通常、木は上から下へ成長しますが、ここでは右から左へと成長する形で描画しています。

水平表示のルール

回転後の水平方向の木構造は、以下のようなルールで構成されています。

• 木のデータ構造は水平方向に格納・表示されます。

  • ルートは開始行からn行下の位置、つまりn行目の先頭に配置されます。

  • 木の新しいレベル（階層）は、n+i行目とn-i行目に配置され、行頭からi個分のタブスペースだけ離れた位置に出力されます。

  • 木の最も右側の葉ノードが最初の行に出力され、最も左側のノードが最後の行に出力されます。

C++での実装例

それでは、このロジックに基づいたC++プログラムを作成してみましょう。

#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

アルゴリズムのポイント

このプログラムの動作を簡単に整理すると、以下のようになります。

1. 逆インオーダー走査（右→根→左）：printTree関数では、まず右部分木を処理し、次に現在のノードを出力、最後に左部分木を処理します。これにより、木が90度回転した形で表示されます。

2. space変数によるインデント管理：再帰が深くなるごとにspaceにCOUNT（10）を加算することで、階層が深いノードほど多くのタブで字下げされ、視覚的に木構造が表現されます。

3. 計算量：各ノードを一度ずつ訪問するため、時間計算量はO(n)、再帰の深さは木の高さに依存します。

この手法を使えば、デバッグ時や学習時に二分木の構造を直感的に確認できるため、非常に便利です。