入力した二分木が別の二分木の部分木（サブツリー）かどうかを判定するC++プログラム

二分木とは

二分木（バイナリツリー）とは、各ノードが最大2つの子ノードを持つことのできる木構造のデータ構造です。子ノードはそれぞれ「左の子」と「右の子」として定義されます。

本記事では、ある二分木 S が、別の二分木 T の部分木（サブツリー）として含まれているかどうかを判定する C++ プログラムを紹介します。

アルゴリズム

判定処理は、次の2つの再帰関数によって実現します。

• identical()： 引数として渡された2つのノード r1・r2 を根とする木同士が、完全に一致しているかどうかを再帰的に調べます。
• Subtree()： 大きな木 T の各ノードを順にたどりながら、その位置から始まる部分木が S と一致するかどうかを identical() を使って確認します。

処理の流れは以下の擬似コードの通りです。

開始
   関数 identical()：
       ノード r1 と r2 を引数として受け取る
       もし r1 と r2 が両方 NULL ならば
           true を返す
       もし r1 または r2 の片方だけが NULL ならば
           false を返す
       （r1->d と r2->d が等しく、かつ
         Identical(r1->l, r2->l) が真、かつ
         Identical(r1->r, r2->r) が真）を返す

   関数 Subtree(node *T, node *S)：
       もし S == NULL ならば
           true を返す
       もし T == NULL ならば
           false を返す
       もし Identical(T, S) が真ならば
           true を返す
       Subtree(T->l, S) または Subtree(T->r, S) を返す
終了

アルゴリズムのポイント

• S が空（NULL）の場合、空の木はどんな木の部分木にもなり得るため true を返します。
• T が空で S が空でない場合、これ以上探索できるノードがないため false を返します。
• 現在のノードを根とする木が S と一致しなければ、左の子・右の子それぞれに対して再帰的に探索を続けます。

サンプルコード

#include <iostream>
using namespace std;

// 二分木のノードを表す構造体
struct n {
   int d;         // ノードが保持する値
   struct n* l;   // 左の子へのポインタ
   struct n* r;   // 右の子へのポインタ
};

// 2つの木が完全に一致しているかを再帰的に判定する
bool Identical(struct n * r1, struct n *r2) {
   if (r1 == NULL && r2 == NULL)
      return true;   // 両方とも空なら一致とみなす
   if (r1 == NULL || r2 == NULL)
      return false;  // 片方だけ空なら一致しない
   return (r1->d == r2->d && Identical(r1->l, r2->l) && Identical(r1->r, r2->r));
}

// S が T の部分木かどうかを判定する
bool Subtree(struct n *T, struct n *S) {
   if (S == NULL)
      return true;   // 空の木は常に部分木となる
   if (T == NULL)
      return false;  // 探索できるノードが残っていない
   if (Identical(T, S))
      return true;   // 現在のノードを根とする木が S と一致
   return Subtree(T->l, S) || Subtree(T->r, S);  // 左右の子で再帰的に探索
}

// 値 d を持つ新しいノードを生成する補助関数
struct n* newN(int d) {
   struct n* nod =
   (struct n*)malloc(sizeof(struct n));
   nod->d = d;
   nod->l = NULL;
   nod->r = NULL;
   return(nod);
}

int main() {
   // 木 T の構築
   struct n *T = newN(24);
   T->r = newN(2);
   T->r->r = newN(5);
   T->l = newN(7);
   T->l->l = newN(3);
   T->l->l->r = newN(40);
   T->l->r = newN(6);

   // 判定対象の木 S の構築
   struct n *S = newN(20);
   S->r = newN(5);
   S->l = newN(3);
   S->l->r = newN(50);

   if (Subtree(T, S))
      cout<<"given tree is subtree of Binary tree"<<"\n";
   else
      cout<<"given tree is not subtree of Binary tree"<<"\n";

   // 木 T1 の構築
   struct n *T1 = newN(30);
   T1->r = newN(20);
   T1->r->r = newN(19);
   T1->l = newN(17);
   T1->l->l = newN(4);
   T1->l->l->r = newN(40);
   T1->l->r = newN(15);

   // 判定対象の木 S1 の構築
   struct n *S1 = newN(17);
   S1->r = newN(15);
   S1->l = newN(4);
   S1->l->r = newN(40);

   if (Subtree(T1, S1))
      cout<<"given tree is subtree of Binary tree";
   else
      cout<<"given tree is not subtree of Binary tree";

   getchar();
   return 0;
}

実行結果

given tree is not subtree of Binary tree
given tree is subtree of Binary tree

結果の解説

1つ目の例では、木 S の根の値は 20 ですが、木 T には値 20 のノードが存在しないため、「部分木ではない」と判定されます。

2つ目の例では、木 S1（根の値 17）が、木 T1 の左側の部分木（17 → 左に 4、右に 15、さらに 4 の右に 40）と完全に一致するため、「部分木である」と判定されます。

計算量について

このアルゴリズムは、木 T の各ノードに対して identical() による照合を行うため、最悪計算量は O(m × n) となります（m は木 T のノード数、n は木 S のノード数）。より効率的な手法としては、両木の先行順・中間順トラバーサルの結果を文字列化し、部分文字列として一致するかを比較する方法などが知られています。