69121

Дерева. Основні поняття. Алгоритм роботи з бінарними деревами

Лекция

Информатика, кибернетика и программирование

Розглянуті у розділі 10.2 списки, стеки та черги палежать до лінійних динамічних структур даних. Визначальною характеристикою лінійних структур є те, що зв’язок між іншими компонентами описується в терминах «попередній-наступний», тобто для кожного компонента лінійної структури...

Украинкский

2014-09-30

80 KB

22 чел.

Лекція 30. Тема: Дерева. Основні поняття. Алгоритм роботи з бінарними деревами.

План:

1. Дерева

2. Основні поняття

3. Алгоритм роботи з бінарними деревами

1. Дерева

Розглянуті у розділі 10.2 списки, стеки та черги палежать до лінійних динамічних структур даних. Визначальною характеристикою лінійних структур є те, що зв’язок між іншими компонентами описується в терминах «попередній-наступний», тобто для кожного компонента лінійної структури визначено не больше одного попереднього та не більше одного наступного компонента. Деревоподібна структура даних або дерево, є нелінійною структурою, що зображує ієрархічні зв’язки типу «предок-нащадок»: компонент-предок може мати батато нащадкыв, хоча для кожного компонента-нащадка визначено не быльше одного предка

2. Основні поняття

Згідно з рекурсивним означенням, дерево з базовим типом Т - це або порожня структура, або вузол типу Т, з яким зв'язана скінченна кількість дерев із базовип типом Т, що їх називають піддеревами [5]. Із означення випливає, що піддерева (гілки) будь-якого вузла не перетинаються, тобто не мають спільних вузлів. Ця властивість розглядуваних структур і споріднює їх із справжніми деревами, адже гілки дерева «зростатися» не можуть. Наведемо графічне зображення дерева.

Вузол дерева, який не має предків,називається коренем. Серед будь-якої пари безпосередньо зв’язаних вузлівдерева можна виділити предка та нащадка. Нащадок є коренем певного піддерева предка. Вважається, що корінь дерева розташований на першому рівні. Кожний вузул нащадок рівня k має предка на рівні k-1. Максимальний рівень дерева називається його глибиною або висотою. Наприклад на рис.10.14 зображено дерево, глибина чкого дорівнює трьом. Вузол дерева, який не має нащадків, називається листком. Кількість беспосередніх нащадків вузла називається його степенем. Максимальний степінь вузла у першому дереві називається степенем дерева.

У даному підручнику розглядають лише бінарні дерева, тобто дерева, степінь яких не перевищує двох. Отже, будь-який вузол бінарного дерева може бути зв’язаним не більше ніж із двома піддеревами, що називаються лівим і правим піддеревами вузла. Оголосимо тип вузла бінарного дерева на мові Pascal.

type ptr=^Node;   {тип покажчика на вузол дерева}

       Node=record      {тип вузла дерева}

         data:string;      {інформаційне поле вузла}

         left,right:ptr;   {покажчик на ліве та праве піддерево}

 end;

Для листів покажчика left та right мають значення nil. Приклад бінарного дерева як структури даних  наведено на рис.10.15.

3. Алгоритм роботи з бінарними деревами

Найпоширенішими операціями під час роботи з деревами є: створення дерева включення вузла в дерево, видалення вузла з дерева, обхід дерева та пощук у ньому. Розглянемо алгоритми цих операцій детальніше на прикладі бінарних дерев.

Створення бінарного дерева

Найпростіший спосіб побудови бінарного дерева полягає у створенні дерева симетричної структури із наперед відомою кількістю вузлів. Усі вузли-нащадки, що створюються, рівномірно розподіляються зліва та справа від кожного вузла-предка.  При цьому досягається мінімально можлива глибина для заданої кількості вузлів дерева. Правило рівномірного розподілу п вузлів можна визначити рекурсивно:

+   перший вузол вважати коренем дерева;

+   створити ліве піддерево з кількістю вузлів nleft=n div 2;

