Ðåêóðñèâíàÿ ïðîöåäóðà íóìåðàöèè óçëîâ áèíàðíîãî äåðåâà

        (èíôèêñíûé ïîðÿäîê).

   ÂÕÎÄ:  ÊÎÐÅÍÜ - ññûëêà íà êîpåíü äåpåâà,

   ÂÛÕÎÄ: ìàññèâ ÍÎÌÅÐ ñ íîìåpàìè âåpøèí

  

        procedure ÈÍÔ_ÐÅÊ(ÊÎÐÅÍÜ):

        BEGIN

          N := 1;

          ÈÍÔÍÓÌ(ÊÎÐÅÍÜ)

        END

 

        procedure ÈÍÔÍÓÌ(ÓÇÅË):

           BEGIN

   1             if ËÅÂÑÛÍ(ÓÇÅË) /= 0

                  then  ÈÍÔÍÓÌ(ËÅÂÑÛÍ(ÓÇÅË));

   2             ÍÎÌÅÐ(ÓÇÅË) := N;

   3             N := N + 1;

   4             if ÏÐÀÂÑÛÍ(ÓÇÅË) /= 0

                  then  ÈÍÔÍÓÌ(ÏÐÀÂÑÛÍ(ÓÇÅË));

           END

  

ÒÅÎÐÅÌÀ 1. Ïðîöåäóðà ÈÍÔ_ÐÅÊ íóìåðóåò âñå âåðøèíû áèíàðíîãî äåðåâà T=(V,E)d â èíôìêñíîì ïîðÿäêå çà âðåìÿ    O(|V|).

 

   Ïðîöåäóðà íóìåðàöèè óçëîâ áèíàðíîãî äåðåâà â òîì æå

   ïîðÿäêå áåç ðåêóðñèè.

   M - ìàãàçèí (ñòåê)

 

    PROCEDURE ÈÍÔ(ÊÎÐÅÍÜ):

          BEGIN

                N := 1;

                ÓÇÅË := ÊÎÐÅÍÜ;

                ÑÎÇÄÀÒÜ_ÑÒÅÊ(M);

       LEFT:    while ËÅÂÑÛÍ(ÓÇÅË) /= 0

                  do

                    BEGIN  ÂÒÎËÊ(Ì,ÓÇÅË);

                           ÓÇÅË := ËÅÂÑÛÍ(ÓÇÅË)

                    END;

       NOM:     ÍÎÌÅÐ(ÓÇÅË) := N;

                N := N + 1;

                if ÏÐÀÂÑÛÍ(ÓÇÅË) /= 0

                  then

                      BEGIN  ÓÇÅË := ÏÐÀÂÑÛÍ(ÓÇÅË);

                             goto  LEFT

                      END;

                if not(ÏÓÑÒ(Ì))

                  then

                      BEGIN ÓÇÅË := ÂÅÐÕ(Ì);

                            ÂÛÒÎËÊ(Ì);

                            goto NOM

                      END

          END

 

 

ÒÅÎÐÅÌÀ 2. Ïðîöåäóðà ÈÍÔ íóìåðóåò âñå âåðøèíû áèíàðíîãî äåðåâà T=(V,E)d â èíôìêñíîì ïîðÿäêå çà âðåìÿ    O(|V|).