C++で二分木が別の二分木の部分木（サブツリー）であるかを判定する方法

はじめに

二つの二分木が与えられたとき、小さい方の木がもう一方の二分木の部分木（サブツリー）として含まれているかどうかを判定する方法を解説します。

例として、以下のような二つの木を考えてみましょう。

この場合、2番目の木は1番目の木の部分木となっています。

判定アルゴリズムの考え方

この性質を確認するためには、大きい方の木を後順走査（post-order traversal）でたどり、各ノードを根とする部分木が2番目の木と完全に一致するかどうかを順番に調べます。一致する部分木が一つでも見つかれば、2番目の木は1番目の木の部分木であると判定できます。

判定の流れは以下の通りです。

1. 部分木側がNULLであれば、空の木は常に部分木とみなせるためtrueを返します。
2. 元の木側がNULLであれば、それ以上比較できないためfalseを返します。
3. 現在のノードを根とする木と部分木が同一であるかを再帰的に確認します。
4. 一致しない場合は、左部分木と右部分木に対して再帰的に同じ判定を繰り返します。

二つの木が同一かどうかを判定する関数

まず、二つの二分木が構造と値の両方において完全に一致するかを再帰的に判定する関数を用意します。

bool areTwoTreeSame(node *t1, node *t2) {
    if (t1 == NULL && t2 == NULL)
        return true;
    if (t1 == NULL || t2 == NULL)
        return false;
    return (t1->data == t2->data
            && areTwoTreeSame(t1->left, t2->left)
            && areTwoTreeSame(t1->right, t2->right));
}

部分木であるかを判定する関数

次に、元の木を再帰的にたどりながら、各ノードを根とする部分木と比較対象の木が一致するかを確認します。

bool isSubtree(node *tree, node *sub_tree) {
    if (sub_tree == NULL)
        return true;
    if (tree == NULL)
        return false;
    if (areTwoTreeSame(tree, sub_tree))
        return true;
    return isSubtree(tree->left, sub_tree) || isSubtree(tree->right, sub_tree);
}

完全なサンプルコード

ノード生成用の補助関数を含めた、実行可能な完全なコードは以下の通りです。

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

class node {
    public:
    int data;
    node *left, *right;
};

bool areTwoTreeSame(node *t1, node *t2) {
    if (t1 == NULL && t2 == NULL)
        return true;
    if (t1 == NULL || t2 == NULL)
        return false;
    return (t1->data == t2->data
            && areTwoTreeSame(t1->left, t2->left)
            && areTwoTreeSame(t1->right, t2->right));
}

bool isSubtree(node *tree, node *sub_tree) {
    if (sub_tree == NULL)
        return true;
    if (tree == NULL)
        return false;
    if (areTwoTreeSame(tree, sub_tree))
        return true;
    return isSubtree(tree->left, sub_tree) || isSubtree(tree->right, sub_tree);
}

node* getNode(int data) {
    node* newNode = new node();
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    node *real_tree = getNode(26);
    real_tree->right = getNode(3);
    real_tree->right->right = getNode(3);
    real_tree->left = getNode(10);
    real_tree->left->left = getNode(4);
    real_tree->left->left->right = getNode(30);
    real_tree->left->right = getNode(6);

    node *sub_tree = getNode(10);
    sub_tree->right = getNode(6);
    sub_tree->left = getNode(4);
    sub_tree->left->right = getNode(30);

    if (isSubtree(real_tree, sub_tree))
        cout << "Second tree is subtree of the first tree";
    else
        cout << "Second tree is not a subtree of the first tree";
}

実行結果

Second tree is subtree of the first tree

計算量について

このアルゴリズムの時間計算量は、最悪の場合でO(m × n)となります（mは元の木のノード数、nは部分木のノード数）。これは、元の木の各ノードに対して、部分木との一致判定を行うためです。

より効率的にしたい場合は、木を前順走査や中順走査で文字列化し、部分木の走査結果が元の木の走査結果の部分文字列になっているかを確認する方法（O(m + n)、KMP法などを併用）もあります。ただし、値の区切りに番兵（センチネル）文字を入れて誤判定を防ぐ必要がある点に注意してください。

まとめ

二分木の部分木判定は、再帰的な木の同一性チェックと木全体の走査を組み合わせることで実現できます。シンプルな実装ではO(m × n)の計算量になりますが、走査結果の文字列比較を利用することで、より高速な判定も可能です。木構造の再帰処理に慣れるための良い練習問題なので、ぜひ自分でも実装してみてください。