Реферат по предмету "Информатика"


Динамические структуры данных двоичные деревья

Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.
В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.
Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: O(n) = C • log2n (в худшем случае O(n) = n).
Пример. Для набора данных 9, 44, 0, –7, 10, 6, –12, 45 построить двоичное дерево поиска.
Согласно определению двоичного дерева поиска число 9 помещаем в корень, все значения, меньшие его — на левое поддерево, большие или равные — на правое. В каждом поддереве очередной элемент можно рассматривать как корень и действовать по тому же алгоритму. В итоге получаем
/>
Выделим типовые операции над двоичными деревьями поиска:
добавление элемента в дерево;
удаление элемента из дерева;
обход дерева (для печати элементов и т.д.);
поиск в дереве.
Поскольку определение двоичного дерева рекурсивно, то все указанные типовые операции могут быть реализованы в виде рекурсивных подпрограмм (на практике именно такой вариант чаще всего и применяется). Отметим лишь, что использование рекурсии замедляет работу программы и расходует лишнюю память при её выполнении.
Пусть двоичное дерево поиска описывается следующим типом
Type BT=LongInt; U = ^BinTree; BinTree = Record Inf: BT; L, R: U End;
Покажем два варианта добавления элемента в дерево: итеративный и рекурсивный.
{Итеративный вариант добавления элемента в дерево, Turbo Pascal}
Procedure InsIteration(Var T: U; X: BT);
Var vsp, A: U;
Begin
   New(A); A^.Inf := X; A^.L:=Nil; A^.R := Nil;
   If T=Nil Then T:=A
               Else Begin vsp := T;
                         While vsp Nil Do
                          If A^.Inf
                          Then
                            If vsp^.L=Nil Then Begin vsp^.L:=A; vsp:=A^.L End Else vsp:=vsp^.L
                          Else
              If vsp^.R = Nil Then Begin vsp^.R := A; vsp:=A^.R End Else vsp := vsp^.R;
                      End
End;
{Рекурсивный вариант добавления элемента в дерево, Turbo Pascal}
Procedure InsRec(Var Tree: U; x: BT);
Begin
  If Tree = Nil
  Then Begin  
    New(Tree);
    Tree^.L := Nil;
    Tree^.R := Nil;
    Tree^.Inf := x
End
  Else If x
Then InsRec(Tree^.L, x)
Else InsRec(Tree^.R, x)
End;
Аналогично на C++.
typedef long BT;
struct BinTree{
      BT inf;
      BinTree *L; BinTree *R;
    };
/* Итеративный вариант добавления элемента в дерево, C++ */
BinTree* InsIteration(BinTree *T, BT x)
{ BinTree *vsp, *A;
 A = (BinTree *) malloc(sizeof(BinTree));
 A->inf=x; A->L=0; A->R=0;
 if (!T) T=A;
 else {vsp = T;
while (vsp)
{if (A->inf inf)
    if (!vsp->L) {vsp->L=A; vsp=A->L;}
    else vsp=vsp->L;
 else
    if (!vsp->R) {vsp->R=A; vsp=A->R;}
    else vsp=vsp->R;
}
}
return T;
}
/* Рекурсивный вариант добавления элемента в дерево, C++ */
BinTree* InsRec(BinTree *Tree, BT x)
{
 if (!Tree) {Tree = (BinTree *) malloc(sizeof(BinTree));
      Tree->inf=x; Tree->L=0; Tree->R=0;
     }
 else if (x inf) Tree->L=InsRec(Tree->L, x);
      else Tree->R=InsRec(Tree->R, x);
 return Tree;
}
Существует несколько способов обхода (прохождения) всех узлов дерева. Три наиболее часто используемых из них называются обход в прямом (префиксном) порядке, обход в обратном (постфиксном) порядке и обход во внутреннем порядке (или симметричный обход). Каждый из обходов реализуется с использованием рекурсии.
Ниже приведены подпрограммы печати элементов дерева с использованием обхода двоичного дерева поиска в обратном порядке.
{Turbo Pascal}
Procedure PrintTree(T: U);
begin
    if T Nil
    then begin PrintTree(T^.L); write(T^.inf: 6); PrintTree(T^.R) end;
