【C++】二分木を括弧付きの文字列に変換する方法

この問題では、二分木が与えられます。求められているのは、C++で二分木を括弧付きの文字列に変換するプログラムを作成することです。

二分木の各ノードの値は整数であり、先行順巡回（プレオーダー走査）の順序でプログラムに入力されます。生成する文字列には整数と括弧「()」のみを含めることができ、さらに最適化されている必要があります。つまり、不要な空の括弧ペアはすべて取り除かなければなりません。

二分木とは、各ノードが最大2つの子ノードを持つという特別な条件を満たす木構造のことです。

二分木の例

先行順巡回：[4, 1, 8, 3, 9, 2, 5]

具体例を見ながら問題を理解しましょう。

入力

preorder: [4, 1, 8, 3, 9, 2, 5]

出力

4(1(8(3)))(9(2)(5))

解説

Root -> 4()() -> 4(1()())(9) -> 4(1(8()())())(9) -> 4(1(8(3)())())(9) -> 4(1(8(3)())())(9(2)(5))

すべての空の括弧を取り除くと、次のようになります。

4(1(8(3)))(9(2)(5))

それでは、この問題を解いていきましょう。基本的な方針は、二分木を先行順で巡回しながら、必要な箇所にだけ括弧を配置することです。同時に、余分な括弧のペアも取り除く必要があります。この処理を実現するために、括弧を配置する関数を再帰的に呼び出す手法を用います。

具体的には、まずノードの値を出力し、そのノードの子に対して再帰関数を呼び出します。この処理を、子を持たないノード（葉ノード）に到達するまで繰り返します。

ノードの子に対して関数を呼び出す際、必ず以下の4つのケースのいずれかに該当します。

ケース1：左右両方の子ノードが存在する場合

両方の子に対して括弧を配置し、それぞれの値を括弧内に出力します。さらに下位の部分木が存在すれば、そこに対しても再帰的に処理を行います。

例：上記の例におけるルートノード「4」は両方の子を持つため、「4(1)(9)」となります。

ケース2：左の子のみが存在する場合

左の子を括弧内に出力します。右の子は存在しないため、右側の括弧は省略されます。左の子の部分木が存在すれば、そこに対してのみ再帰的に処理を行います。

例：上記の例における値「1」のノードは左の子のみを持つため、「4(1(8()()))(9)」となります。

ケース3：右の子のみが存在する場合

左の子に対応する位置に空の括弧を出力します。これは、右の子が左の子より後ろの位置にあることを正しく表現するために必要です。その後、右の子の値を出力し、その部分木が存在すれば再帰的に処理を行います。

ケース4：子を持たない場合（葉ノード）

括弧は一切付けず、ノードの値のみを出力します。

例：上記の例における値「5」のノードは子を持たないため、「4(1(8(3)))(9(2)(5()()))」のように一時的に表現され、最終的な最適化後に「4(1(8(3)))(9(2)(5))」となります。

二分木を括弧付き文字列に変換するプログラム

// 二分木を括弧付き文字列に変換するプログラム

サンプルコード

#include <iostream>
using namespace std;
struct Node {
   int data;
   Node *left, *right;
};
Node* insertNode(int data){
   Node* node = (Node*)malloc(sizeof(Node));
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
void ConveryBinaryTreeToString(Node* root, string& str){
   if (root == NULL)
   return;
   str.push_back(root->data + '0');
   if (!root->left && !root->right)
   return;
   str.push_back('(');
   ConveryBinaryTreeToString(root->left, str);
   str.push_back(')');
   if (root->right) {
      str.push_back('(');
      ConveryBinaryTreeToString(root->right, str);
      str.push_back(')');
   }
}
int main() {
   struct Node* root = insertNode(4);
   root->left = insertNode(1);
   root->right = insertNode(9);
   root->left->left = insertNode(8);
   root->left->left->left = insertNode(3);
   root->right->left = insertNode(2);
   root->right->right = insertNode(5);
   string binaryTreeString = "";
   ConveryBinaryTreeToString(root, binaryTreeString);
   cout<<"The string with preorder traversal of binary tree with brackets is: "<<binaryTreeString;
}

実行結果

The string with preorder traversal of binary tree with brackets is: 4(1(8(3)))(9(2)(5))