バイナリツリーがバイナリ検索ツリーであるかどうかをチェックする機能

Question

誰かが私になぜこれが機能しないのか教えてもらえますか？ これは私にとって正しいようです

誰かにこれを調べてください。

私は間違いを見つけられません。

bool checkbst(node* root,int minValue,int maxValue) 
{ 
    if(root==NULL) 
    { 

     return true; 
    } 
    else if(((root->data)>(minValue))&& 
      ((root->data)>(maxValue))&& 
      (checkbst(root->left,minValue,root->data))&& 
      (checkbst(root->right,root->data,maxValue))) 
    { 

     return true; 
    } 
    else 
    { 

    return false; 
    } 
} 

void isbst(node* root) 
{ 
    if(checkbst(root,INT_MIN,INT_MAX)) 
    { 
     cout<<"the tree is bst"; 
    } 
} 

Answer 1

あなたは、それはおそらく

((root->data)>(minValue))&&((root->data)<(maxValue)) 

（記号 "未満" に注意）である必要がありながら、あなたは

((root->data)>(minValue))&&((root->data)>(maxValue)) 

をチェックしている、checkbstのタイプミスを持っています。

Answer 2

あなたのコードは、キーが範囲内にあることを確認しますが、子がルートに対してbst条件を満たすかどうかを確認しません。つまり、左側のサブツリーのキーはルートよりも小さく、右側のキーはより大きくなければなりません。サブツリーを含む比較を実行する前に、子がnullでないかどうかを確認する必要があります。

このバージョンでは動作するはずです：小さなミスコードがあるが、それを行うには良い方法があり、あなたの私がチェックしている

bool checkbst(node* root, int minValue,int maxValue) 
{ 
    if (root == nullptr) 
    return true; 

    if (not (root->data >= minValue && root->data <= maxvalue)) 
    return false; 

    if (root->left) 
    { 
     if (root->data < root->left->data) 
     if (not checkbst(root->left, minValue, maxValue)) 
      return false; 
     else 
     return false; 
    } 

    // here the left subtree has been checked 
    if (root->right) 
    { 
     if (root->data < root->right->data) 
     return checkbst(root->right, minValue, maxValue); 
     else 
     return false; 
    } 

    return true; // everything is ok 
} 

Answer 3

。指定されたツリーを順番に走査して配列に格納し、配列内の要素がソートされているかどうかを確認するだけです。要素がソートされている場合はバイナリ検索ツリー、それ以外の場合はバイナリツリー（バイナリツリーとバイナリ検索ツリーの基本的な違いです）になります。

は

((root->data)>(maxValue)) 

は、タイプミスが良く目立つように

((root->data)<(maxValue))