4286

Основные понятия бинарных деревьев

Лекция

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

Бинарные деревья Рассмотрим структуры данных, определяемые с помощью рекурсии. Среди них наиболее важными являются деревья. Деревья имеют широкое применение при реализации трансляторов таблиц решений, при работе с арифметическими выражениями, при со...

Русский

2012-11-15

92.5 KB

56 чел.

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

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

Основные понятия и определения.

Древовидная структура (дерево) определяется следующим образом: дерево (tree) с базовым типом Т – это:

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

Если с узлом связаны только два поддерева, то дерево называется бинарным. В дальнейшем мы будем рассматривать только бинарные деревья. Бинарное дерево изображено на рис.1.

Рис.1. Представление бинарного дерева

Терминология, применяемая для описания деревьев:

  •  узел (node) – это точка, где может возникнуть ветвь. На рис.1 узлы – это, например, 70 и 200 и т.д;
  •  корень (root) – “верхний” узел дерева. Для дерева на рис.1 это узел 100;
  •  ветвь (brunch) –отрезок, описывающий связь между двумя узлами;
  •  лист (leaf) – узел, из которого не выходят ветви, т.е. не имеющий поддеревьев. На рис.1 это узлы 10, 90, 58, 65, 170, 210;
  •  родительским (parent) – называется узел, который находится непосредственно над другим узлом;
  •  дочерним (child) – называется узел, который находится непосредственно под другим узлом;
  •  предки данного узла – это все узлы на пути вверх от данного узла до корня. Например, предками узла 60 являются узлы 55, 50, 70, 100;
  •  потомки – все узлы, расположенные ниже данного. Для узла 55 потомками являются узлы 60, 58, 65;
  •  внутренний узел (internal node) – узел, не являющийся листом;
  •  порядок узла (node degree) – количество его дочерних узлов;
  •  глубина (depth) узла количество его предков плюс единица;
  •  глубина (высота) дерева –максимальная глубина всех узлов;
  •  длина пути к узлу – количество ветвей, которые нужно пройти, чтобы дойди от корня к данному узлу;
  •  длина пути дерева(длина внутреннего пути) – сумма длин путей всех его узлов.

Основные операции с бинарными деревьями

Узел бинарного дерева

При определении узла бинарного дерева в Delphi-программе нам требуются две связи (т.е. указатели) с его дочерними узлами и фактические данные (информационная часть), которые должны храниться в узле. При работе программы дерево может модифицироваться: добавляются или удаляются узлы, изменяется информационная часть. То есть дерево является динамической структурой. Узел дерева можно описать как переменную с фиксированной структурой, содержащую информационную часть (например, целое число) и две ссылки, указывающие на левое и правое поддеревья данного узла. Для этого подойдет тип – запись (record). Ссылка на пустое дерево должна быть равна nil.

Описание узла дерева может выглядеть так:

type  PTree = ^TTree;  // указатель на узел дерева

 TTree = record

 Inf: integer; // информационная часть (тип может быть любой и зависит от задачи)

 Left, Right:PTree; // указатели на левое и правое поддеревья

 end;

Обход бинарного дерева.

 

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

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

 

Существуют три порядка, использующие обход в глубину:

  1.  Сверху вниз (PreOrder):
    •  обработать корень;
    •  обход левого поддерева;
    •  обход правого поддерева;

  1.  Слева направо (InOrder):
    •  обход левого поддерева;
    •  обработать корень;
    •  обход правого поддерева;

  1.  Снизу вверх (PosOrder):
    •  обход левого поддерева;
    •  обход правого поддерева;
    •  обработать корень.

Для дерева на рис.1 три способа обхода дают следующий результат:

Обход

Порядок посещения узлов

PreOrder

100

70

50

10

55

60

58

65

90

150

200

170

210

InOrder

10

50

55

58

60

65

70

90

100

150

170

200

210

PosOrder

10

58

65

