Представление бинарных деревьев

Бинарные деревья могут быть представлены в виде списков или массивов. Списочное представление основано на элементах, соответствующих узлам дерева (рис. 7.10). Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой – с левым. Листья имеют пустые указатели потомков.

При списковом представлении обязательно следует сохранять указатель на узел, являющийся корнем дерева. Можно заметить, что такой способ представления имеет сходство с простыми линейными списками. Сходство не случайно, т.к. дерево является разновидностью мультисписка, образованного комбинацией множества линейных списков. Каждый линейный список объединяет узлы, входящие в путь от корня дерева к одному из листьев.

В виде массива проще всего представляется полное бинарное дерево, так как оно всегда имеет строго определенное число вершин на каждом уровне (рис. 7.11). Вершины можно пронумеровать слева направо последовательно по уровням и использовать номера в качестве индексов в одномерном массиве. Если число уровней дерева в процессе обработки не будет существенно изменяться, то такой способ представления будет значительно более экономичным, чем любая списковая структура.

Однако далеко не все бинарные деревья являются полными. Для неполных бинарных деревьев применяют следующий способ представления. Бинарное дерево дополняется до полного дерева, вершины последовательно нумеруются. В массив заносятся только те вершины, которые были в исходном неполном дереве. При таком представлении элемент массива выделяется независимо от того, будет ли он содержать узел исходного дерева. Следовательно, необходимо отметить неиспользуемые элементы массива, например, занесением специального значения в соответствующие элементы массива. В результате структура дерева переносится в одномерный массив.

Рис. 7.10. Представление бинарного дерева в виде списковой структуры.

Рис. 7.11. Представление бинарного дерева в виде массива.

Адрес любой вершины в массиве:

A = 2^k-1+i-1,

где k-номер уровня вершины, i - номер на уровне k в полном бинарном дереве.

Адрес корня равен единице. Для любой вершины адреса левого и правого потомков равны:

A_L = 2^k+2^i-1

A_R = 2^k+2^i-1+1

Недостатком такого способа представления бинарного дерева является то, что структура данных является статической. Размер массива выбирается исходя из максимально возможного количества уровней бинарного дерева. Причем, чем менее полным является дерево, тем менее рационально используется память.