+   створити праве піддерево з кількістю вузлів nright=n-nleft - 1.

Приклад 10. 6

Створимо бінарне дерево із заданою користувачем кількістю вузлів. Тип вузла (компонента) дерева було оголошено у розділі 10.3.1. Оскільки структура дерева визначена рекурсивно, то для його створення та відображення можна розробити рекурсивні підпрограми.

Функція створення дерева tree отримує один цілочисловий параметр AmountNode, що визначає кілъкістъ вузлів дерева та повертає покажчик на його корень. Якщо кількість вузлів дорівнює нулю, дерево порожне, а отже, виконано умову завершення рекурсії і функція має повернути значення nil. Якщо кількістъ вузлів дерева відрізняєтъся від нуля, необхідно виділити пам'ять для кореня дерева, за наведеними вище формулами обчислити кількістъ вузлів у лівому та правому піддеревах і двічі рекурсивно викликати функцію tree для створення піддерева. Для посилання на корінь дерева використаємо локальний покажчик newnode. Значения покажчиків на корені піддерев, що їх повертатиме функція tree в результаті рекурсивних викликів, слід присвоїти полям left та right змінної newnode^.

Дерево відображатиме рекурсивна процедура printtree. Піддерево рівня L виводитиметься так: спочатку буде відображене ліве піддерево, потім - корінь піддерева рівня L, перед яким буде виведено L пробілів, далі - праве піддерево. Приклад створюваного програмою ех10_6 дерева зображено на рис. 10.16 і 10.17. Дерева такого типу називають синтаксичними деревами арифметичних виразів.

program ex10_6;    {створення та відображення бінарного дерева}

type ptr=^node;       {тип покажчика на вузол дерева}

       node=record       {тип вузла дерева}

                 data:string;  {інформаційне поле вузла}

                 left          {покажчик на ліве піддерево}

                 right:ptr;    {покажчик на праве піддерево}

            end;

var n: integer;     {кількість вузлів дерева}

      root:ptr;    {покажчик на корінь дерева}

{==============створення бінарного дерева=================}

function Tree(AmountNode:integer):ptr;

{AmountNote – кількість вузлів дерева, ptr – покажчик на корінь дерева}

var newnode:ptr;     {покажчик на новий вузол}

     LeftNodes          {кількість вузлів у лівому}

     RightNodes:integer; {і правому піддеревах}

     Str:string;   {інформаційне поле вузла}

begin

    if AmountNode = 0 then    {якщо вузлів немає}

        tree:=nil         {дерево порожне}

     else

     begin

       LeftNodes:=AmountNode div2;  {кількість вузлів у піддеревах}

       RightNodes:=AmountNode – LeftNodes – 1;

       write(‘Enter node data:’);

       readln(str);

       new(newnode);   {виділити  пам’ять для нового вузла }

       with newnode^ do

       begin

          data:=str;   {задати інформаційне поле вузла}

                                {створити ліве піддерево}

          left:=Tree(LeftNodes);

                                                {створити праве піддерево}

          right:=Tree(RightNodes);

      end;

      Tree:=newnode;      {значення, що повертається}

    end;

end;

{=============відображення дерева===================}

prpcedure Printtree(RootTree:ptr;L:integer);

{Roottree – покажчик на корінь дерева; L - номеррівня}

var i:integer;     {параметр циклу}

begin

  if RootTree<>nil then    {дерево не порожне}

      with RootTree^ do

      begin

        Printtree(left,L+1);   {вивести ліве піддерево}

        for i:=1 to L do write (‘ ‘);

        writeln(data);   {вивести значення вузла}

        Printtree(right,L+1);    {вивести праве піддерево}

     end;

end;

{============основна програма=================}

begin

  writeln(‘Create and display tree’);

  writeln(‘Enter number of tree’ ‘s nodes’);

  readln(n);            {задати кількість вузлів дерева}

  root:=Tree(n);     {створити дерево}

  writeln(‘Created tree’);

  Printtree(root,0);   {відобразити дерево}

  readln;