end;
// C++
void PrintTree(BinTree *T)
{
if (T) {PrintTree(T->L); cout infR);}
}
Реализуем функцию, возвращающую true (1), если элемент присутствует в дереве, и false (0) — в противном случае.
{Turbo Pascal}
function find(Tree: U; x: BT): boolean;
begin
   if Tree=nil then find := false
               else if Tree^.inf=x then Find := True
                                   else if x
                                        then Find := Find(Tree^.L, x)
                                        else Find := Find(Tree^.R, x)
end;
/* C++ */
int Find(BinTree *Tree, BT x)
{ if (!Tree) return 0;
 else if (Tree->inf==x) return 1;
      else if (x inf) return Find(Tree->L, x);
    else return Find(Tree->R, x);
}
По сравнению с предыдущими задача удаления узла из дерева реализуется несколько сложнее. Можно выделить два случая удаления элемента x (случай отсутствия элемента в дереве является вырожденным):
1) узел, содержащий элемент x, имеет степень не более 1 (степень узла — число поддеревьев, выходящих из этого узла);
2) узел, содержащий элемент x, имеет степень 2.
Случай 1 не представляет сложности. Предыдущий узел соединяется либо с единственным поддеревом удаляемого узла (если степень удаляемого узла равна 1), либо не будет иметь поддерева совсем (если степень узла равна 0).
Намного сложнее, если удаляемый узел имеет два поддерева. В этом случае нужно заменить удаляемый элемент самым правым элементом из его левого поддерева.
{Turbo Pascal}
function Delete(Tree: U; x: BT): U;
var P, v: U;
begin
  if (Tree=nil)
  then writeln('такого элемента в дереве нет!')
  else if x
                        else
                         if x > Tree^.inf
                         then Tree^.R := Delete(Tree^.R, x) {случай 1}
                         else
                         begin {случай 1}
                          P := Tree;
                          if Tree^.R=nil
                          then Tree:=Tree^.L
                          else if Tree^.L=nil
                               then Tree:=Tree^.R
                               else begin
                                     v := Tree^.L;
                                     while v^.R^.R nil do v:= v^.R;
                                     Tree^.inf := v^.R^.inf;
                                     P := v^.R;
                                     v^.R :=v^.R^.L;
                                    end;
                          dispose(P);
                         end;
Delete := Tree
end;
{C++}
BinTree * Delete(BinTree *Tree, BT x)
{ BinTree* P, *v;
 if (!Tree) cout L = Delete(Tree->L, x);
      else if (x > Tree-> inf) Tree->R = Delete(Tree->R, x);
    else {P = Tree;
   if (!Tree->R) Tree = Tree->L; // случай 1
   else if (!Tree->L) Tree = Tree->R; // случай 1
        else { v = Tree->L;
        while (v->R->R) v = v->R; // случай 2
        Tree->inf = v->R->inf;
        P = v->R; v->R = v->R->L;
      }
   free(P);
  }
return Tree;
}
Примечание. Если элемент повторяется в дереве несколько раз, то удаляется только первое его вхождение. Tree-> Tree-> vsp->


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат Поняття конституційного ладу і органів державної влади
Реферат Что выплавляют из тонн словесной руды или попытка реабилитации чатов
Реферат О порядке и сроках проведения реструктуризации кредиторской задолженности юрлиц по налогам и сборам
Реферат Процедуры аудита отдельных форм обмана (мошенничества). Действия аудитора при выявлении фактов мошенничества.
Реферат Политический государственный режим
Реферат Производственный менеджмент и его роль в организации бухгалтерского управленческого учёта на
Реферат Анестезия в оториноларингологии и офтальмологии
Реферат Технология растениеводства в хозяйстве
Реферат Сатирическое изображение помещиков в поэме Н. В. Гоголя "Мертвые души"
Реферат Неделя немецкого языка в школе
Реферат Экскурсия по Фурштатской улице
Реферат Вакцинация против дифтерии и столбняка детей имеющих в анамнезе солидные опухоли
Реферат История водопровода в СПб
Реферат Стародавнє індійське, китайське, античне, арабське і давньоруське мовознавство
Реферат Analysis On Aol Essay Research Paper Situation