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

Question

我必须创建一个静态方法来检查给定树是否为二叉搜索树。它以 BinaryTree<String> 作为它的参数，它只能接触每个节点一次。

我以前用数字填充我的树，但数据类型为字符串，我现在将它们切换为字母，因为有些人认为我想使用整数。

我遇到的问题是，当我在 tree4 上执行 isBST() 方法时，布尔 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));
    }
}

这个returns输出如下：

c
f
e
g
BinarySearchTree.isBST(tree3): true
c
b
BinarySearchTree.isBST(tree4): true

当我从我的静态方法中打印出 compareTo 语句时，我看到对于第二棵树 (tree4) 它 returns -1 当它命中 b .这就是为什么对于 tree4，它 returns 为真，因为布尔值没有被触发。

对此有什么建议吗？

Answer 1

String 的 compareTo() 函数适用于 String 的字母顺序（自然顺序）而不是实际数值（您要比较的值）。
比较整数的字符串值没有多大意义。

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

在另一种情况下，（当你将 9 更改为 10 时）按字典顺序，10 < 4 所以你得到的是错误的。因此，如果要比较整数的 'real' 值，请使用整数，而不是字符串。

改用 BinaryTree<Integer>tree，您的解决方案应该有效

Answer 2

添加到 Parthas 答案

    public static void main (String[] args) {
    String ten = "10";
    String nine = "9";
    System.out.println(nine.compareTo(ten));
    System.out.println(ten.compareTo(nine));
}

生产：

8

-8

与您想要的相反。

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

Check if a binary tree is a binary search tree using a static method

java

tree

binary-tree

inorder

data-structures