Часть I. Используя очередь или стек (считать уже описанными их типы и операции над ними ) описать процедуру или функцию

Используя очередь или стек (считать уже описанными их типы и операции над ними) описать процедуру или функцию, которая:

Находит в непустом дереве Т длину пути от корня до ближайшей вершины с элементом Е, если Е не входит в Т, то за ответ принять -1.

Текст программы:

Program T854a;

Uses CRT;

Const

E='C';

Type

Tree=^Root;

Root=Record

Element:Char;

Left,Right:Tree;

End;

Stack=^Description;

Description=Record

BTree:Tree;

Process:boolean;

Next:Stack;

End;

Var

T:Tree;

S:Stack;

{создает поддерево с двумя листьями}

Procedure SubTreeBuilding(var P:Tree);

Var

TLeft,TRight:Tree;

Begin

New(P);

New(TLeft);

New(TRight);

TLeft^.Left:=nil;

TLeft^.Right:=nil;

TRight^.Left:=nil;

TRight^.Right:=nil;

TLeft^.Element:=Chr(64+Random(28));

TRight^.Element:=Chr(64+Random(28));

P^.Element:=Chr(64+Random(28));

P^.Left:=TLeft;

P^.Right:=TRight;

End;

{создает дерево}

Procedure TreeBuild;

Begin

Randomize;

SubTreeBuilding(T);

SubTreeBuilding(T^.Left);

SubTreeBuilding(T^.Right);

SubTreeBuilding(T^.Left^.Left);

SubTreeBuilding(T^.Right^.Left);

SubTreeBuilding(T^.Left^.Right);

SubTreeBuilding(T^.Right^.Right);

SubTreeBuilding(T^.Left^.Left^.Left);

SubTreeBuilding(T^.Right^.Left^.Left);

SubTreeBuilding(T^.Left^.Right^.Left);

SubTreeBuilding(T^.Right^.Right^.Left);

SubTreeBuilding(T^.Left^.Left^.Right);

SubTreeBuilding(T^.Right^.Left^.Right);

SubTreeBuilding(T^.Left^.Right^.Right);

SubTreeBuilding(T^.Right^.Right^.Right);

SubTreeBuilding(T^.Left^.Left^.Right^.Right);

SubTreeBuilding(T^.Right^.Left^.Right^.Right);

{T^.Right^.Left^.Right^.Right^.Right^.Element:='E';}

End;

{************* Функции и процедуры работы со стеком *****************}

{** Процедура создания и очистки стека **}

Procedure InitStack(var S1:Stack);

var

P1,P2:Stack;

Begin

While S1<>nil Do Begin

P1:=S1^.Next;

Dispose(S1);

S1:=P1;

End;

End;

{** Процедура проталкивания элемента в стек **}

Procedure Shoot(E:Tree);

var

P:Stack;

Begin

New(P);

P^.BTree:=E;

P^.Process:=false;

P^.Next:=S;

S:=P

End;

{ **Функция выталкивания элементов из стека **}

Procedure Pull(var S1:Stack);

var

P:Stack;

Begin

If S1<>nil Then Begin

P:=S1;

S1:=S1^.Next;

Dispose(P);

P:=nil;

End

Else

S1:=nil;

End;

{Функция определения размера стека}

Function Detect_Stack_Size(S1:Stack):Integer;

var

i:Integer;

Begin

i:=0;

While S1<>nil Do begin

inc(i);

S1:=S1^.Next;

End;

Detect_Stack_Size:=i;

End;

{находит длину пути от корня до ближайшей вершины с элементом Е}

Procedure Count_Waypoints(T1:Tree);

var

i:Integer;

P:Tree;

Begin

InitStack(S);

Shoot(T1); {проталкиваем в стек корень дерева}

i:=0;

{****** Цикл обхода дерева ********}

Repeat

inc(i);

P:=S^.Btree; {P-узел на верхушке стека}

{** Если текущий элемент стека - лист **}

If ((P^.Left=nil) and (P^.Right=nil) and (Detect_Stack_Size(S)>0)) Then Begin

Pull(S);

S^.Process:=true;

{Если данный лист - не правый сын своего отца}

If P<>S^.BTree^.Right Then Begin

S^.Process:=true;

Shoot(S^.BTree^.Right); {проталкиваем в стек его правого брата}

End

End

Else Begin {** элемент на верхушке стека-промежуточный узел **}

If (not S^.Process) Then Begin {данное дерево еще не обработано}

S^.Process:=false;

Shoot(P^.Left); {протолкнуть в стек левого сына}

End

Else Begin {данное дерево уже обработано}

Pull(S);

If ((Detect_Stack_Size(S)>0) And (P<>S^.Btree^.Right)) {элемент-не корень}

Then Begin {и не правый сын своего отца}

S^.Process:=true;

Shoot(S^.Btree^.Right); {проталкиваем правого брата}

End;

End;

End;

Until ((Detect_Stack_Size(S)=0) or (S^.Btree^.Element=E));

If ((Detect_Stack_Size(S)=0) And (S^.Btree^.Element<>E)) Then

WriteLn('Указанное значение "',E,'" в дереве не найдено, результат равен "1"')

Else

WriteLn('длина пути к элементу со значением "',E,'" - ',Detect_Stack_Size(S)-1,' узла(ов)');

WriteLn('Всего произведено ',i,' перемещений по узлам дерева');

End;

Begin

TreeBuild;

WriteLn;

WriteLn('Результат обхода дерева:');

Count_Waypoints(T);

WriteLn;

WriteLn('Press any key...');

Repeat Until Keypressed;

End.

Результат работы программы:

Результат обхода дерева: длина пути к элементу со значением "C" - 2 узла(ов) Всего произведено 15 перемещений по узлам дерева   Press any key...