バイナリ ツリーはツリー データ構造であり、各ノードには 2 つの子ノードがあります。これら 2 つの子ノードを左子ノードおよび右子ノードと呼びます。
二分探索木 (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
コードの説明
上記のコードは、二分探索ツリー。 main メソッドはツリーを作成し、isBST() メソッドを呼び出します。このメソッドは、左右の子ノードが二分探索ツリーの規則に従っているかどうかを確認し、isBSTuntil() メソッドを使用して、形成されたサブツリーも二分探索ツリーであるかどうかを確認します。
方法。以上が二分木が二分探索木 (BST) であるかどうかをチェックする C 言語で書かれたプログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。