end.

Обхід дерева

Алгоритм доступу до всіх вузлів дерева називається обходом дерева. Трьома основними способами обходу дерева є обхід зверху вниз, зліва направо та знизу вверх. Якщо при обході дерева, що зображене на рис. 10.17, ми виписуватимемо значення його вузлів у тому порядку, в якому вони трапляються під час обходу, то отримаємо посшдовності символів, наведені в табл. 10.1.

Спосіб обходу                                  Послідовність символів

Зверху вниз                                       * +ab – cd

Зліва направо                                     a + b * c – d

Знизу вверх                                         ab + cd - *

У результаті обходу синтаксичного дерева зверху вниз утворюється префіксна форма виразу, при обході знизу вверх - постфіксна форма, а при обході зліва нараво - інфіксна форма. Будь-який спосіб обходу дерева можна реалізувати рекурсивною процедурою. Такі процедури наведені у прикладі 10.7. Приклад 10.7

Розробимо три рекурсивні процедури обходу бінарного дерева. До цих процедур передаєтъся параметр-значення, що є покажчиком иа корінь дерева. Тіло всіз трьох процедур містить однаковий набір операторів. Першою виконується перевірка того, чи не є дерево порожнім. Якщо дерево порожне, здійснюєтъся рекур сивне повернення, а в іншому разі виводиться значення вузла і рекурсивно викликаються процедури обходу для лівого та правого піддерев. Порядок цих трьох операторів і визначає форму виразу, що буде створений у результаті обходу. А саме, якщо виведення значення вузла виконуватиметься першим, то буде отримано префіксну форму виразу, якщо другим - інфіксну, а якщо третім - постфіксну форму. Наведемо коди процедур обходу дерева.

{===============обхід дерева зверху вниз================}

procedure Prefixorder(RootTree:ptr);

begin

   if RootTree<>nil then

   begin

      write(RootTree^.data,’ ‘);

      Prefixorder(RootTree^.left);

      Prefixorder(RootTree^.right);

 end;

end;

{===========обхід дерева знизу вверх====================}

procedure Postfixorder(RootTree:ptr);

begin

   if RootTree<>nil then

   begin

      Postfixorder(RootTree^.left);

      Postfixorder(RootTree^.right);

      write(RootTree^.data, ‘ ‘);

   end;

end;

{================обхід дерева зліва направо==============}

procudure Infixorder(RootTree:ptr);

begin

   if RootTree<>nil then

   begin

     Infixorder(RootTree^.left);

     write(RootTree^.data, ‘ ‘);

     Infixorder(RootTree^.right);

   end;

end;

В основній програмі обходу дерева необхідно здійснити виклик щойно записаних процедур після виклику функції створення дерева. Результати роботи програми, у якій створюється дерево та виконується йога обхід, зображено на рис.10.18

{основна програма обходу дерева}

begin

    writeln(‘Create and display tree’);

    writeln(‘Enter number of trees nodes’);

    readln(n);     {ввести кількість вузлів}

    root:=Tree(n);   {створити дерево}

    writeln(‘Created tree’);

    Printtree(root,0);    {ввести дерево}

    writeln;

    writeln(‘prefixorder traversal’);

    Prefixorder(root);    {обхід зверху вниз}

    writeln;

    writeln(‘postfixorder traversal’);

    Postfixorder(root);     {обхід знизу вверх}

     writeln;

    writeln(‘infixorder traversal’);

     Infixorder(root);   {обхід зліва направо}

     writeln;

     readln;

end.

Дерева бінарного пошуку

Бінарні дерева часто використовуються для зображення множин, елементи яких потрібно знаходити за заданим значенням ключа. Такі дерева називаються деревами бінарного пошуку. Особливість подібного дерева полягає в тому, що для будь-якого його вузла х значення всіх вузлів лівого піддерева х не більші за значення х, а значення всіх вузлів правого піддерева х не менші за значення х. Така властивість називається впорядкованістю ключів у дереві.

