Проверьте, является ли двоичное дерево бинарным деревом поиска, используя статический метод

Я должен создать статический метод, который проверяет, является ли данное дерево бинарным деревом поиска. Требуется BinaryTree<String> в качестве аргумента, и он может касаться каждого узла только один раз.

Ранее мои деревья были заполнены числами, но с типом данных String я теперь переключил их на буквы, так как некоторые думали, что я хочу использовать целые числа.

Проблема, с которой я сталкиваюсь, заключается в том, что логический bst не отключается, когда мой метод isBST() выполняется на tree4.

То, что я до сих пор, это:

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) оно возвращает -1, когда оно достигает b. Вот почему для tree4 он возвращает true, потому что логическое значение не сработало.

Есть предложения по этому поводу?

Источник

2 ответа

Решение

Функция String String работает в алфавитном порядке (естественном порядке) строки, а не на фактическом числовом значении (которое вы хотите сравнить).
Сравнение строковых значений целых чисел не имеет особого смысла.

В любом случае, в вашем примере - вам нужно обновить "prev" во время выполнения, в вашем дереве примеров каждый преемник inorder сравнивается с 4 (поскольку он никогда не обновляется), а все значения больше 4, поэтому возвращается true.

В другом случае (если вы измените 9 на 10) лексикографически, 10 < 4, так что вы ошибаетесь. Итак, если вы хотите сравнить "реальное" значение целых чисел, используйте Integer, а не String.

использование BinaryTree<Integer>вместо дерева, и ваше решение должно работать

Источник

Добавить в 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

Противоположность того, что вы хотите.

Источник
Другие вопросы по тегам