Тест глубины первого дерева

Question

Я сделал Java-программу для просмотра дерева с глубиной в первую очередь.Программа правильная, но выбор сына узла является случайным.например, в этом дереве:

иногда, результат:

• A-B-E-C-F-D
• A-C-F-D-B-E
• A-B-E-D-C-F

Я хочу провести тестирование (модульное тестирование) этой программы, но я понятия не имею, как я могу это сделать?пожалуйста

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

Answer 1

Есть 2 свойства, которые вы хотите проверить:

1. Каждый узел посетил ровно один
2. Обход - это глубина сначала

Первое легкодля проверки: количество посещенных уникальных узлов должно быть равно количеству узлов в дереве.Можно проверить это на любом случайном дереве.

Второе немного сложнее - выражение в общем случае, вероятно, более сложное, чем проверенный код.Проще всего выбрать некоторые репрезентативные ограничения, основанные на конкретных известных данных, то есть

• B должно быть после A
• E должно быть сразу после B
• ...

Трудно представить реалистичный код, который удовлетворяет первому свойству для всех деревьев, но может не дать второго только в определенных случаях.Так что за пределами самых формальных систем, критически важных для безопасности (и вообще, что они делают с использованием динамических структур данных?), Этого будет достаточно.

Answer 2

Это означает, что порядок дочерних элементов каждого узла не является детерминированным. Вы, вероятно, использовали Set, чтобы держать детей. Попробуйте использовать LinkedHashSet (который сохраняет порядок вставки) или SortedSet (который сортирует дочерние элементы). Таким образом, порядок всегда будет одинаковым.

Если случайность - это особенность вашего дерева, и вы хотите оставить ее как есть, то посмотрите другие ответы или измените сам алгоритм, чтобы убедиться, что вы всегда сортируете дочерние элементы при обходе дерева.

Answer 3

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

Answer 4

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

В качестве альтернативы, вы могли быпопытаться наложить на узлы четко определенный порядок (например, отсортировав по алфавиту дочерние элементы каждого узла, вместо того, чтобы управлять ими в Set)