60

55

50

90

70

170

210

200

150

100

Эти три метода легко представить в виде рекурсивных процедур, листинг которых представлен ниже. Во всех процедурах в качестве обработки корня используется вывод значения информационного поля на экран. В качестве параметра Tree:PTree в процедуры передается адрес корня бинарного дерева.

Листинг процедур обхода бинарного дерева.

Procedure PrintTree(Tree: PTree);  // PreOrder

begin

 if Tree<>nil then begin   // если дерево не пустое, то

 Writeln(‘Value = ‘,Tree^.inf); // обработать узел

 PrintTree(Tree^.Left); // обход левого поддерева

 PrintTree(Tree^.Right); // обход правого поддерева

 end;

end;

Procedure PrintTree(Tree: PTree);  // InOrder

begin

 if Tree<>nil then begin   // если дерево не пустое, то

 PrintTree(Tree^.Left); // обход левого поддерева

 Writeln(‘Value = ‘,Tree^.inf); // обработать узел 

 PrintTree(Tree^.Right); // обход правого поддерева

 end;

end;

Procedure PrintTree(Tree: PTree);  // PosOrder

begin

 if Tree<>nil then begin   // если дерево не пустое, то

 PrintTree(Tree^.Left); // обход левого поддерева

 PrintTree(Tree^.Right); // обход правого поддерева

 Writeln(‘Value = ‘,Tree^.inf); // обработать узел

 end;

end;

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

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

 

Упорядоченным называется дерево, в котором для каждого узла N значение левого дочернего узла меньше, чем значение в N, а значение правого дочернего узла больше значения в N. Если в дереве могут содержаться одинаковые значения, то программист должен самостоятельно определить, влево или  вправо помещать значение, равное  значению в родительском узле (строгое неравенство заменить на нестрогое).

Построение упорядоченного дерева начинается с корня. Первое входящее значение помещается в корень дерева. Для последующих значений производиться сравнение со значением в очередном узле, начиная с корня. Если оно меньше (или равно) значению в узле, то переходим в левое поддерево, иначе – в правое. Эти переходы и сравнения продолжаются  до тех пор, пока мы не придем к ссылке, которая равна nil. Тогда создается новый узел, заполняются его поля: информационное - новым значением, ссылки на левое и правое поддеревья  пустым значение nil. Адрес нового узла передается в одно из ссылочных полей родительского узла. Для этого необходимо воспользоваться параметром-переменной. Этот алгоритм реализован в виде рекурсивной процедуры Insert.

Рис.2 Добавление нового узла в упорядоченное дерево.


Листинг процедуры добавления нового узла в упорядоченное дерево.

{Параметры процедуры: Tree – указатель на корень дерева, NewValue – значение для добавляемого узла.}

Procedure Insert(var Tree:PTree; NewValue:integer);

var Temp:PTree;

begin

 if Tree = nil then begin

 new(Tree); // создание нового узла, в том числе и корневого

 Tree^.inf:=NewValue; Tree^.Left:=nil; Tree^.Right:=nil; // заполнение полей

 end

 else

  if NewValue <=Tree^.inf then

     Insert(Tree^.left,NewValue)

     {переход к левому поддереву}

    else

     Insert(Tree^.Right,NewValue)

     {переход к правому поддереву}

end;

Следует отметить, что в процедуре Insetr параметр Tree передается как параметр-переменная, а не как параметр-значение в процедуре PrintTree. Это очень важно, так как в случае включения нового узла параметру-переменной Tree присваивается адрес нового узла и  через нее передает в родительский  узел ссылкы (адрес) на включенный узел, изменяя старое значение равное nil. Само по себе создание бинарного дерева тривиально. В простейшем случае корневой узел бинарного дерева определяет все бинарное дерево. В программе необходимо описать указатель на корень дерева (например, var Root:PTree;). В начале программы необходимо провести инициализацию бинарного дерева – указателю на корень присвоить пустое значение (Root:=nil;). Бинарного дерева не существует, поэтому это пустое значение служит начальным значением бинарного дерева. Добавление новых элементов в дерево будем осуществлять процедурой Insert. Например, добавление числа Х в бинарное дерево будет выглядеть так: Insert(Root,X). Вывод на экран содержимого дерева можно записать процедурой  PrintTree(Root).

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

