C++で三項演算式を二分木に変換する方法

このチュートリアルでは、三項演算式を二分木に変換するプログラムについて詳しく解説します。

ここでは「a?b:c」のような形式で書かれた三項演算式が入力として与えられます。私たちのタスクは、この式に含まれる条件分岐（選択肢）の構造をもとに、対応する二分木を構築することです。

アプローチの考え方

三項演算式は「条件 ? 真の場合の値 : 偽の場合の値」という構造を持っています。これを木として表現すると、次のように解釈できます。

• 条件や値となる各文字がノードに対応します。
• 「?」の直後に続く式は、現在のノードの左部分木になります。
• 「:」の直後に続く式は、現在のノードの右部分木になります。

この性質を利用すると、文字列を先頭から走査しながら再帰的に処理することで、自然に二分木を組み立てることができます。

実装例

#include<bits/stdc++.h>
using namespace std;

// 木のノード構造体
struct Node {
    char data;
    Node *left, *right;
};

// 新しいノードを作成する
Node *newNode(char Data){
    Node *new_node = new Node;
    new_node->data = Data;
    new_node->left = new_node->right = NULL;
    return new_node;
}

// 三項演算式を二分木へ変換する
Node *convertExpression(string str, int & i){
    // 現在の文字をノードとして格納
    Node * root = newNode(str[i]);
    // 最後の文字なら基底ケースとして返す
    if(i == str.length()-1)
        return root;
    i++;
    // 次の文字が「?」なら、
    // 現在のノードに部分木が存在する
    if(str[i] == '?'){
        // 「?」を読み飛ばす
        i++;
        root->left = convertExpression(str, i);
        // 「:」を読み飛ばす
        i++;
        root->right = convertExpression(str, i);
        return root;
    }
    else return root;
}

// 二分木を先行順で表示する
void display_tree(Node *root){
    if (!root)
        return ;
    cout << root->data << " ";
    display_tree(root->left);
    display_tree(root->right);
}

int main(){
    string expression = "a?b?c:d:e";
    int i = 0;
    Node *root = convertExpression(expression, i);
    display_tree(root);
    return 0;
}

出力結果

a b c d e

コードの解説

convertExpression 関数の動作

この関数は参照渡しのインデックス i を使い、文字列を1文字ずつ進めながら再帰的に木を構築します。

1. 現在位置の文字で新しいノードを作成します。
2. それが最後の文字であれば、そのノードをそのまま返します（基底ケース）。
3. 次の文字が「?」であれば、「?」と「:」をスキップしたうえで、左側の式と右側の式をそれぞれ再帰的に変換し、左右の子として接続します。

ネストした三項演算への対応

サンプルの式「a?b?c:d:e」は、次のような入れ子構造になっています。

• a が条件で、真の場合は「b?c:d」、偽の場合は「e」

このため、生成される二分木は以下の構造になります。

        a
       / \
      b   e
     / \
    c   d

先行順（前順）走査で表示しているため、出力は「a b c d e」となります。

計算量

各文字を一度だけ走査するため、時間計算量は O(n)、ノード数は式の長さに比例するため空間計算量も O(n) となります。