Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.
В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.
Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: 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 < vsp^.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 < Tree^.inf
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 < vsp->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 < Tree->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 << T->inf<< " "; PrintTree(T->R);}
}
Реализуем функцию, возвращающую 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 < Tree^.inf
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 < Tree->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 < Tree^.inf then Tree^.L := Delete(Tree^.L, x) {случай 1}
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 << "такого элемента в дереве нет!" << endl;
else if (x < Tree->inf) Tree->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;
}
Примечание. Если элемент повторяется в дереве несколько раз, то удаляется только первое его вхождение.
Другие работы по теме:
Сочинения на свободную тему - Каштан деловое описание
Вокруг нашей школы высажено много каштанов. Это высокие деревья с аккуратной округлой кроной дающей летом густую прохладную тень. Листья каштана крупные разлапистые. Деревья с такими широкими листьями хорошо очищают воздух и обогащают его кислородом.
Астафьев в. п. - Один на один с тайгой
Деревья деревья деревья. Под ногами мох и жухлая трава над головой равнодушные безучастные к человеческой беде облака. А в сердце холодный липкий пронизывающий ужас заставляющий то бежать сломя голову то без сил лежать на земле.
а по теме динамика управляемых преобразовательных устройств
Введение. Цели регулирования пу. Анализ простейшей системы позиционного регулирования, сравнительная оценка идеального релейного и линейного регуляторов по быстродействию. Непрерывное и импульсное регулирование, их оценка по энергетике
Представление бинарного дерева в виде массива
Понятие линейных и нелинейных списков, иерархическое упорядочение элементов. Дерево - нелинейная структура, состоящая из узлов и ветвей и имеющая направление от корня к внешним узлам. Разработка программы представления бинарных деревьев в виде массива.
Структуры данных
Постановка задачи. Основные понятия и определения. Абстрактные структуры данных.
Городок в табакерке
Сказка В. Ф. Одоевского «Городок в табакерке» — образец художественно-познавательной сказки. В ней научный материал подан в занимательной форме. Мальчик Миша получает в подарок от отца музыкальную табакерку. Он поражён её красотой: на крышке ящика изображены ворота, башенка, золотые домики, золотые деревья.
Весна cочинение-описание природы
Едва повеяло весенним теплом, показались на деревьях почки – вот - вот появятся листочки. Все в природе оживает, будто облекается в ценное одеяние. Ясное солнышко позвало в гости раннюю весну. Поплыли в небесной возвышенности белоснежные облака. Зазеленевшая молоденькая травка. Свежий ветерок затронул голые деревья.
Чародейка зима
(по стихотворениям А. С. Пушкина «Зимняя дорога» и Ф. И. Тютчева «Чародейкою зимою») Зима — необыкновенное время года. Белый пушистый снег, заснеженные деревья, морозный воздух. Не зря в народе называют зиму красавицей, волшебницей. Это удивительное время года вдохновило многих поэтов к созданию прекрасных поэтических строк.
Деревья - наши друзья
Деревья - наши друзья. Они помогают нам всем! Как приятно смотреть на их высокие крепкие стволы, раскидистые ветки, яркую листву! Весной на деревьях распускаются почки и радуют глаз прохожих, поднимая им расположение духа.
Благодарная природа
Автор: Сочинения на свободную тему Что такое природа? Мы все прекрасно понимаем, что такое природа – это леса, поля, моря, озера и реки, деревья, растения, кустарники, цветы. Все то, что нас окружает! А так же животные, насекомые, птицы, рыбы - тоже часть природы. К природе относятся полезные ископаемые: нефть, газ, уголь.…
Осень сочинение-описание
Автор: Сочинения на свободную тему Еще очень тепло, но уже грустно от запаха ушедшего лета, многослойного, пряно-кисловатого. Деревья сбрасывают обожженную за лето листву. Кажется, что стволы темнеют, они устали и хотят спать. Неугомонные мелкие паучки с невероятной скоростью плетут паутины, и ты, не видя, срываешь их ловушки.
Анализ стихотворения И.А. Бунина Ещё и холоден и сыр...
Анализ стихотворения И.А. Бунина "Ещё и холоден и сыр..." Автор: Бунин И.А. Стихотворение "Ещё и холоден и сыр..." написано Буниным в 1901 году. Оно относится к раннему этапу творчества писателя. В стихотворении мы видим февраль, конец зимы: "Ещё и холоден и сыр Февральский воздух...".
Весна в лесу
Автор: Сочинения на свободную тему "Еще в полях белеет снег, А воды уж весной шумят - Бегут и будят сонный брег, Бегут, и блещут, и гласят..." Ф.Тютчев
Природа и храмы
Какому бы ками ни был посвящен храм, его следует воспринимать вместе с прекрасным ландшафтом той местности, где он расположен. Синтоистское богослужение прочно ассоциируется с чувством прекрасного.
Команда перемещения данных микропроцессора К580
Микропроцессор К580. Прямая, непосредственная и косвенная адресация. Команды перемещения данных, загрузки аккумулятора, запоминания данных, непосредственной загрузки пары регистров, обмена содержимого пар регистров. Команды операции со стеком.
BMW
Заднеприводной седан среднего класса со спортивным характером. Отменная управляемость и прекрасные динамические характеристики объединяются в этом автомобиле с престижным и узнаваемым внешним видом и высокой надежностью.
Дерево свободы
(фр. arbre de la libertй, нем. Freiheitsbaum) — революционный символ. История Ведет свое происхождение от распространённого у многих европейских народов обычая встречать наступление весны, а также больших праздников насаждением зелёных деревьев (майские деревья). Символический смысл свободы дерево впервые получило во время американской войны за независимость, в начале которой жители Бостона собирались под подобным деревом для совещаний.
Пятнистый лазающий полоз
План Введение 1 Описание 2 Ареал 3 Образ жизни Введение Пятнистый лазающий полоз, или красная крысиная змея[1] (лат. Pantherophis guttatus[2]) — змея рода Pantherophis, которая обитает в Северной Америке.
Динамические структуры данных
Создание стека как линейного списка. Использование аналогичного ссылочного типа для организации очереди. Циклически связанный список. Построение сложных структур в динамической памяти. Бинарные (двоичные) деревья. Экран результата и контрольные расчеты.
Особенности работы с Microsoft Access
Обзор Microsoft Access, элементы базы данных в различных режимах. Создание простой таблицы. Типы и свойства полей. Установление первичного ключа. Способы удаления и переименования таблиц. Возможности записей с помощью фильтров. Запрос на выборку.
Синтез логических схем
Синтез реверсивного регистра сдвига. синтез РСР на триггерах типа D. Таблица переходов для прямого счёта. Синтез последовательного восьмиразрядного сумматора.
Основы информатики
Общее представление о системах счисления. Перевод чисел в двоичную, восьмеричную и шестнадцатеричную системы счисления. Разбивка чисел на тройки и четверки цифр. Разряды символов числа. Перевод из шестнадцатеричной системы счисления в десятичную.
Определение связности графа на Лиспе
Двоичные деревья в теории информации. Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Обоснование выбора, описание алгоритма и структур данных. Обоснование набора тестов. Построение оптимального кода. Сущность алгоритма Хаффмана.
Микропроцессор КР580ИК
КР580ИК80 представляет собой 8-разрядный процессор, в котором совмещены операционное и управляющее устройства. Опишем кратко узлы этого процессора.
Динамические структуры данных 4
Динамические структуры данных. Указатели До сих пор мы имели дело с переменными, которые размещаются в памяти согласно определенным правилам, а именно, для локальных переменных, описанных в подпрограмме, память отводиться при вызове подпрограммы; при выходе из нее эта память освобождается, а сами переменные прекращают существование.
Динамические структуры данных стеки
Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.
Особенности работы с Microsoft Access 2
Министерство образования и науки Украины Донбасская государственная машиностроительная академия Кафедра КИТ Контрольная работа по дисциплине "Технические средства коммуникаций"
Деревья /english/
Представление информационных конструкций в виде дерева, что такое "дерево", примеры построения и определения "дерева".
Промышленное освоение лесных ресурсов тайги
Промышленное освоение лесных ресурсов тайги ориентируется на "снятие сливок" - то есть использование в данный момент тех ресурсов, которые имеют максимальную ценность, без серьезного учета долговременных перспектив ведения хозяйства.
Зимние явления в жизни растений
Отчет об экскурсии “” Отчет подготовили: 6”А” класс, Ушакова Юля, Хромых Марина. 18 февраля 2003 г Облачно с прояснениями Ветер юго-западный, морозно.
Сравнение однодольных и двудольных растений
Понятие однодольных и двупольных растений, их классификация, разновидности, сходные и отличительные черты. Составление и виды формул цветков. Методика определения семейства растения, общий вид его соцветия, вид плода. Значение растений в жизни человека.
Цузе Конрад
Автор модели механической вычислительной машины, в которой использовались двоичная система счисления , форма представления чисел с плавающей запятой , трехадресная система программирования и перфокарты .