в корінь.
Для дерева на рис. 3 і 4 це дасть послідовність вузлів: B, D, E, G, F, C, A.
У відповідній рекурсивної процедурою дії будуть розташовуватися після рекурсивних викликів. Зокрема для бінарного дерева:
// Postorder Traversal - англійська назва для кінцевого порядкаPostorderTraversal ({Аргументи});
// Проходження лівого піддерева {Існує ліве піддерево} then ({Аргументи 2});
// Проходження правого піддерева {Існує праве піддерево} then ({Аргументи 3});
// Проходження кореня ({Аргументи});;
.3 Подання дерева в пам'яті комп'ютера
Якщо деяка інформація розташовується у вузлах дерева, то для її зберігання можна використовувати відповідну динамічну структуру даних. На Паскалі це робиться за допомогою змінної типу запис (record), яка містить покажчики на піддерева того ж типу. Наприклад, бінарне дерево, де в кожному вузлі міститься ціле число можна зберегти за допомогою змінної типу PTree, який описаний нижче:
= TTree; = record: integer;, RightSubTree: PTree;;
Кожен вузол має тип PTree. Це покажчик, тобто кожен вузол необхідно створювати, викликаючи для нього процедуру New. Якщо вузол є кінцевим, то його полям LeftSubTree і RightSubTree присвоюється значення nil. В іншому випадку вузли LeftSubTree і RightSubTree також створюються процедурою New. p align="justify"> Схематично одна така запис зображена на рис. 5. br/>В
Рис. 5. Схематичне зображення записи типу TTree. br/>
Запис має три поля: Inf - деяке число, LeftSubTree і RightSubTree - покажчики на записи того ж типу TTree.
Приклад дерева, складеного з таких записів, зображений на малюнку 6.
В
Рис. 6. Дерево, складене із записів типу TTree. br/>
Кожна запис зберігає число і два покажчика, які можуть містити або nil, або адреси інших записів того ж типу.
Якщо ви раніше не працювали зі структурами складаються з записів, які містять посилання на записи того ж типу, то рекомендуємо ознайомитися з матеріалом про рекурсивних структурах даних <# "251" src = "doc_zip29.jpg"/>
Рис. 6. Деревце. br/>
Рекурсивна процедура, очевидно повинна малювати одну лінію (стовбур до першого розгалуження), а потім викликати сама себе для малювання двох піддерев. Піддерева відрізняються від містить їх дерева координатами початкової точки, кутом повороту, довжиною ствола і кількістю містяться в них розгалужень (на одне менше). Всі ці відмінності слід зробити параметрами рекурсивної процедури. p> Приклад такої процедури, написаний на Delphi, представлений нижче:
procedure Tree (: TCanvas;// Canvas, на якому буде малюватися дерево, y: extended;// Координати кореня: extende...
