C++で二分木に含まれる二分探索木（BST）の数を数える方法

入力として二分木が与えられ、その内部に部分木として存在する二分探索木（BST：Binary Search Tree）の個数を求めるのが本記事の目的です。

二分探索木とは、次の性質を満たす二分木のことです。

• 左の子ノードの値は、親ノード（根）の値より小さい
• 右の子ノードの値は、親ノード（根）の値より大きい

入力例1

入力された値から構築される二分木は以下の通りです。

出力

Count the Number of Binary Search Trees present in a Binary Tree are: 2

解説

整数値の配列から二分木を構築し、その中に二分探索木が存在するかどうかを確認します。すべての葉ノードはそれ自体が BST とみなせるため、この例では葉ノードが2つ存在し、それ以外に BST を構成する部分木はないため、合計カウントは 2 となります。

入力例2

入力された値から構築される二分木は以下の通りです。

出力

Count the Number of Binary Search Trees present in a Binary Tree are: 6

解説

この例では、葉ノードが4つあり、さらに BST の条件を満たす部分木が2つ存在します。したがって、合計カウントは 6 となります。

アルゴリズムのアプローチ

本プログラムでは、以下の方針で問題を解きます。ノード N について、その左部分木内の最大値が N より小さく、右部分木内の最小値が N より大きいことを確認します。この条件が成立すれば、その部分木は BST です。二分木をボトムアップ（下から上へ）の順序で走査しながらこの条件を判定し、BST の数をカウントしていきます。

• 各ノードの情報（node_data）には、「その部分木に含まれる BST の数」「部分木内の最大値」「部分木内の最小値」「その部分木が BST であるかどうかの真偽値」を持たせます。
• 関数 BST_present(struct tree_node* parent) は、parent を根とする二分木内に存在する BST の数を返します。
• parent が NULL の場合は { 0, min, max, true } を返します（min は INT_MIN、max は INT_MAX）。
• 左の子と右の子がどちらも NULL（葉ノード）の場合は { 1, parent->data, parent->data, true } を返します。
• node_data Left = BST_present(parent->left); および node_data Right = BST_present(parent->right); として、左右の部分木の結果を取得します。
• ノード n1 に対し、n1.lowest = min(parent->data, min(Left.lowest, Right.lowest)) として部分木全体の最小値を設定します。
• 同様に、n1.highest = max(parent->data, max(Left.highest, Right.highest)) として部分木全体の最大値を設定します。
• Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest が true となる場合、その部分木は BST なので n1.check = true とし、n1.total_bst = 1 + Left.total_bst + Right.total_bst として BST 数を1増やします。
• 条件を満たさない場合は n1.check = false とし、n1.total_bst = Left.total_bst + Right.total_bst として子の結果のみを引き継ぎます。
• 最後に n1 を返します。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
struct tree_node{
    struct tree_node* left;
    struct tree_node* right;
    int data;
    tree_node(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
struct node_data{
    int total_bst;
    int highest, lowest;
    bool check;
};
node_data BST_present(struct tree_node* parent){
    if(parent == NULL){
        int max = INT_MAX;
        int min = INT_MIN;
        return { 0, min, max, true };
    }
    if(parent->left == NULL){
        if(parent->right == NULL){
            return { 1, parent->data, parent->data, true };
        }
    }
    node_data Left = BST_present(parent->left);
    node_data Right = BST_present(parent->right);
    node_data n1;
    n1.lowest = min(parent->data, (min(Left.lowest, Right.lowest)));
    n1.highest = max(parent->data, (max(Left.highest, Right.highest)));
    if(Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest){
        n1.check = true;
        n1.total_bst = 1 + Left.total_bst + Right.total_bst;
    } else{
        n1.check = false;
        n1.total_bst = Left.total_bst + Right.total_bst;
    }
    return n1;
}
int main(){
    struct tree_node* root = new tree_node(3);
    root->left = new tree_node(7);
    root->right = new tree_node(4);
    root->left->left = new tree_node(5);
    root->right->right = new tree_node(1);
    root->left->left->left = new tree_node(10);
    cout<<"Count the Number of Binary Search Trees present in a Binary Tree are: "<<BST_present(root).total_bst;
    return 0;
}

出力

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

Count the Number of Binary Search Trees present in a Binary Tree are: 2