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方法，这是否意味着Integer.MIN_VALUE = 1并且Integer.MAX_VALUE = 7被传递给了方法体？

谢谢

4

2 回答 2

1
  1. 如果你想创建一棵大树，我建议你创建一个insertIntoTree(Tree node, int value)函数，在适当的位置添加一个新节点。然后，您可以根据需要多次在循环中调用该函数，可能使用随机生成的值。请注意，尽管您可能会遇到不平衡的 BT，但仍然是 BT。
  2. 不，它不会将 1 和 7 传递给ifBST，它会传递整数类型的最小和最大可能值——可能是 -2^31-1 和 2^31。
于 2013-04-11T20:03:04.463 回答
0

1）听起来你想写一个添加函数。这是一个从根开始遍历树的函数。如果您要插入的值小于根节点，请输入左节点。如果大于根节点，则输入右节点。使用递归重复此操作，直到您要输入的节点为空。然后在该点创建一个新的树节点并将左或右子节点设置为该节点。

2）考虑使其成为二叉搜索树的条件。左边节点应该比父节点小，右边更大。使用这些条件如何确保树的有效性

于 2013-04-11T20:02:31.933 回答