Программа на бинарные деревья

[Jetbalance]

Здравствуйте. Не знаю, сможет ли кто-нибудь помочь с задачей...
Пожалуйста, если не сложно и есть время, набросайте код... (Вопрос жизни и смерти!)

Сама задача: Проверить монотонность убывания ширины уровня дерева.

Нужно написать на Паскале и Си. Из набросков у меня есть Паскаль. Но выкладывать моё "творчество" вряд ли стоит...

[Рико]

помочь могу, не на халяву разумеется

[VIK_aka_TOR]

Сообщение от Jetbalance

Из набросков у меня есть Паскаль. Но выкладывать моё "творчество" вряд ли стоит...

быть может и наши наброски не следует...

кинь.. посмотрим... авось что то и получится... если лень... видимо смерть будет... иначе лишь за материальное вознаграждение ...

[Jetbalance]

В общем, как-то мне удалось найти программу (см. ниже) на паскале, которая решает много лишнего. Собственно, что я смог сделать: дописать пару строчек.

PHP код:

program B_Tree;
type PTree = ^ TTree; {Tip- ukazatel na element dereva}
     TTree = record el: integer; {tip el-ta dereva}
                    left, right: PTree; {ukazateli na lev i prav.sina}
             end;

     { type el-tov steka - informacija - eto ukazatel na el-t dereva, pred - uk-l na predidush. el-t }
     PStek= ^TStek;
     TStek= record Inf:  PTree;
                   pred: PStek;
             end;


var  Tree {ukaz. na koren dereva}, p, pr: PTree;
     elTree: integer;

     i,j: integer;
     c: char;

 {===================Stack ================================================}
 procedure InitStek(var top: PStek); { èíèöèàëèçàöèÿ ñòåêà }
 begin top := nil;
 end;

 {proverka Steka na pustoty. true esli pusto }
 function PustStek(top: PStek): boolean;
 begin PustStek := top = nil;
 end;

 procedure InStek(el: Ptree;  var top: PStek ); { äîáàâëåíèå â ñòåê ýë-òà ñî çíà÷åíèåì el }
 var p: PStek ;
 begin new(p); { âûäåëèëè ïàìÿòü ïîä íîâûé ýëåìåíò }
       p^.inf := el;
       p^.pred := top; { óêàçàòåëü íà ïðåäûäóùèé ýëåìåíò áåðåì èç óêàçàòåëÿ íà ïîñë ýëåìåíò ñòåêà }
       top := p; { òåïåðü íîâûé ýëåìåíò ñòàë ïîñë. ýëåìåíòîì ñòåêà, íà íåãî è áóäåò óêàçûâàòü top}
  end;

  procedure OutStek(var el: PTree;  var top: PStek); {óáèðàåì èç íåïóñòîãî ñòåêà ïîñë ýëåìåíò}
  var p: PStek;
  begin el := top^.inf; { çàïîìíèëè çíà÷åíèå ýë-òà }
        p  := top;     { çàïîìíèëè ññûëêó íà ýë-ò}
        top := top^.pred; {òåïåðü óæå ññûëàåìñÿ íà ïðåäïîñëåäíèé ýë-ò ñòåêà}
        dispose(p);   {îñâîáîæäàåì ïàìÿòü, áûâøóþ ïîä óäàëÿåìûì ýë-òîì }
  end ;


