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

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

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

Адрес любой вершины в массиве = 2^k-1+ i — 1, где k – номер уровня узла (вершины), i – номер на уровне k в полном бинарном дереве.

Адрес корня считается равным единице.

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

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

Дата добавления: 2014-01-11