Студопедия — PrintTree(Root,0)
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

PrintTree(Root,0)






Пример 3.6. Описать процедуру MaxEl, определяющую наибольший
элемент непустого дерева T.

Алгоритм MaxEl использует префиксный обход дерева: наибольший элемент находится или в узле, или в его левом поддереве, или в его правом
поддереве.

procedure MaxEl(T: Tree; var max: integer);

var m: integer;

Begin

if T <> nil then

Begin

max:=T^.inf;

if T^.L <> nil then

Begin

MaxEl(T^.L, m);

if m > max then max:=m

End;

if T^.R <> nil then

Begin

MaxEl(T^.R, m);

if m > max then max:=m

End

End

end; { MaxEl }

Пример 3.7. Описать рекурсивную процедуру Leaf подсчета количества k листьев дерева.

procedure Leaf(T: Tree; var k: integer);

Begin

if T <> nil then

if (T^.L=nil) and (T^.R=nil) then

k:=k+1

Else

Begin

Leaf(T^.L,k);

Leaf(T^.R,k)

End

end; { Leaf }

Количество List листьев дерева Root можно определить, обратившись к процедуре Leaf:

List:=0; Leaf(Root,List);

Если описать реализацию в виде функции, то не придется заботиться о присваивании нуля параметру–результату перед ее вызовом.

function fLeaf (T: Tree): integer;

Begin

if T=nil then fLeaf:=0

Else

if (T^.L=nil) and (T^.R=nil) then

fLeaf:=1

else fLeaf:= fLeaf(T^.L)+fLeaf(T^.R)

end {fLeaf};

Пример 3.8. Описать рекурсивную функцию Double, которая проверяет, есть ли в дереве T хотя бы два одинаковых элемента.

Один из вариантов проверки состоит в использовании функции Count подсчета числа вхождений заданного элемента El в дерево T. Функция Double поочередно проверяет число вхождений текущего значения T^.inf в дерево: если число вхождений больше 1, то результат проверки – истина, если нет, то такая ситуация может возникнуть в левом поддереве или в правом поддереве.

function COUNT(T: Tree; El:integer): integer;

var k: integer;

Begin

if T=nil then COUNT:=0

Else

Begin

if T^.inf = El then k:=1 else k:=0;

COUNT:=k+COUNT(T^.L,El)+COUNT(T^.R,El)

End

end; { COUNT }

function Double(T: Tree): boolean;

Begin

if T=nil then Double:=false

Else

Begin

if COUNT(T,T^.inf) > 1 then Double:=true

Else

Double:= Double(T^.L) or Double(T^.R)

End

end; { Double }

Пример 3.9. Описать функцию Equal проверки на равенство двух двоичных деревьев одинаковой структуры.

function Equal(T1,T2: Tree): boolean;

Begin

if T1=T2 then Equal:=true

Else

if (T1 <> nil) and (T2 <> nil) then

if T1^.inf = T2^.inf then

Equal:=Equal(T1^.L,T2^.L) and

Equal(T1^.R,T2^.R)

else Equal:=false

else Equal:=false

end; { Equal }

Пример 3.10. Описать процедуру Copy, которая создает копию T2
дерева T1.

procedure Copy(T1: Tree; var T2: Tree);

Begin

if T1 = nil then T2:=nil

Else

Begin

new(T2); T2^.inf:=T1^.inf;

Copy(T1^.L,T2^.L);

Copy(T1^.R,T2^.R);

End

end; { Copy }

Упражнение 3.2. Описать нерекурсивную процедуру или функцию, которая возвращает элемент из самого левого (правого) листа непустого дерева.

Упражнение 3.3. Описать нерекурсивную процедуру или функцию, которая

а) определяет количество узлов дерева;

б) вычисляет сумму (произведение, среднее арифметическое) всех элементов дерева.

в) определяет число вхождений заданного элемента в дерево;

г) выдает элементы из всех листьев дерева.

Упражнение 3.4. Описать рекурсивную процедуру или функцию, которая

а) определяет количество узлов (листьев, внутренних узлов) дерева;

б) вычисляет сумму (произведение, среднее арифметическое) всех элементов дерева.

в) определяет, входит ли заданный элемент в дерево;

г) выдает элементы из всех листьев (внутренних узлов) дерева;

д) определяет глубину непустого дерева;

е) определяет количество узлов на заданном уровне;

ж) удаляет листья дерева со значениями, равными заданному.

 

4. ДЕРЕВО ПОИСКА (СОРТИРОВКИ)

 

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

4.1 Построение дерева поиска

Алгоритм создания дерева поиска основан на следующих правилах:

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

Если в дереве есть узел с таким значением, то возможны варианты:

а) новый узел добавляется в правое поддерево,

б) новый узел добавляется в левое поддерево,

в) добавление не происходит.

Инфиксный обход такого дерева дает упорядоченную по возрастанию
(неубыванию в случае добавления одинаковых элементов) последовательность.

Пример 4.1. Упорядочить по неубыванию последовательность целых чисел, которая вводится из текстового файла.







Дата добавления: 2015-08-12; просмотров: 290. Нарушение авторских прав; Мы поможем в написании вашей работы!



Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Дренирование желчных протоков Показаниями к дренированию желчных протоков являются декомпрессия на фоне внутрипротоковой гипертензии, интраоперационная холангиография, контроль за динамикой восстановления пассажа желчи в 12-перстную кишку...

Деятельность сестер милосердия общин Красного Креста ярко проявилась в период Тритоны – интервалы, в которых содержится три тона. К тритонам относятся увеличенная кварта (ув.4) и уменьшенная квинта (ум.5). Их можно построить на ступенях натурального и гармонического мажора и минора.  ...

Понятие о синдроме нарушения бронхиальной проходимости и его клинические проявления Синдром нарушения бронхиальной проходимости (бронхообструктивный синдром) – это патологическое состояние...

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

Признаки классификации безопасности Можно выделить следующие признаки классификации безопасности. 1. По признаку масштабности принято различать следующие относительно самостоятельные геополитические уровни и виды безопасности. 1.1. Международная безопасность (глобальная и...

Прием и регистрация больных Пути госпитализации больных в стационар могут быть различны. В цен­тральное приемное отделение больные могут быть доставлены: 1) машиной скорой медицинской помощи в случае возникновения остро­го или обострения хронического заболевания...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия