C++で先行順走査（プレオーダー）から完全k分木を構築する方法

配列 arr[] には、k分木（k-ary tree）の先行順走査（プレオーダートラバーサル）の結果が順番に格納されています。この記事の目標は、その配列をもとに同じk分木を構築し、後行順走査（ポストオーダートラバーサル）の結果を出力することです。

ここでいう完全k分木（full k-ary tree）とは、各ノードが「0個」または「k個」の子ノードを持つ、すなわち最大でもk個の子しか持たない木のことです。

例

入力

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 2

出力

2つの子を持つ完全k分木を先行順走査から構築すると、下図のようになります。

説明

子の数が k=2 である木の先行順走査（整数値の配列）が与えられています。構築された木の後行順走査の結果は「3 6 1 2 1 7 5 2」となります。これは「まず左側の部分木のすべてのノードを訪問し、次に右側の部分木のすべてのノードを訪問し、最後にルートノードを訪問する」という規則に従って構築・出力されたものです。

入力

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 3

出力

3つの子を持つ完全k分木を先行順走査から構築すると、下図のようになります。

説明

子の数が k=3 である木の先行順走査が与えられた場合も同様です。構築された木の後行順走査の結果は「3 6 1 2 1 7 5 2」となり、先ほどと同じ規則に基づいて出力されます。

プログラムで使用するアプローチ

このアプローチでは、まず配列の最初の要素をルートノードとして、与えられた配列からk分木を構築します。ある部分木が空であれば、それ以降の兄弟部分木も空になります。各子部分木に対して再帰的に処理を呼び出し、ノード同士をリンクしていきます。

後行順走査では、すべての子部分木を先に処理してから、ノード自身の値を出力します。具体的な手順は以下の通りです。

• 各子部分木に対して postorder(子ノード) を再帰的に呼び出す
• すべての子を処理した後で root->data を出力する
• arr[] を先行順走査の結果を含む入力配列として受け取る
• k は子の数を表す変数として受け取る
• 開始インデックスを count = 0 とする
• Tree_Node* node = create_tree(arr, size, children, count) を呼び出して木を構築する
• 関数 new_Node(int data) は木の新しいノードを生成します
• 関数 create_tree(int arr[], int N, int k, int height, int& count) は配列 arr[] からk分木を生成します
• ノード数 N が 0 以下の場合は NULL を返します（木は構築できません）
• newNode = new_Node(arr[count]) として、arr[] の現在の要素から新しいノードを初期化します
• (newNode == NULL) が真であれば、メモリ確保に失敗しているため木を構築できません
• for ループで i = 0 から i < k まで繰り返し、各子ノードを処理します
• (count < N - 1 && height > 1) が成り立つ場合は count をインクリメントして次のインデックスに進み、newNode->root.push_back(create_tree(arr, N, k, height - 1, count)) によって子ノードを木に追加します
• そうでない場合は newNode->root.push_back(NULL); を実行して空の子を追加し、その枝を終了します
• 最後に、生成したノードへのポインタを返します
• 関数 create_tree(int* arr, int N, int k, int count) は、木の高さを計算して構築を行うラッパー関数です
• height = (int)ceil(log((double)N * (k - 1) + 1) / log((double)k)); によって木の高さを求めます
• return 文内で create_tree(arr, N, k, height, count) を呼び出し、計算された高さの木を構築します
• 関数 postorder_traversal(Tree_Node* node, int k) は、node をルートとするk分木の後行順走査を出力します
• node が NULL の場合は何もしません
• for ループで i = 0 から i < k まで走査し、postorder_traversal(node->root[i], k) を再帰的に呼び出します
• for ループの後に node->address を出力します

C++による実装例

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

struct Tree_Node {
    int address;
    vector<Tree_Node*> root;
};

Tree_Node* new_Node(int data){
    Tree_Node* newNode = new Tree_Node;
    newNode->address = data;
    return newNode;
}

Tree_Node* create_tree(int arr[], int N, int k, int height, int& count){
    if(N <= 0){
        return NULL;
    }
    Tree_Node* newNode = new_Node(arr[count]);
    if (newNode == NULL){
        cout << "Code Dumped";
        return NULL;
    }
    for(int i = 0; i < k; i++){
        if (count < N - 1 && height > 1){
            count++;
            newNode->root.push_back(create_tree(arr, N, k, height - 1, count));
        } else {
            newNode->root.push_back(NULL);
        }
    }
    return newNode;
}

Tree_Node* create_tree(int* arr, int N, int k, int count){
    int height = (int)ceil(log((double)N * (k - 1) + 1) / log((double)k));
    return create_tree(arr, N, k, height, count);
}

void postorder_traversal(Tree_Node* node, int k){
    if (node == NULL){
        return;
    }
    for(int i = 0; i < k; i++){
        postorder_traversal(node->root[i], k);
    }
    cout << node->address << " ";
}

int main(){
    int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 };
    int size = 8;
    int children = 2;
    int count = 0;
    Tree_Node* node = create_tree(arr, size, children, count);
    cout << "先行順走査から構築した完全k分木の後行順走査: ";
    postorder_traversal(node, children);
    return 0;
}

出力

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

先行順走査から構築した完全k分木の後行順走査: 3 6 1 2 1 7 5 2