{===============Be-derevo ===========================================}
 {inicialisacija dereva }
 procedure InitTree(var tree:PTree);
 begin
   tree := nil;
 end;

 {proverka dereva na pustoty. true esli pusto }
 function PustTree(tree:PTree): boolean;
 begin PustTree := tree = nil;
 end;

 {-------------------------------------------------------------------}
 {dobavlenie v derevo }
 procedure AddInTree(el: integer; var tree:PTree);
 var p, pr, t: PTree;
 begin new(t); t^.el := el; {sozdaem novii el-t dereva}
       t^.left := nil; t^.right := nil; {nov.el-t bydet listom dereva}
       p:= tree; pr:=nil;
       {ishem mesto privjazki }
       while p<>nil do
       begin pr := p; {"predidushii" ukazatel}

             if p^.el > el then p:=P^.left
             else p:=p^.right;
       end;
       if tree = nil then tree := t {pervii uzel dereva}
       else if pr^.el>el then pr^.left := t
            else pr^.right := t;

 end;
 {--------------------------------------------------------------------}
 { Prjamoi obxod (pechat) dereva - uzel, levoe podderevo, pravoe podderevo - rekursuja }
 procedure PrintTree(tree: PTree);
 begin write(tree^.el, ' ');
       if tree^.left<>nil then PrintTree(tree^.left);
       if tree^.right<>nil then PrintTree(tree^.right);
 end;
 {------------------------------------------------------------------------}
 {Udalenie dereva}
 procedure ClearTree(var p:Ptree);
 begin if p^.left <> nil then ClearTree(p^.left);
       if p^.right <>nil then ClearTree(p^.right);
       dispose(p); p:=nil;
 end;

 { obxod dereva po urovnjam s pechatju kol-va el-tov na kazdom urovne }
 procedure ObxodPoUrovn(tree:Ptree);
 var elStek: PTree;
     top1, top2: PStek; { ukaz. na verchini vspomog. stackov }
     Uroven, Kol, k, z : integer;
 begin

     InitStek(top1); InitStek(top2);

     InStek(tree, top1); {&#226;çÿòü êîðåíü, ïîëîæèòü â ñòåê1. }

     Uroven := 0; k:=0;

     repeat {&#239;îâòîðèòü }

       { &#243;âåëè÷èòü óðîâåíü íà 1, îáíóëèòü êîë-âî ýë-òîâ íà ïåðåõîäå ê ñëåäóþùåìó óðîâíþ.}
       Kol := 0;
       Uroven := Uroven +1;

       writeln('Elementi ', Uroven,' yrovnja:');


       while not PustStek(top1) do {&#239;îêà ñòåê1 íå ïóñò}
{ &#226;ûíóòü î÷åðåäíîé ýëåìåíò, óâåëè÷èòü êîë-âî íà î÷åðåäíîì óðîâíå, ïîëîæèòü åãî âî 2 ñòåê}
       begin OutStek(elStek, top1);
             kol := kol + 1;
             write(elStek^.el,' ');
             InStek(elStek, top2);
       end;
       writeln;
       writeln('Kol-vo elementov ', Uroven,' yrovnja:', kol); 


[Jetbalance]

PHP код:

       if (kol>k) then k:=kol else   begin
                                     writeln ('Монотонность нарушена');
                                     break;
                                     end;

       while not PustStek(top2) do {ïîêà ñòåê2 íå ïóñò}
{ âûíóòü èç íåãî î÷åðåäíîé ýëåìåíò, ïîëîæèòü â ñòåê1 ïðàâîãî è ëåâîãî ñûíà ýòîãî ýë-òà.}
       begin OutStek(elStek, top2);

             if elStek^.right<>nil then
                    InStek(elStek^.right, top1);

             if elStek^.left<>nil then
                    InStek(elStek^.left,  top1);
       end;

     until PustStek(top1); {&#239;îêà ñòåê1 íå áóäåò ïóñò }
 end;




 {===================Osn programma ========================================}
begin
  InitTree(tree);

  writeln('Sozdanie dereva: ');
  repeat
    write('element dereva = ');
    readln(elTree);
    AddInTree(elTree, tree);
    write('Prodolzhit vvod (Y/N)?'); readln(c);
  until (c = 'N') or (c = 'n');

  if not PustTree(tree) then
  begin writeln('Obxod dereva (prjamoi):');
        PrintTree(tree);

        writeln;
        write('Nazmite ENTER...'); readln;

        writeln('Podshet uzlov po urovnjam: ');
        ObxodPoUrovn(tree);

        ClearTree(tree);
  end;
  write('Nazmite ENTER...'); readln;
end. 


В программу я добавил:

PHP код:

if (kol>k) then k:=kol else   begin
                                     writeln ('Монотонность нарушена');
                                     break;
                                     end; 


В итоге, нагруженная лишним программа, решающая много лишнего. Сдаётся мне, есть способы полегче... Но что конкретно из неё удалять, я не могу понять, т.к. можно и лишнего снести...)

Если есть идеи по этому поводу, буду рад выслушать...
P.S.Извиняюсь, за некоторые комментарии в программе.