二分木がBST（二分探索木）かどうかを判定するC++プログラム

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

BST（二分探索木）は、左部分木に含まれるすべてのノードの値が根より小さく、右部分木に含まれるすべてのノードの値が根より大きくなるという性質を持つ木構造です。

この記事では、与えられた二分木がBSTであるかどうかを判定するプログラムを紹介します。

二分木がBSTかどうかを判定する考え方

判定を行うには、木に含まれるすべてのノードに対してBSTの条件を満たしているかを確認します。具体的には、各ノードについて「左の子の値はそのノードの値より小さいこと」「右の子の値はそのノードの値より大きいこと」をチェックします。

ただし、注意すべき点として、親ノードと直接の子同士の比較だけでは不十分です。例えば、左部分木の中のノードが、根から離れた位置にある別の祖先ノードの条件に違反するケースもあり得るため、各ノードが取りうる値の範囲（最小値・最大値）を引数として渡しながら再帰的に検証する方法が有効です。

二分木がBSTかどうかを判定するプログラム

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
class node {
    public:
        int data;
    node* left;
    node* right;
    node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int isBSTUtil(node* node, int min, int max);
int isBST(node* node) {
    return(isBSTUtil(node, INT_MIN, INT_MAX));
}
int isBSTUtil(node* node, int min, int max) {
    if (node==NULL)
        return 1;
    if (node->data < min || node->data > max)
        return 0;
    return
        isBSTUtil(node->left, min, node->data-1) && isBSTUtil(node->right, node->data+1, max);
}
int main() {
    node *root = new node(8);
    root->left = new node(3);
    root->right = new node(10);
    root->left->left = new node(1);
    root->left->right = new node(6);
    if(isBST(root))
        cout<<"The given tree is a BST";
    else
        cout<<"The given tree is Not a BST";
    return 0;
}

実行結果

The given tree is a BST

コードの解説

上記のコードは、二分木がBSTであるかどうかを判定します。

main関数では、まずサンプルとなる二分木を構築し、isBST() 関数を呼び出します。isBST() 関数は、初期状態として許容される値の範囲を INT_MIN〜INT_MAX に設定した上で、isBSTUtil() 関数を呼び出します。

isBSTUtil() 関数は再帰的に動作し、以下の手順で判定を行います。

• ノードがNULLの場合は、そこまでの経路がBSTの条件を満たしているため1（真）を返します。
• 現在のノードの値が許容範囲 [min, max] の外にある場合は0（偽）を返します。
• 左部分木には「min〜ノードの値-1」、右部分木には「ノードの値+1〜max」という範囲を渡して再帰的に判定し、両方が真であれば1を返します。

このように、各ノードに許容される値の範囲を伝播させながら再帰的にチェックすることで、木全体がBSTの条件を満たしているかを正確に判定できます。計算量は各ノードを一度ずつ訪問するため O(n)、ここで n はノードの総数です。