31.Навести алгоритм зворотного порядоку (postorder) обходу дерева.

-відвідати ліве піддерево

-відвідати праве піддерево

-відвідати корінь

Procedure IncoderTraversal (<apr.>);

Begin

If <існує ліве дерево> then

InorderTraversal (<apr.2>);

DoSomething (<apr.>); //проходження корення

If <існує праве дерево> then

InorderTraversal (<apr.3>);

End.

32. Навести алгоритм обходу дерева в кінцевому порядку.

-пройти всі піддерева зліва на право

-потрапити в корінь

Procedure IncoderTraversal (<apr.>);

Begin

If <існує ліве дерево> then

InorderTraversal (<apr.2>);

If <існує праве дерево> then

InorderTraversal (<apr.3>);

DoSomething (<apr.>); //проходження корення

End.

33. Ханойські вежі. За умовою задачі необхідно перенести N дисків з стержня 1 на стержень 3, використовуючи стержень 2 як проміжний. При переносі необхідно дотримуватись наступних правил:

на кожному кроці з стержня на стержень переноситься тільки один верхній диск;

диск не можна переміщувати на диск меншого діаметру.

Вивести послідовність дій при переносі дисків.

В основній програмі задається значення N - кількість дисків, які потрібно перенести. Для того, щоб перенести N дисків з 1-го на 3-ій стержень, потрібно перенести вежу з (N-1) - го диска з 1-го на проміжний 2-ий стержень, що заборонено умовою задачі, тому для цього викликається рекурсивна процедура, вхідними параметрами якої будуть кількість дисків і номери стержнів ( з якого на який потрібно перенести вежу з дисків ). Номер проміжного стержня рахується за формулою d3=6-d1-d2. Ці виклики продовжуватимуться доти, поки кількість дисків у вежі не стане рівна 1, тобто можна буде напряму перенести диск із стержня d1 на d2, не використову- ючи проміжний стержень. В результаті вежа з (N-1) - го диска переноситься із 1-го стержня на проміжний стержень 2, звільняючи найбільший диск на стержні 1, що дозволяє його перенести на стержень 3. Аналогічно вежа з (N-1) - го диска переноситься із проміжного стержня 2 на стержень 3.

{Ханойські вежі}

Uses Crt;

Var

n:word;

p:longint;

procedure Perenos(s1,s2,n:word);

var

s3:word;

begin

if n>0 then

begin

s3:=6-s1-s2;

Perenos(s1,s3,n-1);

write(s1,' ---> ',s2,' '); p:=p+1;

Perenos(s3,s2,n-1);

end;

end;

Begin

ClrScr;

Write('n= ');

Readln(n);

p:=0;

Perenos(1,2,n-1);

Write(1,' ---> ',3,' '); p:=p+1;

Perenos(2,3,n-1);

writeln;

Writeln('p= ',p);

Gotoxy(30,22);

Writeln('Для продовження Enter');

readln;

End.

(це з нету)

Лекції:

Procedure Hanoi (n,a,b,c:integer);

Begin

If n>1 then

Begin

Hanoi (n-1,a,c,b);

Writeln(a,’→’,b);

Hanoi (n-1,c,b,a);

End else

Writeln(a,’→’,b);

End;

Безліч рекурсивно викликаних процедур в даному випадку утворює дерево з обходом в зворотньому порядку..

34. Навести синтаксичний аналіз арифметичних виразів. Синтакси́чний ана́ліз (па́рсинг) (англ. parsing) — в інформатиці це процес аналізу вхідної послідовності символів, з метою розбору граматичної структури згідно із заданоюформальною граматикою. Синтаксичний аналізатор (англ. parser) — це програма або частина програми, яка виконує синтаксичний аналіз. Приклад розбору виразу в дерево

Під час синтаксичного аналізу текст оформлюється у структуру даних, зазвичай — в дерево, яке відповідає синтаксичній структурі вхідної послідовності, і добре підходить для подальшої обробки. Зазвичай синтаксичні аналізатори працюють в два етапи: на першому ідентифікуються осмислені токени (виконується лексичний аналіз), на другому створюється дерево розбору.

Найчастіше парсери використовуються для розбору тексту вихідного коду комп'ютерних мов програмування. Вони мають відносно просту граматику з невеликою кількістю виключень. Парсер мови програмування звичайно заснований на контекстно-вільній граматиці, оскільки на її основі можна написати простий та ефективний парсер.