Основы программирования (947332), страница 41
Текст из файла (страница 41)
Следующее число 8 больше значения в корне, соответственно оно будет записано в правое поддерево (рис. 7.18, в). Следующее число 7 больше, чем значение в корне дерева, значит, оно должнобыть записано в правое поддерево, но правое поддерево уже построено.Сравниваем 7 со значением в корне правого поддерева - числом 8. Так какдобавляемое значение меньше значения в корне правого поддерева, то добав-©®©© 0©5©i2)дРис. 7.18.
Построение сортированного бинарного дерева:первые шаги (ЙГ - г) и окончательный вариант (д)239Часть I. Основы алгоритмизации и процедурное программированиеляем левое поддерево уже к этому корню (рис. 7.18, г). Полностью сформированное бинарное дерево представлено на рис. 7.18, д.Фрагмент программы, реализующий добавление вершины к дереву, состоит из трех частей: создания вершины, поиска корня, к которому можно добавить поддерево, придерживаясь основного правила, и, непосредственно,добавления вершины:{создание новой вершины}new(q); {выделяем память для нового элемента}with q^ do {заносим значения}begin value:=п;left:=nil;right:=nil;end;{поиск корня для добавляемой вершины}pass:=root;{начинаем с корня бинарного дерева}while passonil do {пока не найдено свободное место}begin next:=pass; {сохраняем адрес корня-кандидата}if q\value<pass^.value then pass: =pass\left{влево}elsepass:^pass^,right; {вправо}end;{добавление вершины}if q\value<next\value then{если значение меньше корня}next\left:=q{добавляем левое поддерево}else next^.right:=q;{добавляем правое поддерево}Используя рекурсивь^ость определения дерева, можно построить рекурсивную процедуру добавления вершин к дереву.
В качестве параметров этапроцедура будет получать указатель на корень дерева и указатель на добавляемый элемент.Procedure Add(Var r:top_ptr; pass:top_ptr);beginifr=nil then r:=pass {если место свободно, то добавляем}else {иначе идем налево или направо}if (pass\ value<r\value) then Add(r\ left,pass)else Add(r^.right,pass);end;...Поиск вершины в сортированном бинарном дереве. Поиск в сортированном бинарном дереве осуществляется следующим образом: вначалезначение ключа поиска сравнивается со значением в корне. Если значениеключа в искомой вершине меньше, чем в корневой, то поиск переходит в левую ветвь.
Если больше или равно - то в правую ветвь. И так в каждой следующей вершине до тех пор, пока не отыщется искомая. Так, для предыду2407. Программирование с использованием динамической памятищего варианта последовательности поисквершины с ключом 7 будет выполнен затри шага (рис. 7.19).Если мы добрались до листа, а искомая вершина не обнаружена, то следуетвьщать соответствующее сообщение. Впротивном случае вершину помечают какнайденную (запоминают ее адрес) и обрабагываюг в соогвегствии с алгоритмомпрограммы:^ ^.^ „'^"'-li'l "P""!L!!f'^ "бинарном деревеpass:^root;flag:=false;while (passonil){начинаем с корня бинарного дерева}{признак «вершина не найдена»}and not flag do {пока не найден элемент или не дошли до листа}ifn=pass^.value thenflag:^'true {значение найдено}elseifn<pass\value then pass:-pass\left{влево}else pass:-pass\right; {вправо}(/[;7ag rAew <вершина найдена>else <вершина не найдена> ...Поиск вершины также можно осуществлять, используя рекурсию.
Дляудобства использования построим рекурсивную функцию, которая будетвозвращать true, если элемент найден, и false ~ в противном случае. Адреснайденного элемента будем возвращать через параметр pass:Function Find(r:topj>tr; Varpass:topj)tr; n:integer):boolean;Beginifr^nil then Find:=fiilse {значение не найдено}elseifn=r^.value thenbeginFind:-true; {значение найдено}pass:=r;{запомнили адрес}endelseifn<r^.value thenFind:^Find(r^Jefl,n) {влево}else Find: =Find(r^.right,n); {вправо}End;Вызывать такую функцию можно непосредственно из условия оператора условной передачи управления или циклов, например:241Часть 1.
Основы алгоритмизации и процедурное программированиеабРис. 7.20. Удаление листа:а - поиск удаляемой вершины; б- удаление вершиныif Find(r,pass,n) then <вершина найдена, адрес в pass>else <вершина не найдена> ...Удаление вершины с указанным ключом. Удалению вершины с указанным ключом предшествует ее поиск (см. выше). Непосредственное удаление вершины реализуется в зависимости от того, какая вершина удаляется:• удаляемая вершина не содержит поддеревьев (лист) - удаляем ссьшку на вершину из корня соответствующего поддерева (рис. 7.20);• удаляемая вершина содержит одну ветвь (рис. 7.21, а): для удалениянеобходимо скорректировать соответствующую ссылку в корне, заменив адрес удаляемой вершины адресом вершины, из нее выходящей (рис. 7.21, б);• удаляемая вершина содержит две ветви (рис.
7.22, а): в этом случаенужно найти подходящую вершину, которую можно вставить на место удаляемой, причем эта подходящая вершина должна легко перемещаться. Такаявершина всегда существует: это либо самый правый элемент левого поддерева, либо самый левый элемент правого поддерева удаляемой вершины(рис. 7.22, б).Ниже представлена рекурсивная процедура удаления вершины с указанным значением (параметры: г - адрес корня дерева, к - значение).Рис. 7.21. Удаление корня с одним поддеревом:а -> поиск удаляемой вершины; б- удаление вершины2427. Программирование с использованием динамической памятиш^бвРис.
7.22. Удаление корня с двумя поддеревьями:а - поиск удаляемой вершины и вершин-кандидатов на замещение;б- замена вершины самой правой вершиной левого поддерева;в - замена вершины самой левой вершиной правого поддереваProcedure Delete(var г: topj)tr; к: integer);{Внутренняя рекурсивная процедура поиска заменяющейвершины в левом поддереве. Параметры: г - адрес корнялевого поддерева, q - адрес заменяемой вершины}Procedure delfvar r:topj)tr; q:topj)tr);Var ql:topj)tr;beginifr\right=^nil then{заменяющая вершина найдена}beginq\value:-r\value; {копируем значение}{удаляем заменяющую вершину}r:-r\left;{освобождаемпамять}Dispose(ql);end{идем по поддереву направо}else del(r\right,фEnd;Var q:topj)tr;beginifr=nil then WriteLnCЭлeмeнm не найден или дерево пустое *)else{поиск элемента с заданным ключом}243Часть L Основы алгоритмизации и процедурное программированиеif k<r\valuethen{если меньше, то налево}Delete(r\lefUk)elseifk>r^.value then{если больше, то направо}Delete(r\right,k)elsebegin {элемент найден, его необходимо удалить}{удаление листа или корня с одним поддеревом}ifr\right=nil then {нет правого поддерева}beginr:=r\left;О18ро8е(ф;endelseifr\left=nilbeginthen {нет левого поддерева}r:=r\ right;О18ро8е(ф;endelse {удаление корня с двуми поддеревьями}del(r^Jeft,r);endEnd;...Сортировка с использованием дерева.
Так как дерево формируется поопределенным выше правилам, то сортировка по возрастанию осуществляется обходом дерева «слева направо». Обход начинается с самого нижнеголевого листа или, если такого листа нет, корня. Вывод значений осуществляется в следующем порядке: сначала выводится значение самого нижнего левого поддерева, затем корня, затем самого нижнего левого поддерева правого поддерева и т.д. (рис. 7.23).Пример 7.6.
Разработать программу сортировки заданной последовательности целых чисел сиспользованием сортированногобинарного дерева.Программа должна строитьбинарное дерево из вводимых склавиатуры целых чисел, а затемРис. 7.23. Обход дерева «слеваосуществлять обход дерева длянаправо»вывода отсортированных данных.2447. Программирование с использованием динамической памятиПостроение дерева реализуем отдельной подпрограммой, которая будетполучать адрес добавляемой вершины и адрес корня бинарного дерева. Поиск корня для добавляемой вершины, как показано выше, будем осуществлять рекурсивно.Обход дерева «слева направо» также будем осуществлять рекурсивно.Нерекурсивный вариант достаточно сложен, и его использование нецелесообразно.Полностью текст программы приведен ниже.Program Sort4;Type topjptr^^top; {тип "указатель на вершину дерева"}top=record{тип вершины дерева)value:integer;{целое число}left, right:top_ptr; {указатели на левое и правое поддеревья}end;Var next number: integer;n pass:topj)tr;{корень бинарного дерева}{процедура добавления вершины к дереву}Procedure AddfVar r:top_ptr; pass: top_ptr);beginifr=nil then r:=pass {если место свободно, то добавляем}else {иначе идем налево или направо}if (pass\value<r\value) then Add(r^.left,pass)else Add(r\right,pass);end;{процедура сортировки - обход дерева}procedure Tree(r:top_ptr);beginifronilthenbegin {если есть поддерево}Tree(r\left);{обход левого поддерева}Write (revalue: 4); {вывод значения из корня}Tree(r\right);{обход правого поддерева}end;end;{основная программа}begin{формирование исходного дерева}WriteLnCВводите числа');г:=пП;Read(nextjiumber);while not EOF do245Часть L Основы алгоритмизации и процедурное программированиеbeginnew (pass); {выделяем память для нового элемента}withpass^do {заносим значения}beginvalue: -nextjiumber;left: =nil;right: ==nil;end;Add(r, pass); {добавляем элемент к дереву}Readfnextjiumber)end;ReadLn;WnteLnCCopmupoeaHuan последовательность:);Tree(r);EndОценка вычислительной сложности операций с сортированнымибинарными деревьями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