Procedure PrintTree1(Tree: PTree);  // InOrder

begin

 if Tree<>nil then begin   // если дерево не пустое, то

 PrintTree1(Tree^.Right); // обход правого поддерева

 Writeln(‘Value = ‘,Tree^.inf); // обработать узел 

 PrintTree1(Tree^.Left); // обход левого поддерева 

 end;

end; 

Упорядоченные деревья. Поиск заданного значения.

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

Функция Find осуществляет поиск узла со значением равным параметру Х. Параметр R –указатель на корень дерева, в котором осуществляется поиск. Возвращаемый результат: True – узел со значением Х найден, False – не найден.

Листинг функции поиска в бинарном дереве

Function  Find(R:PTree;X:integer):boolean;

begin

           if R=nil then Result:=false {Дошли до тупика, искать больше негде.}

              else // Указатель на дерево не пуст

                 if R^.inf=X then // Проверяем содержимое на равенство

Result:=True // Узел найден

                    else

                       if  n < R^.inf   then 

find:=find(R^.left,X) // Продолжаем поиск в левом поддереве

                             else

find:=find(R^.right,X); // Продолжаем поиск в правом поддереве

end;

Функцию Find можно записать иначе, изменив тип возвращаемого результата с логического типа  на указатель узла бинарного дерева. В этом случае при успешном поиске получаем адрес найденного элемента, при неудаче – пустой указатель nil.

Удаление бинарного дерева.

После окончания работы с такой динамической структурой как бинарное дерево необходимо высвободить память,  удалив все его узлы. Для удаления узлов бинарного дерева воспользуемся процедурой обхода cнизу вверх (PosOrder). Только такой порядок обхода гарантирует корректное удаление всех узлов (При удалении необходимо освобождать сначала самые крайние дочерние узлы, постепенно переходя на вышележащие родительские уровни. Последним должен быть удален корень дерева). Решает эту задачу процедура DeleteTree. В рекурсивную процедуру передается как параметр-переменная адрес корня дерева. После выхода из процедуры фактический параметр, будет продолжать хранить адрес бывшего корня дерева, но обращение по нему вызовет ошибку. Поэтому, после удаления дерева указателю на корень желательно присвоить значение nil, т.е. провести его повторную инициализацию.    

Листинг процедуры удаления бинарного дерева.

 procedure DeleteTree (var Root: ptelem);

begin

 if r <> nil then

  begin

   DeleteTree (r^.left);

   DeleteTree (r^.right);

   dispose(r);

  end;

end;

Удаление узла из упорядоченного дерева

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

Алгоритм удаления узла с ключом х из упорядоченного дерева реализован процедурой Delete(), приведенной далее.

Процедура обрабатывает три случая:

  •  В дереве нет узла с ключом х.
  •  Узел с  ключом х имеет не более одного сына.
  •  Узел с  ключом х имеет двух сыновей.

Параметры процедуры: x – значение удаляемого узла, Tree – указатель на корень дерева, moving – флаг удаления (moving=True – узел найден и удален, иначе - False)  

Листинг процедуры удаления узла из упорядоченного дерева

Procedure Delete(x:integer; var Tree:PTree; var moving: boolean);

Var q :PTree;

Procedure Del(var R:PTree);

begin

 If R^.Right <> nil then Del(R^.Right)

   else begin

   q^.inf:=R^.inf;

   q:=R; R;=R^.left;

end;

end;

begin