Вузол із заданим значенням ключа буде знайдений доволі швидко, якщо спускатися від кореня дерева бінарного пошуку за таким правилом: ліве піддерево обирається тоді, коли значення розглядуваного вузла більше за шукане, а праве піддерево – тоді, коли вказане значення менше за шукане. Якщо значення вузла дорівнює шуканому, пошук слід завершити. Якщо пошук привів до порожньої гілки дерева, то ключового значення в дереві немає. Легко зрозуміти, що для знаходження за таким алгоритмом значення ключа серед n-елементної множинибуде переглянуто О(log n) елементів.

Приклад 10.8

Розробимо функцію знаходження ключового значення в бінарному дереві пошуку. До функції передається ключове значення і покажчик на корінь дерева, а повертає функці покажчик на вузол, значення якого дорівшоє шуканому. Як ознаку успішності пошуку використаємо логічну змінну found. Пошук починається з кореня дерева, триває доти, доки шукане значення не буде знайдене або доки всі вузли дерева не будутъ перевірені.

function location(key:string;RootTree:ptr):ptr;

{key – ключове значення}

{RootTree – покажчик на шуканий вузол}

var found:boolean;      {ознака успішності пошуку}

begin

  found:=false;

  while(RootTree<>nil) and (not found) do

{цикл триває доти, доки і листа не досягнуто, і ключового значення не знайдено}

   begin

      if RootTree^.data=key   {перевірити значення вузла}

          then found:=true      {значення знайдено}

          else if RootTree^.data>key     {значення не знайдено}

                 then RootTree:=RootTree^.left

                 else RootTree:=RootTree^.right;

    end;

    location:=RootTree;

end.

В основній програмі здійснюється виклик функцій пошуку потрібного значення вузла дерева. Щоб повторит пошук вузла, необхідно використати оператор циклу, який припинить свою роботу після натискання клавіші N.

{=================основна програма======================}

var n:=integer;   {кількість вузлів дерева}

     root:ptr;      {покажчик на корень дерева}

     keyfound:string;    {шукане значення вузла}

     rootfound:ptr;    {покажчик на шуканий вузол}

     сh:char;     {код натиснутої клавіші}

begin

    writeln(‘Create and display tree’);

    writeln(‘Enter number of tree ‘’ s nodes’);

    readln(n);   {ввести кількість вузлів}

    root:=tree(n);   {створити бінарне дерево}

    repeat

       writeln(‘Enter key to search’);

       readln(keyfound);      {ввести ключ пошуку}

       rootfound:=location(keyfound,root);  {виконати пошук}

       if rootfound<>nil         {якщо вузол знайдено}

            then writeln(‘found:’,rootfound^.data)

            else writeln(‘not found’);

       writeln(‘continue?y/n’);   {запит на продовження}

        ch:=readkey;   {пошуку}

    until ch=’n’;

end.

Включення вузлів у дерево

Перейдемо до розгляду дерев змінної структури, тобто таких дерев, кількість елементів яких піщ час роботи певної програми може збільшуватися або зменшуватися. Дерева змінної структури можна використовувати, зокрема, при створенні частотного словника. Задача створення  частотного словника формулюється так: потрібно визначити, скільки разів зустрічається кожне слово в заданій послідовності слів.

Послідовність слів можна зобразити у вигляді дерева бінарного пошуку. В інформаційних полях вузла такого дерева зберігатиметься слово і кількість його повторень. У разі виявленяя в тексті чергового слова дерево переглядають, починаючи з кореневого вузла. Якщо слово в дереві знайдене, то лічильник його повторень збільшується. Але якщо слово в дереві не знайдене, воно включається в дерево із значенням лічильника, що дорівнює 1. Дану задачу називають іще пошуком із включенням.

