Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

Лекция 15 4934

Работа добавлена на сайт samzan.ru: 2015-07-10


PAGE  3

Лекция 15

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

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

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

    Заметим, что в оперативной памяти ячейки расположены линейно по
возрастанию адресов, а дерево – это метод логической организации данных.

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

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

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

function  way_around ( дерево )

    {

    way_around ( левое поддерево );

    посещение корня;

    way_around ( правое поддерево );

    }

    Приведенная функция позволяет получить на выходе отсортированную последовательность ключей, поскольку сначала посещаются вершины с меньшими ключами, расположенные в левом поддереве. Результат обхода дерева на рисунке: 1, 6, 7, 8, 9, 10,  20,  25,  28, 30.

    Можно обходить дерево и в другом порядке, например, сначала корень, потом поддеревья. Если в функции обхода первое обращение будет к правому поддереву, то результат обхода будет другим: 30, 28, 25, 20, 10, 9, 8, 7, 6, 1.

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

    Для бинарных деревьев определены следующие операции:

  •  включение узла в дерево;
  •  поиск по дереву;
  •  обход дерева;
  •  удаление узла.

    Для каждого рекурсивного алгоритма на C++ можно создать его нерекурсивный эквивалент. В приведенной ниже программе реализована нерекурсивная функция поиска по дереву с включением и рекурсивная функция обхода дерева. Первая осуществляет поиск элемента с заданным ключом. Если элемент найден, она возвращает указатель на него, а если нет – включает элемент в соответствующее место дерева и возвращает указатель на него. Для включения элемента необходимо помнить пройденный по дереву путь на один шаг назад и знать, выполняется ли включение нового элемента в левое или правое поддерево его предка.

    Программа формирует дерево из массива целых чисел и выводит его на экран.

#include <iostream.h>

struct Node

  {

  int d:

  Node *left, *right;

  };

//  Объявления функций 

Node  *first (const int d);

Node *search_insert (Node *root, const int d);

void  print_tree (Node *root, const int level);

//  Основная функция

int main ()

  {

  const  int b[] = { 10, 1, 6, 7, 8, 9, 20, 25, 28, 30 };

  const int N = sizeof (b) / sizeof (int);

  Node *root = first (b[0]);

  for (int i = 1;  i < N; i++) search_insert (root, b[i]);

  print_tree (root, 0);

  return 0;

  }

/***   Определения функций   ***/

// Формирование первого элемента дерева

Node  *first (const int d)

  {

  Node *pv = new Node;

  pv->d = d; pv->left = 0; pv->right = 0;

  return pv;

  }

// Поиск с включением

Node *search_insert (Node *root, const int d)

  {

  Node *pv = root, *prev;

  bool  found = false;

  while (pv && !found)

     {

     prev = pv;

     if  (d == pv->d) found = true;
     
else if (d < pv->d) pv  = pv->left;
     
else v = pv->right;

     }

  if (found) return pv;  // Искомый узел найден

  //  Не найден - создать новый узел

  Node *pnew = new Node;

  pnew->d = d; pnew->left = 0; pnew->right = 0;

  if (d < prev->d) prev->left = pnew;      // Присоединение к левому поддереву предка

  else prev->right = pnew;                       // Присоединение к правому поддереву предка

  return  pnew;

  }

// Рекурсивный обход дерева

void  print_tree (Node *root, const int level)

  {

  if (pr)

     {

     print_tree (root ->left, level +1); // Вывод левого поддерева 

     for (int i = 0; i < level; i++) cout << "   ";   //  Сдвиг позиции соответственно уровню

     cout <<  root ->d << endl;  // Вывод корня поддерева

     print_tree (root ->right, level +1); // Вывод правого поддерева

     }

  }

    Рассмотрим подробнее функцию обхода дерева print_tree. Вторым параметром в нее передается целая переменная, определяющая, на каком уровне находится узел. Корень находится на уровне 0. Дерево печатается по горизонтали так, что корень находится слева. Перед значением узла для имитации структуры дерева выводится количество пробелов, пропорциональное уровню узла. Если закомментировать цикл печати пробелов, отсортированный по возрастанию массив будет выведен в столбик.

    Удаление узла дерева представляет собой не такую простую задачу, поскольку удаляемый узел может быть корневым, содержать две, одну или ни одной ссылки на поддеревья. Для узлов, содержащих меньше двух ссылок, удаление тривиально. Чтобы сохранить упорядоченность дерева при удалении узла с двумя ссылками, его заменяют на узел с самым близким к нему ключом. Это может быть самый левый узел его правого поддерева или самый правый узел левого поддерева. Например, чтобы удалить из дерева на рисунке узел с ключом 25, его можно заменить на 20 или 28, узел 10 заменяется на 9 или 20, и т. д. Реализация функции удаления оставлена для самостоятельной работы.

