7.3. Бинарные деревья
С точки зрения представления в памяти различают два типа деревьев: бинарные и сильноветвящиеся. В бинарном дереве из каждой вершины выходит не более двух дуг (рис. 7.7). В сильноветвящемся дереве количество дуг может быть произвольным. Вершины в дереве, имеющие степень ноль, называются листьями.
p7 p8 p5 p4 p6 p2 p1
корень p3 p1,p2,p6
– узлы p3,p4,p5,p7,p8
- листья
Рис. 7.7. Бинарное дерево.
Другим признаком структурной классификации бинарных деревьев является полнота и строгость бинарного дерева. Полное бинарное дерево на всех уровнях, меньше n имеют степень узла 2, а на уровне n степень равно 0 (рис. 7.8). Неполное бинарное дерево на уровнях, меньше n может иметь степень узла меньше 2. Строго бинарное дерево состоит только из узлов, имеющих степень два или ноль (рис. 7.9). Не строго бинарное дерево содержит узлы со степенью равной одному.
а). б).
Рис. 7.8. Неполное (а) и полное (б) бинарные деревья.
а). б).
Рис. 7.9. Строго (а) и не строго (б) бинарные деревья.
7.3.1. Представление бинарных деревьев
Бинарные деревья могут быть представлены в виде списков или массивов. Списочное представление основано на элементах, соответствующих узлам дерева (рис. 7.10). Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой – с левым. Листья имеют пустые указатели потомков.
При списковом представлении обязательно следует сохранять указатель на узел, являющийся корнем дерева. Можно заметить, что такой способ представления имеет сходство с простыми линейными списками. Сходство не случайно, т.к. дерево является разновидностью мультисписка, образованного комбинацией множества линейных списков. Каждый линейный список объединяет узлы, входящие в путь от корня дерева к одному из листьев.
В виде массива проще всего представляется полное бинарное дерево, так как оно всегда имеет строго определенное число вершин на каждом уровне (рис. 7.11). Вершины можно пронумеровать слева направо последовательно по уровням и использовать номера в качестве индексов в одномерном массиве. Если число уровней дерева в процессе обработки не будет существенно изменяться, то такой способ представления будет значительно более экономичным, чем любая списковая структура.
Однако далеко не все бинарные деревья являются полными. Для неполных бинарных деревьев применяют следующий способ представления. Бинарное дерево дополняется до полного дерева, вершины последовательно нумеруются. В массив заносятся только те вершины, которые были в исходном неполном дереве. При таком представлении элемент массива выделяется независимо от того, будет ли он содержать узел исходного дерева. Следовательно, необходимо отметить неиспользуемые элементы массива, например, занесением специального значения в соответствующие элементы массива. В результате структура дерева переносится в одномерный массив.
p5 p4 p2 p1 p3 p1 p2 p3 p4 p5 имя
узла указатель
левого поддерева указатель
правого поддерева
Рис. 7.10. Представление бинарного дерева в виде списковой структуры.
1 2 3 4 5 6 7 адрес
последней вершины полного дерева 2n-1 p5 p4 p2 p1 p3 p7 p1 p2 p3 p4 p5
p7 A
= 2k-1+i-1
Рис. 7.11. Представление бинарного дерева в виде массива.
Адрес любой вершины в массиве:
A = 2k-1+i-1,
где k-номер уровня вершины, i - номер на уровне k в полном бинарном дереве.
Адрес корня равен единице. Для любой вершины адреса левого и правого потомков равны:
AL = 2k+2i-1
AR = 2k+2i-1+1
Недостатком такого способа представления бинарного дерева является то, что структура данных является статической. Размер массива выбирается исходя из максимально возможного количества уровней бинарного дерева. Причем, чем менее полным является дерево, тем менее рационально используется память.