二分木が二分探索木 (BST) であるかどうかをチェックする C 言語で書かれたプログラム-C++-php.cn

二分木が二分探索木 (BST) であるかどうかをチェックする C 言語で書かれたプログラム

バイナリツリーはツリーデータ構造であり、各ノードには 2 つの子ノードがあります。これら 2 つの子ノードを左子ノードおよび右子ノードと呼びます。

二分探索木 (BST) は、左側のサブツリーにルートノードより小さい値を持つノードが含まれ、右側のサブツリーにルートノードより大きい値を持つノードが含まれるツリー構造です。

ここでは、バイナリツリーが BST であるかどうかを確認します。

これを確認するには、バイナリツリー上の BST 条件を確認する必要があります。ルートノードの場合、左側の子ノードの値はルートノードの値より小さく、右側の子ノードの値はルートノードの値より大きくなければなりません。この条件はすべてのノードで満たされる必要があります。ツリー内の子ノードと。

バイナリツリーが BST かどうかを確認するプログラム

#include #include 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

ログイン後にコピー

コードの説明

上記のコードは、二分探索ツリー。 main メソッドはツリーを作成し、isBST() メソッドを呼び出します。このメソッドは、左右の子ノードが二分探索ツリーの規則に従っているかどうかを確認し、isBSTuntil() メソッドを使用して、形成されたサブツリーも二分探索ツリーであるかどうかを確認します。

方法。

以上が二分木が二分探索木 (BST) であるかどうかをチェックする C 言語で書かれたプログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。