Структуры и алгоритмы обработки данных


Краткая теория


 

Общие сведения о структуре данных – дерево.

Дерево - это нелинейная связанная структура данных, характеризуемая следующими признаками :

  • дерево имеет один элемент, на который нет ссылок от других элементов. Этот элемент, или "узел", называется корнем дерева;
  • в дереве можно обратиться к любому элементу путем прохождения конечного числа ссылок (указателей) ;
  • каждый элемент дерева связан только с одним предыдущим элементом.

Каждый узел дерева может быть промежуточным (элементы 2,3,5,7) либо терминальным ("листом" дерева) (элементы 4,9,10,11,8,6). Характерной особенностью терминальных узлов является отсутствие ветвей.

 

 

Элемент Y, находящийся непосредственно ниже элемента X, называется непосредственным потомком X, если X находится на уровне i , то говорят, что Y лежит на уровне i+1.

Считается, что корень лежит на уровне 0.

Число непосредственных потомков элемента называется его степенью исхода, в зависимости от степени исхода узлов деревья классифицируют :

A) Если степень исхода узлов - М, то дерево называется М-арным ;

B) Если степень исхода узлов - М или 0, то - полное М-арное дерево;

C) Если степень исхода узлов дерева равна 2, то дерево называется бинарным ;

D) Если степень исхода равна 2 или 0, то - полное бинарное дерево.

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

Представление деревьев в памяти ЭВМ

Деревья наиболее удобно представлять в памяти ЭВМ в виде связанных нелинейных списков. Элемент должен содержать INFO-поле, где содержится характеристика узла. Следующее поле определяет степень исхода узла и количество полей указателей равное степени исхода. Каждый указатель элемента ориентирует данный элемент-узел с его сыновьями. Узлы, в которые входят стрелки от исходного элемента, называются его сыновьями.

INFO-поле содержит два поля : поле записи (rec) и поле ключа (key). Ключ задается числом, по ключу определяют место элемента в дереве.

 

Сведение М-арного дерева к бинарному




- Начало -  - Назад -  - Вперед -



Книжный магазин