Включення вузла в дерево має здійснюватися так, щоб не порушувалася властивість упорядкованності ключів. Це правило буде дотримане, якщо застосувата розглянутий вище алгоритм знаходження ключового значення у бінарному дереві пошуку, а  включення нового елемента здійснювати тоді, коли пошук завершився безуспішно. У прикладі 10.9 буде реалізований рекурсивний варіант алгоритму пошуку із включенням.

Приклад 10.9

У програмі, що реалізує пошук із включенням, компоненти бінарного дерева містить два інформаційні поля: поле рядкового типу для збереження слова та цілочислове поле для збереження кількості повторень слова. Наведемо оголошення типу такого компонента разом із оголошеннями використаних у програмі глобальних зміних:

type ptr=^node;

       node=record

                   data:string;   {значення, що включається в дерево}

                   count:integer;    {кількість повторень значень}

                   left,right:ptr;  {покажчики на ліве та праве}

              end;     {піддерева}

var n:integer;        {кількість вузлів дерева}

     root:ptr;     {покажчик на корень дерева}

     searchkey:string;   {шукане слово}

     ch:char;    {символ, що позначає кінець процесу пошуку}

 Запишемо код процедури SearchInsert, призначеної для пошуку та включення вузла у бінарне дерево, і код основної програми. Шукане слово передаватимемо до згаданої процедури через параметр-значення key, а покажчик на корень дерева — через параметр-змінну RootTree. Після того як роботу процедури SearchInsert буде завершено, покажчик RootTree посилатиметься на знайдений вузол. На рис. 10.20 зображено результата роботи програми пошуку із включенням. Як бачите, етап введення даних на ньому не показано.

Розглянемо задачу видалення вузла бінарного дерева пошуку. Можливі три випадки: вузол, що видаляється, не має нащадків, тобто є листком дерева; вузол, що видаляється, має одного нащадка; вузол, що видаляється. має двох ващадків.

Задача розв'язується найпростішим способом тоді, коли вузол, що видялаєтъся, є листком дерева. У такому разі слід звілънити ділянку динамічної пам'яті, яку цей вузол займав, та присвоїти значення nil покажчикові на даний вузол.

Якщо видаляється вузол х, який має одного нащадка, то покажчику на цей вузол слід присвоїти адресу його нащадка і звільнити пам'ять, яку вузол х займав. Операцію видалення вузла, що має одного нащадка проілюстрований рис. 10.21.

Найскладнішим є випадок, коли вузол х, що видаляється, має двох нащадків. У цьому разі на місце х слід переставити  вузол дерева так, щоб не порушувалася властивістъ впорядкованості ключів. Вузол, що переставляєтъса, I еться термгшльним. Один \э спосоо!в внзначення термшального ву-= виконанн! спуску по правей гтщ левого пидерева л доти, докв вузла без правого нащадка. Цей вузол 1 е термшалъним, Спраади:— —. вузла не менше за значения вс!х вузлгв лхвого тддерева л; оскільк ж вш н прав!й плц! цього пщдерева 1 не мае правого нащадка, 3 шшого боку, знайденого в такий спосіб вузла не йлыие за значения ВС1Х вузлш правого П(д. дерева х, осюлькя виг наложить л.вому шддереву х. А отжс, значения зпайде1,ого вузла може бути записано до вузла х без порушення впорядкованост] ключ1в. Сам термшальний вузол мае бути видалений шсля котюваиня його значения до вуэ.

Контрольні питання

1. Дерева

2. Основні поняття

3. Алгоритм роботи з бінарними деревами


 

А также другие работы, которые могут Вас заинтересовать

20625. Мегамир. Основные космогонические представления 81.5 KB
  Звезды их характеристики источники энергии2. Звезды их характеристики источники энергии Более 90 видимого вещества Вселенной сосредоточено в звездах. Именно звезды и планеты были первыми объектами астрономических исследований. Пожалуй лишь диск нашего солнца позволяет реально наблюдать процессы происходящие на поверхности звезды.