If Tree = nil then moving:=false // узел для удаления не найден 

  else

  If x< Tree^.inf then Delete(x,Tree^.left,moving)

    else

    If x> Tree^.inf then Delete(x,Tree^.right,moving)

   else

begin // удаление узла

Moving:=true; q:=Tree;

    If q^.right=nil then Tree:=q^.left

     else

         If q^.left= nil then Tree:=q^.right

             else

                  Del(q^.left);

Dispose(q);

   end

end;

Вспомогательная рекурсивная процедура Del() вызывается только в случае, когда удаляемый узел имеет двух сыновей. Она “спускается” вдоль самой правой ветви левого поддерева удаляемого узла q^, а затем заменяет ключ в q^ соответствующим значением самого правого узла r^ этого левого поддерева. После чего r^ удаляется. Параметр-переменная moving передает сведения о том, был ли удален требуемый узел. True – узел найден и удален,  false - в противном случае.

Пример использования упорядоченного бинарного дерева для частотного анализа данных

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

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

program testTree;

 {$APPTYPE CONSOLE}

uses

 SysUtils;

type

 PTree = ^Tree;

 Tree = record

   inf, cnt: integer;// поле cnt – счетчик числа повторений

   left, right: PTree;

  end;

var

 root: PTree; // указатель на корень дерева

 n: integer;

procedure Insert (var r: PTree; x: integer); // Процедура поиска и добавления узла

 var

  p: PTree;

begin

 if r = nil then

  begin {Дерево пусто или нашли место добавления}

   new(r);{Создаем и заполняем узел}

   r^.inf := x;

   r^.cnt := 1;{Счетчик повторений устанавливаем в единицу }

   r^.left := nil;

   r^.right := nil;

  end

 else if x < r^.inf then

  Insert(r^.left, x) // Продолжение поиска в лев. поддереве

 else if x > r^.inf then

  Insert(r^.right, x) // Продолжение поиска в прав. поддереве

 else

  r^.cnt := r^.cnt + 1; { нашли узел со значением равным Х – увеличиваем счетчик cnt на единицу}

 end; {Insert}

procedure PrintTree (r: PTree); {Обход и вывод дерева на экран(InOrder)}

begin

 if r <> nil then

  begin

   PrintTree(r^.left);

   writeln('  ', r^.inf : 4, '  ', r^.cnt : 4);

   PrintTree(r^.right);

  end; {if}

end; {PrintTree}

procedure DeleteTree (r: PTree); {Удаление дерева}

begin

 if r <> nil then

  begin

   DeleteTree (r^.left);

   DeleteTree (r^.right);

   dispose(r);

  end;

end; { DeleteTree }

begin {main  program}

root := nil; {Инициализация структуры дерева }

 writeln('Input integers; 777- exit');

 repeat {Читаем числа с клавиатуры до ввода числа 777 и добавляем в дерево}

 write('> ');

 readln(n);

 Insert(root, n);

until n = 777;

 Writeln('Tree sorted contents :');

 Writeln('       Value   Count');

 PrintTree(root); {Печатаем содержимое дерева на экране, сортировка -  по возрастанию значения ключа inf}

 DeleteTree (root); {Удаляем структуру дерева и освобождаем память}

 readln;

end.


Задачи

  1.  Проверить, является ли данное двоичное дерево деревом поиска.
  2.  Дан текстовый файл. Определить частоту использования каждого слова в тексте. Результаты вывести в алфавитном порядке (слово - сколько раз встретилось). Найти наиболее и наименее встречающиеся слова.
  3.  Подсчитать число узлов в заданном двоичном дереве.
  4.  В бинарном дереве хранятся целые числа, определить их среднее значение.
  5.  Дан текстовый файл с целыми числами. Распечатать числа по убыванию. (Использовать бинарное дерево).
  6.  Даны два текстовых файла А и Б. Занести в файл С те слова, которых нет в файле В. Для хранения слов из файла В и ускорения поиска  воспользуйтесь деревом двоичного поиска.
  7.  Даны два текстовых файла А и Б. Занести в файл С те слова, которых есть и в файле А и в файле В.
  8.  Описать логическую функцию, проверяющую на равенство два заданных двоичных дерева.
  9.  Описать логическую функцию, проверяющую, есть ли в заданном двоичном дереве хотя бы два одинаковых элемента.
  10.  Определить сколько раз встречается в упорядоченном бинарном дереве максимальное значение.


 

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

