Бинарное дерево — это древовидная структура данных, в которой каждый узел имеет не более двух дочерних узлов: левого и правого.
Ключевые характеристики:
- Каждый узел имеет указатель на значение (данные) и указатели на левого и правого потомков (могут быть пустыми).
- Существует корневой узел — верхний узел дерева, не имеющий предка.
- Листья — узлы, не имеющие потомков.
- Поддеревья — каждое поддерево корня бинарного дерева также является бинарным деревом.
Основные типы бинарных деревьев:
- Полное бинарное дерево: на каждом уровне за исключением, возможно, последнего, все узлы имеют двух потомков, а на последнем уровне все узлы сдвинуты влево.
- Совершенное бинарное дерево: все уровни полностью заполнены, каждый узел (кроме листьев) имеет двух потомков.
- Сбалансированное бинарное дерево: высоты левого и правого поддеревьев каждого узла отличаются не более, чем на 1.
Применение в QA:
- Тестовая иерархия: организация тестовых сценариев или наборов тестов в древовидной структуре для лучшей читаемости и навигации.
- Поиск и сортировка данных: бинарные деревья поиска используются для быстрого поиска, вставки и удаления элементов (например, при тестировании производительности операций над данными).
- Структурирование данных: представление и организация данных тестов или результатов выполнения.
Пример представления узла на Python:
python