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

Question

バイナリツリーがバイナリ検索ツリーであるかどうかを示す以下のメソッドを記述しようとしましたか？私はテストケースの半分だけを渡します。私は間違って何をしていますか？

boolean checkBST(Node root) { 

    boolean leftflag = false; 
    boolean rightflag = false; 

    Node l = root.left; 
    Node r = root.right; 

    if(l!=null) { 
     if(root.data <= l.data) { 
      leftflag = false; 
     } 
     else { 
      leftflag = true; 
      checkBST(l); 
     } 
    } 
    if(leftflag == false) 
     return false; 
    if(r != null) { 
     if(root.data >= r.data) { 
      rightflag = false; 
     } 
     else { 
      rightflag = true; 
      checkBST(r); 
     } 
    } 
    if(rightflag == false) 
     return false; 

    return true; 
} 

Answer 1

プログラムが間違って誤って返される場合があります。

あなたが深い、次のように行くの3つの支店を持つツリーを持っている想像してみて：放置すれば

  7 
     / \ 
     3  8 
     \ /\ 
     4 6 9 

あなたのプログラムは、7（ルート）で起動し、偽（leftflagとrightflag）の2つのブール値を作成し、チェックがnullであります。そうではありません。次に、左のデータが< =右のデータであるかどうかをチェックします。そうです。

したがって、新しいルートノードを左にして関数を再帰的に呼び出す（この例では3つ）。再度、falseの初期値で2つのブール値を作成し、左のノードがヌルかどうかを確認します。それは！だから、もしあなたが戻ってくる前に、あなたの他の人に直接行く。私はどうだろう何

// The condition here is respected, there is no left node 
// But the tree is an actual search tree, you didn't check right node 
// Before returning false. 
if(leftflag == false) 
    return false 

は、あなたの左のノードがnullの場合でもそう、プログラムがまだ右のノードをチェック

if(l != null) 
{ 
    if(root.data<=l.data) 
    { 
     return false; 
    } 
    else 
    { 
     // recursive call here 
    } 
} 

if(r != null) 
{ 
    // Same as left node here 
} 

です。私は少し助けてくれることを願っています！

Answer 2

主な間違いは、再帰呼び出しの戻り値を無視することです。例：

else { 
     leftflag = true; 
     checkBST(l); 
    } 
} 
if(leftflag == false) 
    return false; 

checkBST（l）がfalseを返す場合は無視します。値を保存することは決してありません。したがって、後続の左フラッグのチェックでは、サブツリーの適性を完全に知らないことになります。意味的には、ルーチンはすべてのサブツリーがBSTであるとみなします。フラグを設定し、サブツリーに再帰させますが、フラグを変更しないでください。このロジックを試してみてください：

else 
    leftflag = checkBST(l) 

ここで、ブール式に慣れてください。たとえば、ブール値に対してブール値をテストするのはちょっと無駄です。代わりに

if (flag == false) 

のほんの直接チェック：ヌルポインタをチェック

if (!flag) 

は、ほとんどの言語に似ている：あなたがしている場合

if (l) 

最後に、あなたのフラグを初期化しません最初のアクションと同じ値に設定するだけです。

今、あなたのコードは次のように表示されることがあります。

boolean leftflag = false; 
    boolean rightflag = false; 

    if(l) { 
     if(root.data > l.data) { 
      leftflag = checkBST(l); 
     } 
    } 
    if(!leftflag) 
     return false; 

    if(r) { 
     if(root.data < r.data) { 
      rightflag = checkBST(r); 
     } 
    } 
    if(rightflag == false) 
     return false; 

    return true; 
} 

今では、論理の流れに従うことを少し簡単です。あなたの基本ケースには基本的な障害があります。ヌルツリーはですが、falseを返します。あなたは、ロジック短絡およびブール式の詳細については気にしている場合

は今、あなたはより多くのこのような何かにあなたのルーチンを減らすことができます

return 
    (!root.left ||   // Is left subtree a BST? 
     (root.data > root.left.data && 
     checkBST(root.left))) 
    && 
    (!root.right ||   // Is right subtree a BST? 
     (root.data > root.right.data && 
     checkBST(root.right)))