Полное бинарное дерево

воичное дерево называется полным бинарным деревом Без рубрики

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

Введение в полное двоичное дерево

Двоичное дерево называется полным бинарным деревом, когда все уровни заполнены полностью, за исключением узлов самого низкого уровня, которые заполняются максимально слева.

воичное дерево называется полным бинарным деревом

Полное бинарное дерево

Немного терминологии

  • Корень— узел, в котором от родителя не исходит ни одно ребро. Пример — узел А
  • Дочерний— узел, имеющий некоторое входящее ребро, называется дочерним. Пример — узлы 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

олное бинарное дерево высоты h является правильным бинарным деревом

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

Высота данного бинарного дерева равна 2, а максимальное количество узлов в этом дереве равно n= 2 h+1 −1 = 2 2+1 −1 = 2 3 −1 = 7.
Следовательно, мы можем заключить, что это идеальное бинарное дерево.
Теперь для полного бинарного дерева оно заполнено до высоты h-1, т.е. 1, а элементы последнего уровня сохраняются в порядке слева направо. Следовательно, это также полное двоичное дерево. Вот представление элементов при хранении в массиве

Читайте также:  Как найти последнее вхождение строки в файловом Linux

ерь для полного бинарного дерева оно заполне

Элемент хранится в массиве уровень за уровнем

В массиве все элементы хранятся непрерывно.

Пример 2

сота данного бинарного дерева равна 2, а макси

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

Высота данного бинарного дерева равна 2, а максимальное количество узлов, которое должно быть, равно 2 h+1 — 1 = 2 2+1 — 1 = 2 3 — 1 = 7.
Но количество узлов в дереве равно 6. Следовательно, это не идеальное бинарное дерево.
Теперь для полного бинарного дерева оно заполнено до высоты h-1, т.е. 1, и элемент последнего уровня сохраняются в порядке слева направо. Следовательно, это полное бинарное дерево. Сохраните элемент в массиве, и он будет выглядеть так:

ого бинарного дерева оно заполнено до

Элемент хранится в массиве уровень за уровнем

Пример 3

ерева равна 2, а максимальное количество узлов, кото

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

Высота бинарного дерева равна 2, а максимальное количество узлов, которое может быть, равно 7, но узлов всего 5, поэтому это не идеальное бинарное дерево.
В случае полного бинарного дерева мы видим, что на последнем уровне элементы не заполняются слева направо. Так что это не полное бинарное дерево.

 

менты не заполняются слева направ

Элемент хранится в массиве уровень за уровнем

Элементы массива не являются непрерывными.

Полное двоичное дерево против полного двоичного дерева:

Для полного бинарного дерева у каждого узла есть либо 2 дочерних элемента, либо 0 дочерних элементов.

Пример 1

инарного дерева у каждого узла есть либо 2 доче

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

В данном бинарном дереве нет узла, имеющего степень 1, 2 или 0 для каждого узла, следовательно, это полное бинарное дерево.

Для полного бинарного дерева элементы хранятся по уровням, а не с крайней левой стороны на последнем уровне. Следовательно, это не полное бинарное дерево. Представление массива:

инарного дерева элементы хранятся по уровням, а не с крайней

Элемент хранится в массиве уровень за уровнем

Пример 2

нном бинарном дереве нет узла, имеющего степе

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

В данном бинарном дереве нет узла, имеющего степень 1. Каждый узел имеет степень либо 2, либо 0. Следовательно, это полное бинарное дерево.

Для полного бинарного дерева элементы хранятся по уровням и заполняются с крайней левой стороны последнего уровня. Следовательно, это полное бинарное дерево. Ниже представлено массивное представление дерева:

лементы хранятся по уровням и заполняются с крайней левой

Элемент хранится в массиве уровень за уровнем

Пример 3

рном дереве узел B имеет степень 1, что нарушает св

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

В данном бинарном дереве узел B имеет степень 1, что нарушает свойство полного бинарного дерева, следовательно, это не полное бинарное дерево.

Читайте также:  Microsoft Azure — подключение к учетной записи хранения с помощью частной ссылки

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

арного дерева элементы хранятся по уровням и заполняются с крайней левой ст

Элемент хранится в массиве уровень за уровнем

Пример 4

нарном дереве узел C имеет степень 1, что нарушае

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

В данном бинарном дереве узел C имеет степень 1, что нарушает свойство полного бинарного дерева, следовательно, это не полное бинарное дерево.

Для полного бинарного дерева элементы хранятся по уровням и заполняются с крайней левой стороны последнего уровня. Здесь узел E нарушает условие. Следовательно, это не полное бинарное дерево.

Создание полного бинарного дерева

Мы знаем, что полное бинарное дерево — это дерево, в котором, за исключением последнего уровня (скажем, l ), все остальные уровни имеют ( 2l ) узлов, и узлы выстроены слева направо.
Его можно представить с помощью массива. Если родитель имеет индекс i, то левый дочерний элемент находится в 2i+1, а правый дочерний элемент — в 2i+2.

Полное бинарное дерево и его представление в виде массива

Полное бинарное дерево и его представление в виде массива

Алгоритм:

Для создания полного двоичного дерева нам требуется структура данных очереди для отслеживания вставленных узлов.

Шаг 1: Инициализируйте корень новым узлом, когда дерево пусто.

Шаг 2: Если дерево не пусто, получите передний элемент

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

Шаг 3: Если у узла есть оба дочерних элемента, извлеките его из очереди.

Шаг 4: Поставьте в очередь новые данные.

Иллюстрация:

Рассмотрим следующий массив:

1. 1-й элемент будет корнем (значение по индексу = 0)

А принимается за корень

А принимается за корень

2. Следующий элемент (с индексом = 1) будет левым, а третий элемент (с индексом = 2) будет правым дочерним элементом корня.

B как левый дочерний элемент и D как правый дочерний

B как левый дочерний элемент и D как правый дочерний элемент

3. Четвертый (индекс = 3) и пятый элементы (индекс = 4) будут левым и правым дочерними элементами узла B.

нты (индекс = 4) будут левым и правым дочерними элемента

E и F — левый и правый потомки B

4. Следующий элемент (индекс = 5) будет левым дочерним элементом узла D.

G делается левым дочерним элементо

G делается левым дочерним элементом узла D

Вот как создается полное бинарное дерево.

Оцените статью
bestprogrammer.ru
Добавить комментарий