20626. Мегамир, основные космогонические представления 107 KB
  Имеются многочисленные данные подтверждающие предположение что звезды образуются при конденсации облаков межзвездной пыли и газа. Глобула становится зародышем будущей звезды протозвездой и начинает светиться так как энергия движения частиц переходит в тепло. Дальнейшее сжатие протозвезды приводит к такому повышению температуры и давления что становятся возможными термоядерные реакции синтеза гелия из водорода. При этом силы тяготения стремящиеся сжать вещество звезды уравновешиваются силами внутреннего давления.
20627. Химическая эволюция Земли 81.5 KB
  Общая теория химической эволюции и биогенезаТеории возникновения жизниГипотеза ОпаринаХолдейна Контрольные вопросыЛитература Ранее уже говорилось о том что использование ЭВМ позволило строить и рассчитывать образование и развитие солнечной системы и Земли в частности на различных моделях. Химическая эволюция Земли В процессе эволюции Земли складывались определенные пропорции различных элементов. Земля наиболее массивная среди внутренних планет прошла сложнейший путь химической эволюции. Следует подчеркнуть что геологическая история Земли...
20628. Специфика живого 72 KB
  Предмет изучение задачи и методы биологииТри образа биологииАксиомы биологии 2. Предмет изучения задачи и методы биологии Биология совокупность или система наук о живых системах. Предмет изучения биологии все проявления жизни а именно: строение и функции живых существ и их природных сообществ; распространение происхождение и развитие новых существ и их сообществ; связи живых существ и их сообществ друг с другом и с неживой природой. Задачи биологии состоят в изучении всех биологических закономерностей и раскрытии сущности жизни.
20629. Термодинамика живых систем. Жизнь как информационный процесс 76.5 KB
  Термодинамика живых систем Состояние живых систем в любой момент времени динамическое состояние характерно тем что элементы системы постоянно разрушаются и строятся заново. Это означает что живые системы обязательно должны быть открытыми системами. Именно на этом неравновесии основана работоспособность живой системы направленная на поддержание высокой упорядоченности своей структуры а. Переход живо системы в такое состояние означает для нее смерть.
20630. Концепция эволюции в биологии 87 KB
  Концепция эволюции в биологии 1. Современная синтетическая теория эволюцииОсновные законы эволюцииОсновные факторы эволюцииФормы естественного отбора Контрольные вопросыЛитература Под эволюцией подразумевается процесс длительных постепенных медленных изменений которые в конечном итоге приводят к изменениям коренным качественным завершающимся образованием новых систем структур и видов. Представления об эволюции в естествознании имеют ключевое значение. [1] Парадигма современного естествознания это эволюционносинергетическая...
20631. Человек. колого-эволюционные возможности человека 110.5 KB
  Место человека в системе животного мира и антропогенез2. Основные этапы развития Человека Разумного3. Экологоэволюционные возможности человека5. Место человека в системе животного мира и антропогенез Вопрос о происхождении человека имеет не только научное значение: с позиций эволюционной биологии или чисто зоологической точки зрения это частный филогенетический вопрос.
20632. Биосфера и цивилизация 72.5 KB
  Живые организмы входящие в состав биоценоза неодинаковы с точки зрения специфики ассимиляции ими вещества и энергии из ОС. Совокупность множества параметров среды определяющих условия существования того или иного вида и его функциональных характеристик преобразование им вещества и энергии обмен информацией со средой и с себе подобными и др. Энергетика основа цивилизации и без производства достаточного количества энергии человечество не сможет существовать и развиваться. Сегодня главный производитель энергии теплоэлектростанции ТЭС...
20633. Основные концепции и перспективы биотехнологии 120.5 KB
  Расшифровка генома человека3. Пастер выяснивший роль микроорганизмов в брожении виноделие пивоварение и в возникновении болезней животных и человека. Исключительное значение для борьбы с заразными болезнями имел предложенный Пастером метод предохранительных прививок основанный на введении в организм животного или человека ослабленных культур болезнетворных микроорганизмов. Медицинская микробиология исследует микроорганизмы вызывающие заболевания человека и разрабатывает эффективные методы борьбы с ними.