Бинарные деревья

Rear

Rear

FIFO (FIRST INPUT — FIRST OUTPUT)

Функции, реализующие операции работы с очередью

int empty()

{

if (frnt ==rear) return 1;

else return 0; }

float remove()

{

if(empty() == 1)

{

printf("Очередь пуста."); return 0.0;

} else

{

if(frnt == (Maxq-1)) frnt=0; else frnt++; return git[frnt]; } }

void insert(float x)

{

if(rear == (Maxq-1)) rear = 0;

else rear++;

if(rear == frnt)

printf("Переполнение!");

else git[rear]=x; }

Реализация очереди на базе однонаправленного связанного списка

Однонаправленный связанный список можно рассматривать в качестве очереди поскольку (рис. 2.12): а) определены начало и конец списка, б) задан порядок расположения узлов.

ptrn —■*

t

frnt

Начало очереди

info

ptrn

ptrn=NULL —■*! info ptrn

rear

Конец очереди

Рис. 2.12

1. Операция проверки пустоты очереди empty

if(frnt == NULL && rear == NULL; printf("Очередь пуста.");

2. Операция удаления элемента из очереди remove (рис. 2.13)

x=frnt->infо; p=frnt;

frnt=frnt->ptrn; free(p);

in\Wn —A info ptrn—■*■

frnt

•1Г

frnt

Начало очереди

Рис. 2.13

3. Операция помещения элемента в очередь insert (рис. 2.14)

p=(struct NODE*)malloc(sizeof(struct NODE)); p->ptrn=NULL;

p->info=x;

rear->ptrn=p;

rear=p;

ptrn

Л

ptrn=NULL ---►I info ptrn i

Конец очереди

Рис. 2.14

Недостатки представления очереди и стека в виде связанного списка:

• Элемент списка занимает в оперативной памяти больше места, чем элемент массива.

• Требуется дополнительное время на обработку списка: необходимо выделять блоки оперативной памяти под узлы и изменять значения указателей.

Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент (корень), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями. Каждый элемент бинарного дерева называется узлом [1,3].

Общепринятый способ изображения бинарного дерева представлен на рис. 2.15: дерево состоит из 9 узлов; А — корень; левое поддерево имеет корень В; правое — С.

Узел у, который находится непосредственно под узлом х, называется потоком х; если х находится на уровне i, то у — на уровне i+\. Наоборот, узел х называется предком у. Считается, что корень дерева расположен на уровне 1. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой. Если элемент не имеет потомков, он называется листом. Остальные элементы — внутренние узлы. Число потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева. Число ветвей, которое нужно пройти от корня к узлу х, называется длиной пути к х. Корень имеет длину пути 1; узел на уровне / имеет длину пути /.

Рис. 2.15

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

Узел дерева можно описать как структуру с полями.