• Поиск

    Введите ваш запрос для начала поиска.

  • Об авторах

    Курс разработан на кафедре Компьютерных технологий и систем Кубанского государственного аграрного унивеситета. Авторами являются заведующий кафедрой, доктор технических наук, профессор Лойко Валерий Иванович и доцент кафедры, кандидат физико-математических наук Лаптев Сергей Владимирович.

    Основные цели сайта

      Сайт предназанчен для максимально эффективного и быстрого доступа ко всем материалам курса "Алгоритмы и структуры данных", имеющимся на кафедре компьютерных технологий и систем КубГАУ. Основной задачей его создания является повышения эффективности освоения дисциплины студентами и всеми желающими.

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

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

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

Каждый узел дерева может быть промежуточным (элементы 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). Ключ задается числом, по ключу определяют место элемента в дереве.

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

1. В каждом узле дерева отсекают все ветви, кроме крайних левых, соответствующих старшим сыновьям;

2. Соединяют горизонтальными линиями сыновей одного родителя (узла);

3. Старшим сыном в каждом узле полученной структуры будет узел под обрабатываемым узлом.

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

 - ключ записи,

 - ссылка

  • · на элемент влево-вниз,
  • · на элемент вправо-вниз и
  • · на текст записи.

При построении необходимо помнить, что левый сын имеет ключ меньше чем отец (родитель). Значение ключа правого сына больше значения ключа отца.

Если узлы дерева имеют значения 6, 21, 48, 49, 52, 86, 101, то бинарное дерево может иметь вид, изображенный на рисунке ниже. Это упорядоченное бинарное дерево с минимальным числом уровней. Идеально сбалансированное дерево - это дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не больше, чем на единицу.