2

与えられた二分木が二分探索木であるかどうか知りたかったのです。

どうすればいいのかわからない？

私が知っている唯一のことは、BSTを順番にトラバースすると、昇順の出力が得られるということです。

したがって、これが確認する必要がある唯一の条件ですか、それとも他に確認する必要がある条件がありますか。

他に確認が必要な条件がある場合、それは何ですか？そして、なぜそれらの条件をチェックする必要があるのですか？なぜなら、INORDERトラバーサル自体は、与えられたツリーがBSTであるかどうかを簡単に知ることができるからです。

4

5 に答える 5

13

はい、ツリーの順序どおりのトラバーサルにより、ツリーが BST であると判断するのに十分な厳密に単調な値のリストが得られる場合。

于 2012-04-16T08:42:19.387 に答える
5

二分探索木の定義によれば、二分木のすべてのノードが次の条件を満たす場合、それは二分探索木です。

  • ノードの左側のサブツリーには、ノードのキーよりも小さいキーを持つノードのみが含まれている必要があります
  • ノードの右側のサブツリーには、ノードのキーよりも大きいキーを持つノードのみが含まれている必要があります
  • 左と右の両方のサブツリーも二分探索木である必要があります。

上記のすべての条件は、インオーダートラバーサルが昇順である場合に検証されます。

于 2013-03-05T16:04:23.103 に答える
0

Java でのシンプルだが洗練された再帰的ソリューション:

public static boolean isBST(TreeNode node, int leftData, int rightData)
{
    if (node == null) return true;

    if (node.getData() > leftData || node.getData() <= rightData) return false;

    return (isBST(node.left, node.getData(), rightData)
           && isBST(node.right, leftData,  node.getData()));

}

この関数の最初の呼び出しは、次のようになります。

if (isBST(root, Integer.MAX_VALUE, Integer.MIN_VALUE))
    System.out.println("This is a BST.");
else
    System.out.println("This is NOT a BST!");

基本的に、有効な範囲 ([ MIN_VALUE, MAX_VALUE] から開始) を作成し続け、再帰的に下降するにつれて、各ノードに対してそれを縮小し続けます。

ソース: http://exceptional-code.blogspot.com/2011/08/binary-search-trees-primer.html

于 2014-05-09T21:30:28.497 に答える
0

実際には、順番にトラバーサルを行うだけでは十分ではなく、各ノードの値がツリーのルールに従っていることを確認する必要もあります。BST の場合、左の子の値はノードの値よりも小さく、右の子の値はノードの値よりも大きくなります。Java での再帰的な例を次に示します。

private static boolean isBST(Node current, Comparable more, Comparable less) {
    if (current == null) 
        return true;

    if (less != null && current.value.compareTo(less) > 0)
        return false;

    if (more != null && current.value.compareTo(more) < 0) 
        return false;

    return isBST(current.left, more, current.value) && 
            isBST(current.right, current.value, less);
}

public static boolean isBST(BinarySearchTree tree) {
    return isBST(tree.getRoot(), null, null);
}
于 2013-08-27T13:57:04.153 に答える