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


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

Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.
В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.
Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: 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 мильонов к студенческой карме :

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

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

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

Реферат Cоциальная стратификация
Реферат Комерціїні банки
Реферат Современная наука о сущности этноса и этничности
Реферат Конституційні принципи побудови і діяльності державних органів
Реферат Кодекс адміністративного судочинства України
Реферат Колективні форми організації праці
Реферат Анализ структуры затрат и издержек предприятия ООО "Фабэр"
Реферат Контрольна робота з історії України за перший семестр
Реферат Корпоративное мышление в пермских бизнес-структурах на примере ОАО Уралсвязьинформ
Реферат Концепция атомизма как концепция корпускулярноволнового дуализма
Реферат Компетенція парламентів Статус депутатів
Реферат Конституція Пилипа Орлика 1710 року
Реферат Компетенція міської ради була дуже широка вона повинна була стежити за господарством міста
Реферат Комплексное исследование природных ресурсов Республики Бурятия на основе данных дистанционного
Реферат Генеральные штаты Франция