69121

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

Лекция

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

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

Украинкский

2014-09-30

80 KB

15 чел.

Лекція 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. Алгоритм роботи з бінарними деревами


 

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

66320. Три мушкетёра. 10 лет спустя 155 KB
  Школа Равнение на выпускников школы 2009-2010 Звучит Муз 3; выпускники по одному выходят через арку на сцене спускаются в зал девочкам помогает спуститься со сцены юноша и рассаживаются на свои места.: Все стало так как вы хотели И вот настал...
66321. Сказка о попе и работнике его Балде 237.5 KB
  Пушкиным Сказки Пушкина мы читаем в детстве и с уверенностью считаем что до конца разобрались в этом вопросе что никаких загадок в нем больше нет. Практически все сказки в разное время были написаны Пушкиным в имении Болдино.
66322. БАСКЕТБОЛЬНОЕ ШОУ 31 KB
  В нашей программе вы увидите выступление баскетболистов – профессионалов нашей школы конечно это не профессионалы НБА но тем не менее вы сможете увидеть виртуозное ведение мяча точные броски молниеносные передачи
66323. Байки. Езопова байка «Хлібороб і орел» 89.5 KB
  Тема нашого уроку Езопові байки. Що таке байка З яких частин складається байка Що таке мораль Хто є героями байок Як називають авторів байки Яких байкарів знаєте Чим байка відрізняється від казки Гра З якої байки предмет...
66324. Білокора красуня 67 KB
  Як зовуть її Берізка Назва берізка прийшла до нас із глибокої давнини. Чому радіє берізка Що шепоче теплому вітерцю сонечку Складемо казочку Сонечко та Берізка. Послухайте початок: Жила була собі Берізка.
66325. Учитель творить Людину… 54.5 KB
  Учитель знайомить їх із спогадами про свою першу вчительку українського письменника І. Чендеєм Бесіда за змістом Класний керівник: Який загальний настрій цих спогадів На яких спогадах акцентує увагу письменник Чому навчала дітей учителька Який основний урок виніс письменник з її розповідей...
66326. Урок-путешествие в «Огненную страну» 62 KB
  Огонь одно из самых больших чудес природы с которым человек познакомился. Огонь дарил человеку тепло свет защищал от диких зверей. Люди сколько жили на свете Пуще глаза огонь берегли. Ведь огонь в холода в непогоду У костра их всегда согревал.
66327. Безпека вдома. Електроприлади. Безпека під час користування електроприладами 59 KB
  Діти за кожну правильну відповідь маємо можливість із частин збудувати будинок. Та не збагну я діти Хто мені допомагає світити Учитель: Дорога лампочко Не сумуй лапочко Зараз розкажуть діти що відбувається з тобою у світі. То ж запам’ятай лампочко І запам’ятайте діти...
66328. Волшебная страна – библиотека 183.5 KB
  Книги встречают нас с самого раннего детства и сопровождают нас всю жизнь они заставляют нас совершенствоваться. Что же тогда в них хранили Книги Конечно же книги В Египте их писали на папирусе а в Индии составляли их из нарезанных пальмовых листьев в Междуречье выцарапывали на глиняных дощечках.