1

簡単な二分探索木チェックについては、以下のコードを見つけてください。

class Tree {

    int value;
    Tree left;
    Tree  right;

    public Tree (int a){

        value = a;
        left = right = null;
        }

}



public class VerifyBST {



public static boolean ifBST(Tree myTree, int small , int large){

        if(myTree == null)
            return true;
        if(myTree.value > small && myTree.value < large){

        boolean leftBST = ifBST(myTree.left, small,myTree.value);
        boolean rightBST = ifBST(myTree.right,myTree.value,large);

        return leftBST&&rightBST;
        }
        else{

        return false;
        }

    }

    public static void main(String[] args) {
        /*

                4
               / \
              2   6      
             / \  /\
            1   3 5 7         */

        Tree myTree = new Tree(4);

        myTree.left = new Tree(2);
        myTree.right = new Tree(6);

        myTree.left.left = new Tree(1);
        myTree.left.right = new Tree(3);

        myTree.right.left = new Tree(5);
        myTree.right.right = new Tree(7);



        System.out.println("BST or NOT?" + ifBST(myTree,Integer.MIN_VALUE,Integer.MAX_VALUE));




    }

}

私の質問:

  1. コードから明らかなように、バイナリ ツリーのすべてのエントリを手動で入力したので、手動エントリが適切ではない大きなツリーをチェックする必要がある場合は、何が最善のアプローチである必要がありますか?従うべきですか？

  2. ifBST(myTree,Integer.MIN_VALUE,Integer.MAX_VALUE)mainメソッドに渡したので、メソッド本体に and が渡されるということですInteger.MIN_VALUE = 1かInteger.MAX_VALUE = 7？

ありがとう

4

2 に答える 2

0

1) add 関数を書きたいようですね。これは、ルートから開始してツリーをトラバースする関数です。挿入する値がルート ノードより小さい場合は、左側のノードを入力します。ルート ノードより大きい場合は、正しいノードを入力します。再帰を使用して、入力しようとしているノードが null になるまでこれを繰り返します。次に、その時点で新しいツリー ノードを作成し、そのノードに左または右の子を設定します。

2) 二分探索木になる条件を考える。左のノードは親よりも小さく、右のノードは大きくする必要があります。これらの条件を使用して、ツリーの有効性をどのように保証しますか

于 2013-04-11T20:02:31.933 に答える