C++でN分木（N-aryツリー）を二分木にエンコード・デコードする方法

N分木（N-ary tree）を1本の二分木へ変換（エンコード）することを考えてみましょう。あわせて、エンコード済みの二分木を元のN分木へ復元（デコード）する機能も実装します。

たとえば、次のような入力が与えられたとします。

このとき、出力は次のようになります。

解法のアプローチ：左子・右兄弟表現

この問題は「左子・右兄弟表現（Left-Child Right-Sibling Representation）」と呼ばれる古典的な手法で解くことができます。考え方はシンプルで、N分木の最初の子を二分木の左の子に対応させ、2番目以降の兄弟ノードを順番に右の子として連結していきます。これにより、任意のN分木を構造情報を失うことなく二分木として一意に表現できます。

具体的な手順は以下の通りです。

encode()：N分木 → 二分木への変換

• encode(root) 関数を定義します。
• root が NULL の場合は、NULL を返します。
• root と同じ値を持つ新しい二分木ノード node を作成します。
• root に子が存在する場合は、node の左の子に encode(root.children[0]) の結果を設定します。
• curr を node の左の子とします。
• i = 1 から root の子の数 − 1 までループします。
  • curr の右の子に encode(root.children[i]) の結果を設定します。
  • curr をその右の子へ移動します。
• node を返します。

decode()：二分木 → N分木への復元

• decode(root) 関数を定義します。
• root が存在しない場合は、NULL を返します。
• root と同じ値を持つ新しいN分木ノード node を作成します。
• curr を root の左の子とします。
• curr が NULL でない間、以下を繰り返します。
  • decode(curr) の結果を node の子リストの末尾に追加します。
  • curr をその右の子へ移動します。
• node を返します。

どちらの操作も各ノードを一度だけ訪問するため、計算量はノード数を N として O(N) で抑えられます。

C++ 実装例

より理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};
void inord(TreeNode *root) {
    if (root != NULL) {
        inord(root->left);
        cout << root->val << " ";
        inord(root->right);
    }
}
class Node {
    public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
string n_ary_to_str(Node *root){
    string ret = "";
    if(root){
        ret = ret + to_string(root->val);
        if(root->children.size() > 0){
            ret += "[";
            for(Node* child : root->children){
                ret += n_ary_to_str(child) + ", ";
            }
            ret += "]";
        }
    }
    return ret;
}
class Codec {
public:
    TreeNode* encode(Node* root) {
        if(!root) return NULL;
        TreeNode* node = new TreeNode(root->val);
        if(root->children.size()){
            node->left = encode(root->children[0]);
        }
        TreeNode* curr = node->left;
        for(int i = 1; i < root->children.size(); i++){
            curr->right = encode(root->children[i]);
            curr = curr->right;
        }
        return node;
    }
    Node* decode(TreeNode* root) {
        if(!root) return NULL;
        Node* node = new Node(root->val);
        TreeNode* curr = root->left;
        while(curr){
            node->children.push_back(decode(curr));
            curr = curr->right;
        }
        return node;
    }
};
main() {
    Codec ob;
    Node n5(5), n6(6);
    Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
    Node n2(2), n4(4);
    Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
    n1.children.push_back(&n4);
    cout << "Given Tree: " << n_ary_to_str(&n1) << endl;
    cout << "Serialized Binary Tree: ";
    TreeNode *root = ob.encode(&n1);
    inord(root);
    cout << endl;
    Node *deser = ob.decode(root);
    cout << "Deserialized Tree: " << n_ary_to_str(deser);
}

入力

テスト用に構築するのは、ルート 1 の下に子 [3, 2, 4] がぶら下がり、さらにノード 3 の下に子 [5, 6] がぶら下がるN分木です。

Node n5(5), n6(6);
Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
Node n2(2), n4(4);
Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
n1.children.push_back(&n4);

出力

Given Tree: 1[3[5, 6], 2, 4]
Serialized Binary Tree: 5 6 3 2 4 1
Deserialized Tree: 1[3[5, 6], 2, 4]

エンコード後の二分木を中間順走査（inorder traversal）すると「5 6 3 2 4 1」となり、またデコード結果を文字列化すると元のN分木と完全に一致することが確認できます。このことから、エンコード→デコードの一連の処理で木の構造が損なわれていないことがわかります。