Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Прохождение дерева



Прохождение дерева, т.е. последовательное обращение ко всем его узлам может выполняться с разными целями: просмотр (т.е. вывод на дисплей), сохранение в файл, поиск. Наиболее пpo- cтo реализуется прохождение с целью просмотра.
Порядок следования узлов дерева при его прохождении за- висит от того, каким образом нужно организовать доступ к узлам. Процесс получения доступа ко всем узлам прохождение дерева (или его обход). Прохождение дерева может выполняться по ме- тодам «в zлyduny» и «s шupuny».
Существует три способа прохождения дерева в глубину:

1. 
   Последовательный (он же инфиксный, симметричный, поперечный) — дерево проходится, начиная с левой ветви вверх к корню, затем к правой ветви;
   
2. 
   Нисходящий (префиксный или прямой) — от корня к левой
   

ветви, затем к правой;

3. 
   Восходящий (постфиксный или обратный) проходится
   

левая ветвь, затем правая, затем корень.

121

f

Последовательный: а b с d е f g Нисходящий: d b а с f е g

Восходящий: а с b е g f d Рис. 10.7 — Обход дерева
Под корнем здесь понимается как корень всего дерева, так и
корень текущей ветви (поддерева), т.е. текущий узел.
Последовательный способ удобен для сортировки данных. Хотя двоичное дерево не обязательно должно быть отсортирова- но (т.е. быть двоичных деревом поиска), во многих практиче- ских случаях это требуется. Порядок сортировки дерева опреде- ляется методом, которым дерево будет проходиться. Фактически сортировка как таковая для двоичного дерева поиска не требует- ся, поскольку при последовательном просмотре данные уже ока- зываются отсортированными по возрастанию.
Нисходящий способ удобен для сохранения дерева (т.е. дан- ных, в нём хранящихся) в файл так, чтобы при последующем считывании была бы полностью восстановлена структура дерева.
Восходящий обход может использоваться при полном уда- лении всего дерева (или выбранной ветви).
Рекурсивные процедуры прохождения дерева в последова- тельном (inordeг), нисходящем (preorde г) и восходящем (posГ ordeг) порядках на языке Паскаль.

procedure inorder(r: ptr); begin

if г = nil then exit; inorder(r’.left);
writeln( ... ); { Вывод информации } inorder(r’.right)
end;

122
procedure preorder(r: ptr); begin

if r = nil then exit;
writeln( ... ); { BuBoQ xH/OpMamxx }
preorder(r’.left); preorder(r’.right)
end;

procedure postorder(r: ptr);

begin
if r = nil then exit; postorder(r’.left); postorder(r’.right)
writeln( ... ); { BSBOQ xH OpMamxx
end;

ApryMeHT 3TiiX npouepyp — yKasilTéJlh Hit KO]3éHh BéTBH, KOTO- pyio Tpe6yeTcII HI1$JTH. Ecuii HymHo HH TH BCé ne]3éBO, ncnous3yeTcR yKasIITéJIh HH KO]3éHh Bcero pe]3éBI1. BhIXOp ris peKypcHBHOii npoue- pypsI n]3oncxopnT, KOFQI1 BCT]3éUIIéTCII Té]3MHHiIJIhHsIii ysen.

AHauor uHhIe npouepypsI HH R3hIKé Sri++.

void inorder(node* r)

if (r == NULL) return; inorder(r->left); cout<key<<" "; inorder(r->right);

void preorder(node* r)

if (r == NULL) return; cout<key<<” ", preorder(r->left); preorder(r->right);

123
void postorder(node* r)

if (!r) return; postorder(r->left); postorder(r — >right); cout<key<<" ",

O6xoд дe]3ëBIł If шиpиHf BЬIПOJIHIIëTCII c пoмoıılhЮ BCHoмora-
TëJIЬHOй cTpyKTypьI дIlHHЬIX — oчepenи ИЛH CTöKI1. PI1CCMOT]ЭИM BH-
]ЭHIIHT C HCHOJIh3 OBIIHH M OЧë]3ëДH, B KIIЧ CTBë KOTO]3OÎÎ BO3ЬMÖM
дBycBя3HЬIЙ KoльUëBOĞ cпиCOK, чTo ycTpaHяöT Hë 6XOØИMOCTЬ
H]3HMöHëHИЯ ØOHOJIHИTëJIЬHOÎÎ пe]3öMëHHOй — yKa3IITëJIII HH XBOCT
(или гoлoBy) oчepeдH, T.K. B дBycBяЗHOM CПHCKë C BЬIДëЛëHHЬIM Bë- дyщиM 3BöHOM гoJlOBlł H XBOCT HIIXOØЯTCR rtc› 6ë CTO]3OHЬI OT Beдy- ıılero 3BöHI1. П]ЭИMöHИM CHHCOK И OHë]3IłIIHH C HHM, ]3IłCCMOT]ЭëHHЬIö
B ПilpaгpaQax 9.2 и 9.5, дoпOJlHИB ИX TOJIЬKo фyHKцHëÎÎ HЗBЛëUëHHЯ
ØIlHHьIx (yзлa дe]3ëBI1) из oчe]3ëØH.

struct Link2 // Cпиcoк yзлoB

node* n; // Узeл Uepeвa Link2* next, *prev;

void Insert2(Link2* Pred, node* data)
Loc->п = data; // BøoU yзna Qe eBa B CMxCOK



node* Retrieve2(Link2* Del) // ИsBx ew eHxe
{ // yзлa из oчepeAи
node* a=Del->n; Delete2(Del); return a;
124
void WidthTraverse(пode *г)

if(!r) return;

Link2 *L2 = new Link2; // Локальная очередь L2— >next = L2;
L2— >prev = L2;
Insert2(L2->prev, r); // Занесение в очередь while(L2->prev!=L2) // Пока очередь не пуста

node* cur = Retrieve2(L2 — >next); printf("%d ", cur— >key);

if(cur->left)
Insert2(L2->prev, cur->left); if(cur->right)
Insert2(L2 — >prev, cur— >right); delete L2;

Результат обхода дерева, показанного на рисунке 10.7 с вы- водом содержимого узлов на экран, следующий:

d lo I а с е q.

Фактически дерево проходится по уровням: верхний (корень), второй слева направо и т.д.

Следует отметить, что дерево может быть организовано не только как динамическая связная структура данных, но и как массив. В зависимости от способа обхода дерева данные в эле- ментах такого массива могут размещаться по—разному, например, при нисходящем обходе начальный элемент массива оказывается корнем дерева, а при последовательном обходе — самым левым узлом (см рисунок 10.7). При использовании массива для по- строения дерева могут использоваться совсем другие операции для доступа к узлам, а также существенно усложняется процесс добавления в дерево узлов, количество которых превышает раз- мер массива.
Одна из возможностей применения такого дерева — дерево с фиксированным или с заранее известным максимальным числом узлов, а преимущество — очень быстрый доступ к любому узлу.

125
Строго говоря, содержимое любого массива при желании может интерпретироваться как дерево с соответствующим кор- нем. В частности, именно массив является основной структурой данных в алгоритме быстрого доступа к данным с возможностью их модификации, подсчёта суммы, нахождения максимума или минимума. Такой алгоритм получил название дерева отрезков . Ещё один подобный алгоритм называется деревом Фенвика.

3.