木が渡されたかどうかを調べるためにrubyにコードを書いて、バイナリ検索ツリーにしました。ちょうど私が正しい道にいるかどうかをチェックしたい。木がBSTであるかどうかを確認する
def checkBST(t)
return false if t==nil
if t.left!=nil && t.left>t
return false
end
if t.right!=nil && t.right<t
return false
end
if checkBST(t.left) && checkBST(t.right)
return true
end
end
私は最初の行ごとにそれを説明してみましょう： -
1 def checkBST(t)
2 return false if t==nil
3 if t.left!=nil && t.left>t
4 return false
5 end
6 if t.right!=nil && t.right<t
7 return false
8 end
9 if checkBST(t.left) && checkBST(t.right)
10 return true
11 end
12 end
2行目は、 - tがNULLの場合にtrueを返します。
3行目と6行目 - 直系の子をチェックしていますが、子供がBSTプロパティを満たしていて、そのグランド・チャイルドを満たしていない場合はどうなりますか？自分自身を試して、あなたは私が何を言おうとしているのかを知るようになるでしょう。
ここには解決策があります - 私はそれを書いているだけですが、コンパイルしていないので、もっと作業することができます。
機能 - 空の木（ `トン== nil`）が有効でBSTではないと言う
bool isBST(class tree* root, int minL, int maxR)
{
if(!root)
return true;
else if(root->data > minL && root->data < maxR)
return true;
else if(root->data < minL || root->data > maxR)
return false;
return isBST(root->right, root->data, maxR) && isBST(root->left, minL, root->data);
}
Caller -
isBST(root, INT_MIN, INT_MAX);
？あなたのベースケースは私には間違っているようです。さらに、この質問はそれほど詳しく述べる必要があります。コードの現在の_issue_は何ですか？具体的にする。チェックアウト[ask] – CollinD
私は何を意味したのですか？このコードは、ツリー内に値を持つツリーがBSTのように配置されているかどうかをチェックすることです。私のコードが私の望むやり方で機能しているかどうかは分かりませんし、もっと意見を出したいと思っています。 – Clement
SOはコードテストサービスではありません。あなたはそれを実行し、それが自分で動作するかどうかを完全に知ることができます。複数の同一のキーや空のツリーのようなエッジケースを必ず確認してください。それがうまくいかなければ、それは宇宙を破壊するのではなく、悪い出力やクラッシュを与えます。コードを実行するのを恐れず、コードが動作するかどうかを確認してください。コードレビューを探しているなら、そのための別のSEサイトがあります。あなたが特定の問題を抱えている場合、これがその場所です。質問の更新や説明がある場合は、コメントではなく質問の編集として投稿することをお勧めします。 – CollinD