Структуры данных и алгоритмы (1021739), страница 24
Текст из файла (страница 24)
Этот массив будет состоять из записей с полямиweight (вес) и root (корень) следующего типа:3.4. ДВОИЧНЫЕ ДЕРЕВЬЯ95recordweight: real;root: integerendНачальные значения всех трех массивов, соответствующих данным на рис. 3.15,а,показаны на рис. 3.16. Эскиз программы (псевдопрограмма, т.е. программа напсевдоязыке, как описано в главе 1) построения дерева Хаффмана представлен влистинге 3.8.Поля weight root1а0.12110002b0.40220003с0.15330004d0.08440005е0.2555000symbol proba- leafbilityМассивы FORESTALPHABETРис.
3.16. Исходное состояние массивовleft- right- parentchild childTREEЛистинг 3.8. Программа построения дерева Хаффмана(1) while существует более одного дерева в лесу dobegin(2)i:= индекс дерева в FOREST с наименьшим весом;(3)j : = индекс дерева в FOREST со вторым наименьшим весом;(4)Создание нового узла с левым сыном FOREST[i].root иправым сыном FOREST[j].root;(5)Замена в FOREST дерева i деревом, чьим корнем являетсяновый узел и чей вес равенFORESТ[i].weight + FOREST[j].weight;(в)Удаление дерева j из массива FORESTend;Для реализации строки (4) листинга 3.8, где увеличивается количество используемых ячеек массива TREE, и строк (5) и (6), где уменьшается количество ячеекмассива FOREST, мы будем использовать курсоры lasttree (последнее дерево) иlastnode (последний узел), указывающие соответственно на массив FOREST и массивTREE.
Предполагается, что эти курсоры располагаются в первых ячейках соответствующих массивов1. Мы также предполагаем, что все массивы имеют определеннуюобъявленную длину, но здесь мы не будем проводить сравнение этих ограничивающих значений со значениями курсоров.В листинге 3.9 приведены коды двух полезных процедур.
Первая из них,lightones, выполняет реализацию строк (2) и (3) листинга 3.8 по выбору индексовдвух деревьев с наименьшими весами. Вторая процедура, функция create(nlt n2),создает новый узел и делает заданные узлы пг и И2 левым и правым сыновьямиэтого узла.1Для этапа чтения данных, который мы опускаем, необходим также курсор для массиваALPHABET, который бы "следил" за заполнением данными этого массива.96ГЛАВА 3. ДЕРЕВЬЯЛистинг 3.9. Две процедурыprocedure lightones ( var least, second: integer ),{ присваивает переменным least и second индексы массиваFOREST, соответствующие деревьям с наименьшими весами.Предполагается, что lasttree > 2.
}vari: integer;begin { инициализация least и second,рассматриваются первые два дерева }if FOREST[l].weight <= FOREST[2].weight thenbegin least:= 1; second:= 2 endelsebegin least:= 2; second:= 1 endfor i:= 3 to lasttree doif FOREST Ii].weight < FORESTlleast].weight thenbegin second:= least; least:= i endelse if FOREST[i].weight < FOREST[second].weight thensecond:= iend; { lightones }function create ( lefttree, righttree: integer-): integer;{ возвращает новый узел, у которого левым и правым сыновьямистановятся FOREST[left tree].root и FORESГ[righttree].root }beginlastnode:= lastnode + 1;{ ячейка TREE[lastnode] для нового узла }mEEflastnode].leftchild:= FOREST[lefttree] .root;TREEllastnode].rightchild:= FOREST[righttree] .root;{ теперь введем указатели для нового узла и его сыновей }TREE[lastnode].parent:= 0;TREE[FOREST[lefttree].root].parent:= lastnode;TREE[FOREST[righttree].root].parent:= lastnode;return(lastnode)end; { create }Теперь все неформальные операторы листинга 3.8 можно описать подробнее.
Влистинге 3.10 приведен код процедуры Huffman, которая не осуществляет ввод ивывод, а работает со структурами, показанными на рис. 3.16, которые объявленыкак глобальные.Листинг 3.10. Реализация алгоритма Хаффманаprocedure Hufrman;vari, j:integer; {два дерева с наименьшими весами из FOREST}newroot: integer;beginwhile lasttree > 1 do beginlightones(i, j);newroot:= created, j) ;{ далее дерево i заменяется деревом с корнем newroot }FORESTd] .weight:=FOREST[i] .weight + FOREST[j] . weight;FOREST[i].root:= newroot;{ далее дерево j заменяется на дерево lasttree,массив FOREST уменьшается на одну запись }3.4.
ДВОИЧНЫЕ ДЕРЕВЬЯ97FOREST[j] := FOREST[lasttree];lasttree:= lasttree - 1end;end{ Huffman }На рис. 3.17 показана структура данных из рис. 3.16 после того, как значениепеременной lasttree уменьшено до 3, т.е. лес имеет вид, показанный на рис.
3.15,в.weight rootFOREST1а0.121-10062b0.402-2003с0.153-3004d0.084-4000765е0.255-5000symbol proba- leafbility64177360ALPHABETleft- right- parentchild childTREEРис. 3.17. Структура данных после двух итерацийПосле завершения работы алгоритма код каждого символа можно определить следующим образом. Найдем в массиве ALPHABET запись с нужным символ в полеsymbol. Затем по значению поля leaf этой же записи определим местоположение записи в массиве TREE, которая соответствует листу, помеченному рассматриваемымсимволом.
Далее последовательно переходим по указателю parent от текущей записи,например соответствующей узлу п, к записи в массиве TREE, соответствующей егородителю р. По родителю р определяем, в каком его поле, leftchild или rightchild,находится указатель на узел п, т.е. является ли узел га левым или правым сыном, и всоответствии с этим печатаем 0 (для левого сына) или 1 (для правого сына).
Затемпереходим к родителю узла р и определяем, является ли его сын р правым или левым, и в соответствии с эти печатаем следующую 1 или О, и т. д. до самого корнядерева. Таким образом, код символа будет напечатан в виде последовательности битов, но в обратном порядке. Чтобы распечатать эту последовательность в прямом порядке, надо каждый очередной бит помещать в стек, а затем распечатать содержимоестека в обычном порядке.Реализация двоичных деревьев с помощью указателейДля указания на правых и левых сыновей (и родителей, если необходимо) вместокурсоров можно использовать настоящие указатели языка Pascal. Например, можносделать объявлениеtypenode = recordleftchild: T node;rightchild: t node;parent: t nodeend98ГЛАВА З.
ДЕРЕВЬЯИспользуя этот тип данных узлов двоичного дерева, функцию create (листинг 3.9)можно переписать так, как показано в следующем листинге.Листинг 3.11. Код функции create при реализации двоичного дерева с помощьюуказателейfunction create ( lefttree,varroot: Tnode;beginnew(root) ;rootT.leftchild:=rootf.rightchild:=roott.
parent:= 0;lefttreeT. parent:=righttree1.parent:=return(root)end; { create }righttree: Tnode): tnode;lefttree;righttree;root;root;Упражнения3.1.Ответьте на следующие вопросы о дереве, показанном на рис. 3.18:а) какие узлы этого дерева являются листьями?б) какой узел является корнем дерева?в) какой узел является родителем узла С?г) назовите сыновей узла С;д) назовите предков узла Е;е) назовите потомков узла Е;ж) какие узлы являются правыми братьями узлов D и Е?з) какие узлы лежат слева и справа от узла G?и) какова глубина узла С?к) какова высота узла С?Рис. 3.18. Дерево3.2.3.3.Сколько путей длины 3 существует на дереве, показанном на рис. 3.18?Напишите программы вычисления высоты дерева с использованием трех представлений деревьев, описанных в разделе 3.3.УПРАЖНЕНИЯ993.4.3.5.3.6.Составьте списки узлов дерева, представленного на рис.
3.18, при обходеэтого дереваа) в прямом порядке;б) в обратном порядке;в) во внутреннем порядке.Пусть два различных узла тп и п принадлежат одному и тому же дереву. Покажите, что только одно из следующих утверждений может быть истинным:а) узел т расположен слева от узла п;б) узел т расположен справа от узла п;в) узел т — истинный предок узла п;г) узел т — истинный потомок узла п.Поставьте галочку в ячейку на пересечении строки i и столбца j, если одновременно выполняются условия, представленные в заголовках строки i истолбца j.Узел т» предшеству- Узел п предшеству- Узел п предшествует узлу /га приет узлу тп приет узлу т приобходе дереваобходе деревасимметричномв прямом порядке в обратном порядкеобходе дереваУзел п расположен слева отузла тпУзел п расположен справаот узла тУзел п — истинный предокуЗЛа 771Узел п — истинный потомок УЗЛа 7713.7.*3.8.3.9.100Например, поставьте галочку в ячейку на пересечение третьей строки и второго столбца, если уверены, что узел п может быть истинным предком узла т ив тоже время предшествовать узлу т при обходе дерева в обратном порядке.Предположим, что есть массивы PREORDER[n], INORDER[n] и POSTORDER[n],содержащие списки узлов дерева, полученные при его обходе в прямом, внутреннем и обратном порядке соответственно.
Используя эти массивы, опишитеалгоритм, который для любой пары узлов i и j определяет, является ли узел iпредком узла j.Существует способ проверить, является ли один узел истинным предком другого узла, который основан на следующем правиле: узел т является истиннымпредком узла п, если узел тп предшествует узлу п при обходе дерева в X порядке, но следует за узлом п при обходе в Y порядке, где X и Y выбираются измножества {прямом, обратном, внутреннем}. Определите все возможные парыX и Y, когда это правило справедливо.Напишите программы обхода двоичных деревьева) в прямом порядке;б) в обратном порядке;в) во внутреннем порядке.ГЛАВА 3. ДЕРЕВЬЯ3.10. При прохождении дерева в порядке уровней в список узлов сначала заноситсякорень дерева, затем все узлы глубины 1, далее все узлы глубины 2 и т.д.
Узлы одной глубины заносятся в список узлов в порядке слева направо. Напишите программу обхода деревьев в порядке уровней.3.11. Преобразуйте выражение ((а + Ь) + с * (d + е) + f) * (g + h)а) в префиксную форму;б) в постфиксную форму.3.12. Нарисуйте дерево, соответствующее префиксным выраженияма) *а + Ь*с + de;б) *а + *b + cde.3.13. Пусть Т — дерево, в котором каждый узел, не являющийся листом, имеетровно двух сыновей.
Напишите программы преобразованияа) списка узлов дерева Т, составленного при обходе дерева в прямом порядке,в список, составленный при обходе в обратном порядке;б) списка узлов дерева Т, составленного при обходе дерева в обратном порядке, в список, составленный при обходе в прямом порядке;в) списка узлов дерева Т, составленного при обходе дерева в прямом порядке,в список, составленный при симметричном обходе.3.14. Напишите программу вычисления арифметических выражений при обходедереваа) в прямом порядке;б) в обратном порядке.3.15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
