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

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

二分探索木 (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

コードの説明

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

方法。

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