Представление бинарного дерева в виде массива (стр. 2 из 2)

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

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

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

адрес = 2к-1+i-1,

где k-номер уровня вершины, i- номер на уровне k в полном бинарном дереве. Адрес корня будет равен единице. Для любой вершины можно вычислить адреса левого и правого потомков

адрес_L = 2к+2(i-1)

адрес_R = 2к+2(i-1)+1

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

Приложение

В качестве примера использования бинарного дерева в виде массива был использован массив – a[ i ], состоящий из 15 элементов (от 1 до 15). В результате дерево должно иметь вид:

Текст программы

дерево нелинейное массив бинарное

#include <fstream.h>

#include <stdio.h>

#include <conio.h>

#include <windows.h>

char bufRus[256];

char* Rus(const char* text){

CharToOem(text, bufRus);

return bufRus;

}

int main()

{ int i,k;

int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

cout << Rus("Дерево:") << endl;

cout << Rus("Корень дерева - a[0] = ") << a[0] << endl;

k=0;

for (i=1; i<=14; i++)

{

if (i%2==0) k=k+1;

if (i%2!=0) cout << Rus(" левый сын узла a[") << i-k-1 << "]=" << a[i] << endl;

if (i%2==0) cout << Rus(" правый сын узла a[") << i-k-1 << "]=" << a[i] << endl;

}

return 0;

Результат выполнения программы:

Список литературы

1) Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы.

2) Д. Райли Абстракция и структуры данных. Вводный курс.

3) Д. Кнут Искусство программирования для ЭВМ. Т1, Основные алгоритмы.