我必须创建一个静态方法来检查给定的树是否是二叉搜索树。需要 BinaryTree<String>
作为它的参数,它只能触及每个节点一次。
我以前用数字填充了我的树,但数据类型为字符串,我现在将它们切换为字母,因为有些人认为我想使用整数。
我遇到的问题是,当我的 isBST() 方法在 tree4 上执行时, boolean bst 没有被触发。
到目前为止我所拥有的是:
public class BinarySearchTree < T extends Comparable < ? super T >> {
public static boolean isBST(BinaryTree<String> tree) {
boolean bst = true;
if (tree.getRootData() != null) {
Iterator<String> iterator = tree.getInorderIterator();
String prev = iterator.next();
while (bst && iterator.hasNext()) {
String next = iterator.next();
System.out.println(next); // Debug purposes only
if (prev.compareTo(next) > 0) {
bst = false;
}
}
}
return bst;
}
}
对于我的测试用例,我有这个:
public class Test {
public static void main(String[] args) {
BinarySearchTree<String> tree1 = new BinarySearchTree<String>();
BinarySearchTree<String> tree2 = new BinarySearchTree<String>();
BinaryTree<String> h = new BinaryTree<String>("h");
BinaryTree<String> g = new BinaryTree<String>("g");
BinaryTree<String> f = new BinaryTree<String>("f");
BinaryTree<String> e = new BinaryTree<String>("e", f, g);
BinaryTree<String> d = new BinaryTree<String>("d");
BinaryTree<String> a = new BinaryTree<String>("a");
BinaryTree<String> b = new BinaryTree<String>("b");
BinaryTree<String> tree3 = new BinaryTree<String>("c", a, e);
BinaryTree<String> tree4 = new BinaryTree<String>("c", a, b);
System.out.println("BinarySearchTree.isBST(tree3): " + BinarySearchTree.isBST(tree3));
System.out.println("BinarySearchTree.isBST(tree4): " + BinarySearchTree.isBST(tree4));
}
}
这将返回以下输出:
c
f
e
g
BinarySearchTree.isBST(tree3): true
c
b
BinarySearchTree.isBST(tree4): true
当我从静态方法中打印出compareTo 语句时,我看到第二棵树(tree4)在命中b 时返回-1。这就是为什么对于 tree4,它返回 true,因为 boolean 值没有被触发。
对此有什么建议吗?
最佳答案
String 的compareTo() 函数按字符串的字母顺序(自然顺序)而不是实际的数值(要比较的值)工作。
比较整数的字符串值没有多大意义。
无论如何,在您的示例中 - 您需要在执行时更新“prev”,在示例树中,每个中序后继者都与 4 进行比较(因为它从未更新过),并且所有值都大于 4,所以 true 是回。
在另一种情况下,(当你将 9 更改为 10 时)按字典顺序,10 < 4 所以你得到了错误。因此,如果您想比较整数的“真实”值,请使用 Integer,而不是 String。
使用BinaryTree<Integer>
相反,您的解决方案应该有效
关于java - 使用静态方法检查二叉树是否是二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36854727/