Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 39
Текст из файла (страница 39)
Дерево, представленное с помогпью массива 1 2 3 4 5 б 7 8 9 10 11 Прежде чем обсуждать, как лучше использовать деревья и как выполнять операции с деревьями, мы покажем на при. 4. Динамее а иа иа~форличноннме структуры 226 мсрс, как программа может строить дерево. Предположим, что нужно сформировать деоево, содержащее узлы типа, описанного в (4,39), а значениями узлов будут и чисел, прочитанных из входного файла. Для усложнения задачи потребуем построить дерево с а узлами и минимальной высотой.
Чтобы достичь минимальной высоты при данном числе узлов, нужно располагать максимально возможное число узлов на всех уровнях, кроме самого нижнего. Это можно сделать очень просто, если распределять все поступающие узлы Рис. 4.22 Идеальна сбалансированные деревьв. поровну слева и справа от каждого узла. В результате по. строенное дерево при данном и имеет внд, как показано на рнс. 4.22 для и = 1, ..., 7. Правило равномерного распределения при известном числе узлов л лучше всего формулируется с помощью рекурсии: 1. Взять один узел в качестве корня.
2. Построить левое поддерево с п1= л411н2 узламн тем же способом. 3. Построить правое поддерево с пг = и†п! — 1 узлами тем же способом. Это правило описано рекурсивной процедурой 1гее, входящей в программу 4.3, которая читает входной файл и строит идеально сбалансированное дерево. Мы получаем такое определение: 4.4. Древовидные структуры ргодтапь Ъи11е11гее(шриг,оигри1) ," еуре ген =- ",пот1е1 поде = гесогд Ьеу: 1п(ееег; 1е11, пад1: ген едд „ ааг и; рдгееег; гоо1: ген 4пнс11од ггее(и: 1111ееег); гег; уаг пеппойе.
'ге1;" х, п1, г1г; 1п1едег; Ъерп 1построение идеально сбалансированног Ы и =- 0 йод 1гее:= п11 е1во Ъец!и п1:= и д1у 2; пг:= и — п1 — 1; геаа1д); пеи(пенпоЫе)1 д11Ъпенпот1е, до Ъеа1д Ьеу:= л'; Ц~:= 1геефУ)1 г1а1ее ода 1 йее ."= педпен1, епд епд фее); ргоседнгерг1пгггее(11.ге~; Ь: 1игеаег)1 чае П 1п1ецег;. Ъед1д '1 печать дерева 1 со сдвигом Ь) Ы 1 .-рь д11 4Ъеп д11Ъ 11 Йо ъерпрг1игггее11е11, л+1); Гог К:=- 1 4о Ь до ит11е(' дг11е1и (Ьеу); рпп1й ее(пцЫ, Ь+1) едд епд "1 рг1п Дгее); Ъефд 1,первое целое число есть число увлов) ген(л); гоо1:= йети); 'рпп11гефоо1, 0) Фдд . о дерева с и узлами'1 = йЕЕЦ4Г) Программа 4.3. Построение идеально сбалансированного дерева.
4. Динамические информационнв~е структуры 228 Дерево идеально сбалансировано, если для каждого его узла количества узлов в левом и правом поддереве различаются не более чем на 1. Предположим, например, что имеются следующие входные данные для дерева с 21 узлом: 21 8 0 11 15 19 20 21 7 3 2 1 5 6 4 13 14 10 12 !7 16 18 Тогда программа 4.3 строит идеально сбалансированное де- рево, показанное на рис. 4.23. Рнс.
428. Дерево, построенное с помошьв программы 4.8. Отметим простоту и ясность этой программы, достигнутые благодаря использованию рекурсивных процедур. Очевидно, что рекурсивные алгоритмы особенно уместны, когда программа должна обрабатывать данные, структура которых определена рекурсивно. Это вновь отражается в процедуре рг1пгггее, которая печатает полученное дерево: пустое дерево не печатается для поддерева уровня 7., а вначале печатается его левое поддерева, затем узел, который выделяется предшестнуюпцтми Т.
пробелами, и, наконец, печатается его правое поддерево. Преимушество рекурсивного алгоритма особенно наглядно по сравнению с его нерекурсивной формулировкой. с!итател1о предлагаешься проявить свою изобретательность н написать нерекурснвную программу, строящую такие же деревья, прежде чем смотреть на (4.41). Эта программа приведена без дальнейших комментариев и может служить упражнением для читателя, Ему предлагается выяснить, как и почему опа работает. 4.4. Древовадние струсгорм ргоягага ба!Бйгее[!при!,оигри!); 1уре ге1' = 1иой; иоде = гесогй'кеу: !и!ееег„' 1ег1, г!кйг: ге1' евб; тат 1,Пп1пг,х; !игекег; гоог,р ц,г,дту: гег; х: аггау [1 ..
30] о1 [стек) гесоп1 и; ул!екег; ф ге1 а; Ьея[п [Первое целое число есть число узлов] геа4[п); пегг[гоо!) ! пеи(а!ту); [Яиктивпый элемент) 1:=- 1; э[1].и:= п; а[1],пг:= гоог; (4.41) гереа1 п:= з[!] т; г:= з[!],г1'! 1: 1 — 1; [из стека) 11п = 0 1Ьев г[,г!ай!: =. п]1 е1ае Ьей]в р: — йпу; гереа1 п1: — и 41т 2„' пг:=- и — п1-1; геаг1(х); пея'(ц); д~.йеу;=- х,' 1:= !+1; з[!].и .'= пг; з[!] ту'! д] [в стек» и:= и1; р].1е~Я;=- д; р:= д ип111 п = О; ц[.1е11:=- в11; гТ,г!йЫ:= дту[.!ей ° 4 1111=0; ргупгггее [гоог[.пей!,О) епй . 4.4.2. Основные операции с бинарными деревьвми Имеется много задач, которые можно выполнять на древовидной структуре; распространенная задача — выполнение заданной операции Р с каждым элементом дерева.
Здесь Р рассматривается как царамстр более общей задачи посещения всех узлов, пли, как это обычно называют, обхода дерева. Если рассматривать эту задачу как единый последовательный процесс, то отдельные узлы посещаются в некотором определенном порядке и могут считаться расположенными линейно. В самом деле, описание многих алгоритмов сущесзвенно упрощается, если можно говорить о переходе к следующему элементу дерева, имея в виду некоторое упорядочение. Существуют трн принципа упорядочения, которые естественно вытекают из структуры деревьев.
Так же как и саму язо 4. Динами»еское ииформациоииыв структуры ййы узнаем трн формы записи выражений: обход сверху вниз дает префиксную зались, обход снизу вверх — постфикс- Я. Я~ Рвс. 424. Бинарное дерево. ную запись, а обход слева направо дает привычную инфиксную запись, хотя и без скобок, необходимых для определения порядка выполнения операций, Теперь выразим зти три метода обхода как трн нонкретные программы с явным параметром 1, означающим дерево, с которым они имеют дело, и неявным параметром Р, означающим операцию, которую нужно выполнить с каждым узлом. Введем следующие определения: 1уре те/ = )пос1е но;1е .== кесогй...
1е/Г,т(ИБ1: гсГ епй (4.42) Эти трн метода легко сформулировать в виде рекурсивных процедур; они вновь служат примером того, что действия древовидную структуру, их удобно выразить с помощью рекурсии, Обращаясь и бинарному дереву на рпс. 4.24, где Л обозначает корень, а А и  — левое и правое поддеревья, мы можем определить таяне три упорядочения: 1. Сверху вниж В, Л, В (посетить корень до поддеревьев1 2. Слави направо: А, р(, В 3.
Снизу вверх; Л, В, В (посетнть корень после поддеревьев) Обходя дерево на рнс. 4.20 и выписывая символы, находящиеся в узлах, в том порядке, в котором они встречаются, мы получаем следующие последовательности: 1. Сверху вниз; »+ а/Ь с — д»е1 2. Слева направо: а + Ь/с» д — е» 1 3. Снизу вверх: айс/+ де/» — » е.е. 1(ревавидкые структуры рскурсивно определенными структурами данных лучше всего описываются рекурсивными алгоритмами.
ргосейите ргеогйег(1: тег ) Ъей!и !Е 1:~ ш! Ъйеи Ъей!и Р(г). ргеогйег(1 ! ЛеЯ; (4.43) ргеогйег(Я.т1йй1) ртосеаие ров!огйег(1: тей; Ъей!и Ы 1 эа и(! 1Ъеи Ъей1и ролгогйег(11 .1еуг)1 розготйег®.тщй1)' Р(г) евй (4,44) ргосейпге 1иотйет (1: те~); Ъеа!и!11 Ф и!! 1Ъеи ьед!и 111отйег(г"1,1егг)! Р(г) 1лотйег(г ~,тцй1) (4.45) еий еий Отметим, что ссылка 1 передается как параметр-значение. Э;э отражает тот факт, что здесь существенна сама ссылка (указание) на рассматриваемое поддерево, а не переменнан, значение которой есть эта ссылка и которая могла бы изменить значение, если бы 1 передавался как параметр-переменная.
Пример подпрограммы, осуществляющей обход дерева,-- это подпрограмма печати дерева с соответствующим сдвигом, выделяющим каждый уровень узлов (см. программу 4.3). Бинарные деревья часто используются для представления множеств данных, элементы которых ищутся по уникальному, только им присущему ключу. Если дерево организовано таким образом, что для каждого узла й все ключи в левом поддереве меньше ключа 1ь а ключи в правом поддереве больше ключа 1ь то это дерево называется деревом поиска.
В дереве поиска можно найти место каждого ключа, двигаясь начиная от корня и переходя на левое или правое поддерево каждого узла в зависимости от значения его ключа. Как мы видели, 4. дииемиеесиие ип4вормечиопнме сгпиегковв 232 Рис. 4,25. Дерево поиска е барьером. Так как этот поиск проходит по единственному путя от корня к искомому узлу, его можно запрограммировать с помоцнно итерации (4.46): Йаст!вп 1ос(х: 1пгеяег; М геу): ген татуоипс(; Ьоо(еап; !еей!и 3оипс1: = .1а(ее; тт!н!е (г Ф и!!) Д вЂ”,1оипс(до Ьей!п !Г г(.йеу =- х !!вен уоипс1:= Ггие е!ае !1 г 1Лсеу > х !!веп г: = гт,1е1) е!ае 1.'= т~,гас епд; 1ос:= ! епй (4.46) Функция!ос(х,1) имеет значение пЦ, если в дереве с кор. нем ! не найдено ключа со значением и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
