Реферат: Динамические структуры данных: двоичные деревья
🛑 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.
В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.
Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: 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);
New(A); A^.Inf := X; A^.L:=Nil; A^.R := Nil;
If vsp^.L=Nil Then Begin vsp^.L:=A; vsp:=A^.L End Else vsp:=vsp^.L
If vsp^.R = Nil Then Begin vsp^.R := A; vsp:=A^.R End Else vsp := vsp^.R;
{Рекурсивный вариант добавления элемента в дерево, Turbo Pascal}
Procedure InsRec(Var Tree : U; x : BT);
/* Итеративный вариант добавления элемента в дерево, C++ */
BinTree* InsIteration(BinTree *T, BT x)
A = (BinTree *) malloc(sizeof(BinTree));
/* Рекурсивный вариант добавления элемента в дерево, C++ */
BinTree* InsRec(BinTree *Tree, BT x)
if (!Tree) {Tree = (BinTree *) malloc(sizeof(BinTree));
else if (x < Tree->inf) Tree->L=InsRec(Tree->L, x);
Существует несколько способов обхода (прохождения) всех узлов дерева. Три наиболее часто используемых из них называются обход в прямом (префиксном) порядке, обход в обратном (постфиксном) порядке и обход во внутреннем порядке (или симметричный обход). Каждый из обходов реализуется с использованием рекурсии.
Ниже приведены подпрограммы печати элементов дерева с использованием обхода двоичного дерева поиска в обратном порядке.
then begin PrintTree(T^.L); write(T^.inf : 6); PrintTree(T^.R) end;
if (T) {PrintTree(T->L); cout << T->inf<< " "; PrintTree(T->R);}
Реализуем функцию, возвращающую true (1), если элемент присутствует в дереве, и false (0) — в противном случае.
function find(Tree : U; x : BT) : boolean;
else if Tree^.inf=x then Find := True
else if (x < Tree->inf) return Find(Tree->L, x);
По сравнению с предыдущими задача удаления узла из дерева реализуется несколько сложнее. Можно выделить два случая удаления элемента x (случай отсутствия элемента в дереве является вырожденным):
1) узел, содержащий элемент x, имеет степень не более 1 (степень узла — число поддеревьев, выходящих из этого узла);
2) узел, содержащий элемент x, имеет степень 2.
Случай 1 не представляет сложности. Предыдущий узел соединяется либо с единственным поддеревом удаляемого узла (если степень удаляемого узла равна 1), либо не будет иметь поддерева совсем (если степень узла равна 0).
Намного сложнее, если удаляемый узел имеет два поддерева. В этом случае нужно заменить удаляемый элемент самым правым элементом из его левого поддерева.
function Delete(Tree: U; x: BT) : U;
then writeln('такого элемента в дереве нет!')
else if x < Tree^.inf then Tree^.L := Delete(Tree^.L, x) {случай 1}
then Tree^.R := Delete(Tree^.R, x) {случай 1}
BinTree * Delete(BinTree *Tree, BT x)
if (!Tree) cout << "такого элемента в дереве нет!" << endl;
else if (x < Tree->inf) Tree->L = Delete(Tree->L, x);
else if (x > Tree-> inf) Tree->R = Delete(Tree->R, x);
if (!Tree->R) Tree = Tree->L; // случай 1
else if (!Tree->L) Tree = Tree->R; // случай 1
while (v->R->R) v = v->R; // случай 2
Примечание. Если элемент повторяется в дереве несколько раз, то удаляется только первое его вхождение.
Название: Динамические структуры данных: двоичные деревья
Раздел: Рефераты по информатике, программированию
Тип: реферат
Добавлен 21:42:16 13 июля 2005 Похожие работы
Просмотров: 1283
Комментариев: 12
Оценило: 6 человек
Средний балл: 4.8
Оценка: 5 Скачать
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Реферат: Динамические структуры данных: двоичные деревья
Обществоведческое Эссе Человек Немыслим Вне Общества
Реферат: Контрольная по языковедению 2
Реферат Ценные Породы Деревьев
Курсовая работа: Исследование креативности: критерии оценки и методы изучения
Практическая Работа Номер 13 По Географии 7
Реферат по теме Особенности воспитания умственно отсталых и физически дефективных детей
Контрольная работа по теме Денежно-кредитная политика в Республике Беларусь
Реферат по теме Исследование периода колебаний математического маятника
Доклад: Гордеев Вячеслав Михайлович
Курсовая Работа Государство Актуальность
Таможенный Контроль Дипломная
Реферат: Общие свойства открытых иерархических систем
Реферат по теме Правовые отношения в сфере наемного труда
Реферат: Learning Styles Essay Research Paper Throughout our
Купер Практик 14 Характеристики
Салауатты Өмір Салты Туралы Эссе
Налог и налогообложение
Реферат: Оценка экологической ситуации в регионе . Скачать бесплатно и без регистрации
Реферат На Тему Классификация Пород Свиней Скачать
Мой Любимый Сайт Сочинение
Курсовая работа: Предмет социальной философии: постановка проблемы
Сочинение: Гончаров И.А.
Доклад: Индикаторы речевого поведения