52423. Загальна характеристика Членистоногих 115.5 KB
  Загальна характеристика Членистоногих Мета уроку: ознайомити із загальними рисами типу; відмітити ускладнення організації членистоногих порівняно з кільчаками; з’ясувати їхнє походження; розкрити різноманітність членистоногих їхню роль у природі та житті людини; формувати навички роботи з текстом підручника вміння виділяти головне порівнювати робити висновки; розвивати пізнавальні пошукові та творчі можливості учнів під час створення проектів розвивати вміння презентувати власну роботу; формувати основи екологічного мислення Тип уроку:...
52424. Chocolate is good for you 94.5 KB
  INTRODUCTION t the lesson we re going to tlk with you bout chocolte nd its role nd plce in our life.CHOCOLTE: Wlk round the clss nd tlk to other students bout chocolte. studies fntstic news reserch diet hert ttcks milk chocolte risks suffering stroke nutrition blood pressure weight gin clories sweets snck Hve cht bout the topics you liked.
52425. Чорнобиль не має минулого. Історія Чорнобильської трагедії крізь призму української літератури 72.5 KB
  Історія Чорнобильської трагедії крізь призму української літератури Мета: розширити знання дітей про Чорнобильську трагедію розповісти про ліківідаторів аварії на Чорнобильській АЕС розкрити трагедію ЧАЕС через твори українських письменників; розвивати вміння школярів аналізувати та узагальнювати навчальну інформацію вміння виразно декламувати артистичні здібності; виховувати співчуття до чужого болю любов до рідного краю природи; виховувати людяність доброту згуртованість. Драч Чорнобильська мадонна М. І тихо ступає життя у полин...
52427. Чорнобиль – найбільша трагедія світу 50 KB
  Досліджуючи солі урану він виявив що уран випромінює невидимі промені. фізик і хімік Петербурзької Академії наук невидимі промені назвала радіоактивними а явище випромінювання радіоактивністю. У забруднених зонах спостерігаються масові аномалії тому що радіонукліди потрапивши в організм людини випромінюють радіоактивні промені які руйнують клітини. випромінювання – це потік позитивно заряджених частинок з масою атома Гелію промені – це потік негативно заряджених електронів це потік електромагнітних хвиль подібних до звичайного...
52429. Розпад Радянського Союзу і проголошення незалежності України. (1985 -1991 рр.) 63 KB
  Тип проекту: міжпредметний дослідницько інформаційний творчий груповий. Стадії здійснення проекту: 1. На основі отриманих результатів попередньої підготовки учителі предметники формулюють пізнавальне завдання учасникам проекту виконання яких буде очікуваним результатом та кінцевим продуктом проекту. Повідомляє що проект буде нестандартним оскільки учасникам проекту доведеться проявити свої знання не лише з історії а й з інших наук навчальних предметів.
52430. Систематизація та узагальнення знань учнів з теми “Чотирикутник” 296 KB
  Узагальнити і систематизувати знання учнів про чотирикутники, їх властивості та ознаки. Відпрацьовувати практичні уміння та навички використовувати набуті знання, формувати вміння раціонально використовувати час. Розвивати логічне мислення, вміння аналізувати, робити висновки, геометричну уяву.
52431. Маркетинг у страхуванні 605 KB
  Особливе місце в діяльності страхової компанії відводять маркетингу - методу дослідження страхового ринку і впливу на нього з метою отримання компанією якомога більшого прибутку.