Страницы

Поиск по вопросам

пятница, 16 ноября 2018 г.

Бинарное дерево

Требуется реализовать бинарное дерево, НО: Обязательное ли условие, чтобы правая крайняя сторона с корня увеличивалась до максимума, а левая крайняя сторона уменьшалась до минимума?(см. на приложенное изображение) Интернет перерыл, но прямым текстом это нигде не написано, но на одних визуализациях это условие выполняется, а на других нет.
Обновлено: Можно ли данную реализацию считать бинарным деревом?


Ответ

Определения
Определение бинарного дерева:(1)
Дерево, в котором каждая вершина имеет не более двух потомков, называется бинарным, в противном случае будем дерево называть произвольным
Определение бинарного дерева поиска:(2)
Будем называть бинарное дерево деревом поиска, если для любой вершины ключ этой вершины не меньше ключа любой вершины левого поддерева и строго меньше ключа любой вершины правого поддерева
Ссылки:
(1) В.Д.Валединский, Ю.Н.Пронкин Вычислительные системы и программирование, Схемы хранения данных (Москва, 2006 г.) стр 67 (2) В.Д.Валединский, Ю.Н.Пронкин Вычислительные системы и программирование, Схемы хранения данных (Москва, 2006 г.) стр 74

Изображение на рисунке терминала является бинарным деревом, но не бинарном деревом поиска, так как нет алфавитного или какого-нибудь другого, заранее обговорённого, порядка

Комментариев нет:

Отправить комментарий