【C++】中順走査（Inorder Traversal）の配列から特殊な二分木を構築する方法

問題概要

二分木の中順走査（インオーダー走査）の結果が格納された整数型配列 arr[] が与えられます。この配列をもとに「特殊な二分木」を構築することが本記事の目的です。ここでいう特殊な二分木とは、根ノードの値が、その左の子ノードおよび右の子ノードの値よりも常に大きいという条件を満たす二分木を指します。

入力例と出力例

入力1

int arr[] = {10, 20, 28, 40, 32, 31, 30}

上記の中順走査から構築される特殊な二分木は以下の通りです。

解説

整数値の配列、すなわち木の中順走査が与えられています。これをもとに構築される特殊な木は「10, 20, 28, 40, 32, 31, 30」となります。

入力2

int arr[] = {10, 20, 25, 28, 40, 32, 31, 30, 35}

上記の中順走査から構築される特殊な二分木は以下の通りです。

解説

同様に、9つの整数値からなる中順走査が与えられています。構築される特殊な木は「10, 20, 25, 28, 40, 32, 31, 30, 35」となります。

アルゴリズムの考え方

このアプローチでは、配列内の最大要素を根ノードとして採用することで、特殊な二分木を構築します。最大要素より左側にある要素は左部分木に、右側にある要素は右部分木に属します。この処理を再帰的に繰り返すことで、木全体を組み上げていきます。

手順の詳細

• 中順走査を格納した配列 arr[] を入力として受け取ります。
• 関数 new_node(int data) は、左右の子ポインタが NULL の新規ノードを生成します。
• 関数 total(int arr[], int first, int last) は、指定範囲内で最大値となる要素のインデックスを返します。
• 最初に highest = arr[first]、lowest = first と初期化します。
• first + 1 から last まで走査し、arr[i] が highest より大きい場合は、そのインデックスを lowest に記録して highest を更新します。
• ループ終了後、lowest には最大要素のインデックスが格納されています。
• 関数 create_tree(int arr[], int first, int last) は、arr[] から再帰的に特殊な二分木を構築します。
• first > last の場合は木を構成できないため、NULL を返します。
• temp = total(arr, first, last) により、範囲内の最大値のインデックスを取得します。
• arr[temp] をデータとするノードを生成し、根ノードへのポインタ parent がそれを指すようにします。
• first == last の場合、木は単一ノードのみとなるため、parent を返します。
• 再帰的に parent->left = create_tree(arr, first, temp - 1); を計算します。
• 続いて parent->right = create_tree(arr, temp + 1, last); を設定します。
• 最後に parent を返します。
• 関数 Inorder_traversal(tree_node* node) は、生成された木の中順走査結果を出力します。
• ノードが NULL であれば何もしません。そうでなければ、まず Inorder_traversal(node->left) で左部分木を出力します。
• 次に現在のノードの値を出力します。
• 最後に Inorder_traversal(node->right) で右部分木を出力します。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
int total(int arr[], int first, int last);
class tree_node{
    public:
    int data;
    tree_node* left;
    tree_node* right;
};
tree_node* new_node(int data);
tree_node* create_tree (int arr[], int first, int last){
    if(first > last){
        return NULL;
    }
    int temp = total(arr, first, last);
    tree_node *parent = new_node(arr[temp]);
    if(first == last){
        return parent;
    }
    parent->left = create_tree(arr, first, temp - 1);
    parent->right = create_tree(arr, temp + 1, last);
    return parent;
}
int total(int arr[], int first, int last){
    int highest = arr[first];
    int lowest = first;
    for(int i = first + 1; i <= last; i++){
        if(arr[i] > highest){
            highest = arr[i];
            lowest = i;
        }
    }
    return lowest;
}
tree_node* new_node (int data){
    tree_node* newNode = new tree_node();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
void Inorder_traversal(tree_node* node){
    if (node == NULL){
        return;
    }
    Inorder_traversal(node->left);
    cout<<node->data<<" ";
    Inorder_traversal (node->right);
}
int main(){
    int arr[] = {10, 20, 28, 40, 32, 31, 30};
    int size = sizeof(arr)/sizeof(arr[0]);
    tree_node *root = create_tree(arr, 0, size - 1);
    cout<<"与えられた中順走査から構築した特殊な二分木: "<<"\n";
    Inorder_traversal(root);
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

与えられた中順走査から構築した特殊な二分木:
10, 20, 28, 40, 32, 31, 30

まとめ

本記事では、二分木の中順走査の配列から「根ノードの値が常に子ノードより大きい」という条件を満たす特殊な二分木を構築する方法を解説しました。区間内の最大値を根とする再帰的な分割アプローチにより、直感的に木を構築できます。なお、各再帰呼び出しで線形探索を行うため計算量は最悪 O(n²) となりますが、セグメント木などを併用すれば O(n log n) への改善も可能です。