4.9.3.5. О применении массивов

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

    Так можно, например, реализовать стек. Кроме массива элементов, соответствующих типу данных стека, достаточно иметь одну переменную целого типа для хранения индекса элемента массива в вершине стека. При помещении в стек индекс увеличивается на единицу, а при выборке – уменьшается. Для работы очереди понадобятся две переменные целого типа – для хранения индексов начала и конца очереди.

    Для реализации линейного списка требуется вспомогательный массив целых чисел и еще одна переменная, например:

10   25   20    6   28    8    1    30    7    9   (массив данных)

 1     2     3    4     5    6    7     8     9   -1   (вспомогательный массив)

0   (индекс первого элемента в списке).

При таком представлении списка i-й элемент вспомогательного массива содержит для i-гo элемента массива данных индекс следующего за ним элемента списка. Отрицательное число используется в качестве признака конца списка. Тот же массив после сортировки:

10   25   20    6   28    8    1    30    7    9   (массив данных)

 2     4     1    8     7    9    3   -1     5    0   (вспомогательный массив)

6   (индекс первого элемента в списке).

Для создания бинарного дерева можно использовать два вспомогательных массива (индексы вершин его левого и правого поддерева). Отрицательное число используется как признак пустой ссылки. Например, рассмотренное в предыдущем пункте дерево можно представить следующим образом:

10   25   20    6   28     8    1    30    7    9   (массив данных)

 3     2   -1     6    -1    8   -1     4    -1  -1   (левая ссылка)

 1     7   -1     5    -1    9   -1    -1    -1  -1   (правая ссылка)

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

struct  Node

  {

  Data  d;     // тип данных Data должен быть определен ранее

  int  i;

  }:

const  int  N = 1000;

Node  listl [N];        // на этапе компиляции

……………………………………………………..

Node *plist2 = new  Node [N]; // на этапе выполнения

 

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

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


28

9

7

30

20

8

1

25

6

10




1. ТЕЛЕРЕМОНТ 1
2. Реферат Техника и технология Выполнил Проверил
3. ru Все книги автора Эта же книга в других форматах Приятного чтения Григорию Лукьяновичу Ску
4. это определенная форма или определенный способ организации государства закрепленный в его конституции.html
5. Общая биология
6. темах Тема- Построение концептуальных моделей представления знаний о технологии стандарта IEEE 802
7. восстанавливающий укрепляющий подразумевают группу лекарственных средств возбуждающих в первую очередь.
8. Реферат- Наследование по римскому праву
9. 1мозговидное набухание лимф тк 2некротизация лимф тк 3отторжение некротических язв 4стадия чистых язв 5ре
10. Метрология, стандартизация, сертификация
11. ТЕМА- ХІМІКОТОКСИКОЛОГІЧНИЙ АНАЛІЗ АЛКАЛОЇДІВ План лекції 1
12. Внешнеторговая деятельность Республики Корея
13. тема поведения предприятия П на длительный период времени означающая выбор одного из альтернативных
14. Преобразите свой участок без значительных затрат сил и времени Идея 1- Водные процедуры Искусственн
15. Научнотехнический прогресс и потенциал предприятия
16. Казанский университет
17. Тема 7 Разрешение земельных споров ПЛАН Понятие земельных споров и их классификация
18. АМЕРИКАНСКИЙ ИНСТИТУТ ИНФОРМАЦИОННЫХ РЕСУРСОВ ИРИ
19. Кабеля для компьютерной сети
20. тема измерения не имеет значения и там он приобретает уже совсем иной смысл