Мы знаем, что дерево — это нелинейная структура данных. Он не имеет ограничений по количеству детей. Бинарное дерево имеет ограничение, поскольку любой узел дерева имеет не более двух дочерних элементов: левого и правого дочерних элементов.
Введение в полное двоичное дерево
Двоичное дерево называется полным бинарным деревом, когда все уровни заполнены полностью, за исключением узлов самого низкого уровня, которые заполняются максимально слева.
Полное бинарное дерево
Немного терминологии
- Корень— узел, в котором от родителя не исходит ни одно ребро. Пример — узел А
- Дочерний— узел, имеющий некоторое входящее ребро, называется дочерним. Пример — узлы B, H являются дочерними узлами A и D соответственно.
- Одноуровневый— узлы, имеющие одного и того же родителя, являются одноуровневыми. Пример- J, K являются братьями и сестрами, так как у них один и тот же родитель E.
- Степень узла— количество дочерних элементов определенного родителя. Пример. Степень A равна 2, а степень H равна 1. Степень L равна 0.
- Внутренние/внешние узлы. Листовые узлы являются внешними узлами, а нелистовые узлы — внутренними узлами.
- Уровень— количество узлов на пути к целевому узлу. Пример. Уровень узла H равен 3, поскольку узлы A, D и H сами образуют путь.
- Высота— количество ребер для достижения конечного узла, корень находится на высоте 0. Пример — высота узла E равна 2, так как он имеет два ребра от корня.
Свойства полного бинарного дерева
- Полное бинарное дерево называется правильным бинарным деревом, все листья которого имеют одинаковую глубину.
- В полном бинарном дереве число узлов на глубине dравно 2 d.
- В полном бинарном дереве с nузлами высота дерева равна log(n+1).
- Все уровни, кроме последнего, полностью заполнены.
Идеальное бинарное дерево против полного бинарного дерева
Двоичное дерево высоты «h», имеющее максимальное количество узлов, является совершенным бинарным деревом.
Для заданной высоты h максимальное количество узлов равно 2 h+1 −1.
Полное бинарное дерево высоты h является правильным бинарным деревом до высоты h-1, и элементы последнего уровня хранятся в порядке слева направо.
Пример 1
Бинарное дерево
Высота данного бинарного дерева равна 2, а максимальное количество узлов в этом дереве равно n= 2 h+1 −1 = 2 2+1 −1 = 2 3 −1 = 7.
Следовательно, мы можем заключить, что это идеальное бинарное дерево.
Теперь для полного бинарного дерева оно заполнено до высоты h-1, т.е. 1, а элементы последнего уровня сохраняются в порядке слева направо. Следовательно, это также полное двоичное дерево. Вот представление элементов при хранении в массиве
Элемент хранится в массиве уровень за уровнем
В массиве все элементы хранятся непрерывно.
Пример 2
Бинарное дерево
Высота данного бинарного дерева равна 2, а максимальное количество узлов, которое должно быть, равно 2 h+1 — 1 = 2 2+1 — 1 = 2 3 — 1 = 7.
Но количество узлов в дереве равно 6. Следовательно, это не идеальное бинарное дерево.
Теперь для полного бинарного дерева оно заполнено до высоты h-1, т.е. 1, и элемент последнего уровня сохраняются в порядке слева направо. Следовательно, это полное бинарное дерево. Сохраните элемент в массиве, и он будет выглядеть так:
Элемент хранится в массиве уровень за уровнем
Пример 3
Бинарное дерево
Высота бинарного дерева равна 2, а максимальное количество узлов, которое может быть, равно 7, но узлов всего 5, поэтому это не идеальное бинарное дерево.
В случае полного бинарного дерева мы видим, что на последнем уровне элементы не заполняются слева направо. Так что это не полное бинарное дерево.
Элемент хранится в массиве уровень за уровнем
Элементы массива не являются непрерывными.
Полное двоичное дерево против полного двоичного дерева:
Для полного бинарного дерева у каждого узла есть либо 2 дочерних элемента, либо 0 дочерних элементов.
Пример 1
Бинарное дерево
В данном бинарном дереве нет узла, имеющего степень 1, 2 или 0 для каждого узла, следовательно, это полное бинарное дерево.
Для полного бинарного дерева элементы хранятся по уровням, а не с крайней левой стороны на последнем уровне. Следовательно, это не полное бинарное дерево. Представление массива:
Элемент хранится в массиве уровень за уровнем
Пример 2
Бинарное дерево
В данном бинарном дереве нет узла, имеющего степень 1. Каждый узел имеет степень либо 2, либо 0. Следовательно, это полное бинарное дерево.
Для полного бинарного дерева элементы хранятся по уровням и заполняются с крайней левой стороны последнего уровня. Следовательно, это полное бинарное дерево. Ниже представлено массивное представление дерева:
Элемент хранится в массиве уровень за уровнем
Пример 3
Бинарное дерево
В данном бинарном дереве узел B имеет степень 1, что нарушает свойство полного бинарного дерева, следовательно, это не полное бинарное дерево.
Для полного бинарного дерева элементы хранятся по уровням и заполняются с крайней левой стороны последнего уровня. Следовательно, это полное бинарное дерево. Массивное представление бинарного дерева:
Элемент хранится в массиве уровень за уровнем
Пример 4
Бинарное дерево
В данном бинарном дереве узел C имеет степень 1, что нарушает свойство полного бинарного дерева, следовательно, это не полное бинарное дерево.
Для полного бинарного дерева элементы хранятся по уровням и заполняются с крайней левой стороны последнего уровня. Здесь узел E нарушает условие. Следовательно, это не полное бинарное дерево.
Создание полного бинарного дерева
Мы знаем, что полное бинарное дерево — это дерево, в котором, за исключением последнего уровня (скажем, l ), все остальные уровни имеют ( 2l ) узлов, и узлы выстроены слева направо.
Его можно представить с помощью массива. Если родитель имеет индекс i, то левый дочерний элемент находится в 2i+1, а правый дочерний элемент — в 2i+2.
Полное бинарное дерево и его представление в виде массива
Алгоритм:
Для создания полного двоичного дерева нам требуется структура данных очереди для отслеживания вставленных узлов.
Шаг 1: Инициализируйте корень новым узлом, когда дерево пусто.
Шаг 2: Если дерево не пусто, получите передний элемент
Если передний элемент не имеет левого дочернего элемента, установите левый дочерний элемент в новый узел
Если правильный дочерний элемент отсутствует, установите правильный дочерний элемент в качестве нового узла.
Шаг 3: Если у узла есть оба дочерних элемента, извлеките его из очереди.
Шаг 4: Поставьте в очередь новые данные.
Иллюстрация:
Рассмотрим следующий массив:
1. 1-й элемент будет корнем (значение по индексу = 0)
А принимается за корень
2. Следующий элемент (с индексом = 1) будет левым, а третий элемент (с индексом = 2) будет правым дочерним элементом корня.
B как левый дочерний элемент и D как правый дочерний элемент
3. Четвертый (индекс = 3) и пятый элементы (индекс = 4) будут левым и правым дочерними элементами узла B.
E и F — левый и правый потомки B
4. Следующий элемент (индекс = 5) будет левым дочерним элементом узла D.
G делается левым дочерним элементом узла D
Вот как создается полное бинарное дерево.
