java - 使用静态方法检查二叉树是否是二叉搜索树

Question

我必须创建一个静态方法来检查给定的树是否是二叉搜索树。需要 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 值没有被触发。

对此有什么建议吗？

Answer 1

String 的compareTo() 函数按字符串的字母顺序(自然顺序)而不是实际的数值(要比较的值)工作。
比较整数的字符串值没有多大意义。

无论如何，在您的示例中 - 您需要在执行时更新“prev”，在示例树中，每个中序后继者都与 4 进行比较(因为它从未更新过)，并且所有值都大于 4，所以 true 是回。

在另一种情况下，(当你将 9 更改为 10 时)按字典顺序，10 < 4 所以你得到了错误。因此，如果您想比较整数的“真实”值，请使用 Integer，而不是 String。

使用BinaryTree<Integer>相反，您的解决方案应该有效