Двоичное дерево или бинарное дерево - Упорядоченная динамическая структура данных состоящих из элементов (узлов) каждый, который является родителем 2 ух других левого и правого соответственно.
Бинарное дерево может иметь не более 2 ух потомков.
Коренной элемент – Элемент, у которого нет родительских элементов.
Листья дерева – Элементы, у которых нету потомков а указатели на левую и правую часть дерева указывают на NULL.
В бинарном дереве каждый новый элемент добавляется упорядоченно. И новые элементы не двигают старые как в Пирамидной сортировке.
Обход этого дерева очень удобно совершать через рекурсивный алгоритм.
Разберем пример:
И так допустим у нас есть цифры массив с данными: 50, 45, 55, 20, 28, 68, 89, 75, 19.
Вначале берем число 50 и делаем его корнем нашего бинарного дерева.
После чего
Берем число 45 и сравниваем его с 50. Т.К. 45 меньше 50 ставим его слева от корня.
Берем число 55 и сравниваем его с 50. Т.К. 55 больше 50 ставим его правее от корня.
Хочу отметить, что в данном случае 55 и 45 являются листьями дерева. Т.К. их потомки ведут к NULL.
Еще раз повторюсь при добавлении нового элемента или же при поиске существующего. Этот элемент сравнивается с корнем дерева, если корень больше сравнение идет уже с потомком корня справа, если же меньше тогда сравнение идет с потомком слева.
Дерево
Дерево – Это иерархическая структура данных представляющая совокупность элементов (узлов) и родительских отношений.
Основные свойства:
· Корень может иметь потомков но не может иметь предков.
· Любой узел (за исключением главного корня) имеет только одного предка
· Во всем дереве отсутствуют замкнутые контуры (циклы)
Корневой узел – узел, не имеющий предков.
Корень – любая вершина взятая наблюдателем
Внутренний узел – любой узел, не являющийся листом
Высота дерева - количество узлов от самого глубокого до корня
Глубина узла – количество узлов от нужного до корня
Давайте разберем пример:
Привычнее всего разбирать на примере книги. Допустим что сама книга это корневой узел. В таком случае Т.К. в Книге 2 главы мы можем разделить ее в две стороны, на 2 ветки. Но не будем забывать, что в главах, присутствуют какие либо параграфы. Хочу обратить внимание, что в главе 1 целых 3 параграфа нет это не ошибка. В дереве общего вида может быть сколько угодно ветвей только больше «0» (иначе это будет лист дерева).
Применения Деревьев.
· управление иерархией данных
· упрощение поиска информации
· управление сортированными списками данных
· синтаксический разбор арифметических выражений оптимизация программ
· в качестве технологии компоновки цифровых картинок для получения различных визуальных эффектов
· форма принятия многоэтапного решения
Наименьший общий предок
Наименьший общий предок (нижайший общий предок) вершин u и v в корневом дереве T — наиболее удалённая от корня дерева вершина, лежащая на обоих путях от u и v до корня, т. е. являющаяся предком обеих вершин.