Деревья. Данные с динамической структурой

Списки

Данные с динамической структурой

Связанные списки - это набор последовательно организованных данных.

Главное преимущество связанных списков перед массивами состоит в том, что они могут уменьшать или увеличивать свои размеры во время выполнения программы. В частности, мы не должны заранее знать его максимальный размер.

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

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

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

Узел и ссылку можно описать так:

Пример: описание узла списка (не двунаправленного)

strukt spis_node

{

node *down;//

int y[20]; //=============================//

float f, g; //===Данные находящиеся в списке===//

//=============================//

} node;

Пример: описание узла списка (двунаправленного)

strukt spis_node

{

node *up; // Ссылка на узел «выше» по иерархии

node *down; // Ссылка на узел «ниже» по иерархии

int y[20]; //===========================//

float f, g; //==Данные находящиеся в списке==//

//===========================//

} node;

В повседневной жизни очень часто встречаются примеры деревьев, и вы уже наверняка знакомы с этой концепцией.

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

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

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

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

Самые простые из деревьев считаются бинарные деревья.

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

Эти подмножества называются левым и правым поддеревьями исходного дерева.

Каждый элемент бинарного дерева называется узлом дерева.

На рисунке показан общепринятый способ изображения бинарного дерева. Это дерево состоит из семи узлов, А-корень дерева. Его левое поддерево имеет корень В, а правое- корень С. Это изображается двумя ветвями, исходящими из А: левым - к В и правым - к С. Отсутствие ветви обозначает пустое поддерево.

Например, левое поддерево бинарного дерева с корнями D и Е и правое поддерево бинарного дерева с корнями F и G оба пусты.

На рисунке выше приведена структура, не являющаяся бинарным деревом.

Если А - корень бинарного дерева и В - корень его левого или правого поддерева, то говорят, что А-отец В, а В-левый или правый сын А.

Узел, не имеющий сыновей (такие как узлы D, E, F, G), называется листом.

Узел nl -предок узла n2 (а n2-потомок nl), если nl-либо отец n2, либо отец некоторого предка n2. Например, в дереве из рисунке А-предок B и C.

Узел n2-левый потомок узла n1, если n2 является либо левым сыном n1, либо потомком левого сына n1. Похожим образом может быть определен правый потомок.

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

Глубина бинарного дерева — это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева.

Стало быть, глубина дерева на первом рисунке равна 2.

Полное бинарное дерево уровня n — это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые левое и правое поддеревья.

Описание узла бинарного древа можно произвести следующим образом:

typedef class tree_node

{

tnode *root, // Указатель на корень дерева

*left, // Указатель на левого сына

*right; // Указатель на правого сына

int key; // Ключ узла

float y[20]; // Данные хранимые в узле

tree_node(); // Конструктор класса узeл

~tree_node(); // Деструктор класса узeл

int AddNode(int key); // =================//

................................... //Функции класса узел=//

int DelNode(int key); //=================//

} tnode;

Дата добавления: 2014-10-17