Algoritmusok 4

1. Algoritmus: PREORD(INFO, LEFT, RIGHT, ROOT). Az algoritmus az irányítással megegyező sorrendben bejárja a memóriában lévő T bináris fát, miközben a fa csomópontjaira a PROCESS-szel jelölt műveleteket alkalmazza. A STACK tömb ideiglenesen tárolja a csomópontok címét.
1. [Kiindulásként a NULL ráhelyezése a STACK-re és a PTR inicializálása.]
   TOP:=1, STACK[1]:=NULL, PTR:=ROOT.
2. Repeat 3. to 5. lépés while PTR . NULL:
3. A PROCESS alkalmazása az INFO[PTR] csomópontra.
4. [Van-e jobb oldali "gyermek"?]
   If RIGHT[PTR] . NULL, then: [Ráhelyezés a STACK-re.]
   TOP:=TOP+1, STACK[TOP]:=RIGHT[PTR].
   [Az If szerkezet vége.]
5. [Van-e bal oldali "gyermek"?]
   If LEFT[PTR] . NULL, then:
   PTR:=LEFT[PTR].
   Else: [Leemelés a STACK-ről.]
   PTR:=STACK[TOP], TOP:=TOP-1.
   [Az If szerkezet vége.]
   [A 2. lépésben elkezdődött ciklus vége.]
6. Exit.




2. Algoritmus: INORD(INFO, LEFT, RIGHT, ROOT). Az algoritmus - szimmetrikus sorrendben - bejárja a memóriában lévő T bináris fát, miközben a szóban forgó fa csomópontjaira a PROCESS-szel jelölt műveletet alkalmazza. A STACK tömb ideiglenesen tárolja a csomópontok címét.
1. [Kiindulásként a NULL ráhelyezése a STACK-re és a PTR inicializálása.]
   TOP:=1, STACK[1]:=NULL, PTR = ROOT.
2. Repeat while PTR . NULL: [A bal szélső útvonal ráhelyezése a STACK-re.]
1. TOP:=TOP+1, STACK[TOP]:=PTR. [A csomópont elmentése.]
2. PTR:=LEFT[PTR]. [A PTR aktualizálása.]
   [A ciklus vége.]
3. PTR:=STACK[TOP], TOP:=TOP-1. [A csomópont leemelése a veremről.]
4. Repeat 5. to 7. lépés while PTR . NULL: [Visszalépés.]
5. A PROCESS alkalmazása az INFO[PTR] csomópontra.
6. [Van-e jobboldali "gyermek"?] If RIGHT[PTR] . NULL, then:
1. PTR:=RIGHT[PTR].
2. Go to 3. lépés.
   [Az If szerkezet vége.]
7. PTR:=STACK[TOP], TOP:=TOP-1. [A csomópont leemelése a veremről.] [A 4. lépésben elkezdődött ciklus vége.]
8. Exit.




3. Algoritmus: POSTORD(INFO, LEFT, RIGHT, ROOT). Az algoritmus az irányítással ellenkező sorrendben bejárja a memóriában lévő T bináris fát, miközben a csomópontjaira a PROCESS-szel jelölt műveletet alkalmazza. A STACK tömb ideiglenesen tárolja a csomópontok címét.
1. [Kiindulásként a NULL ráhelyezése a STACK-re és a PTR inicializálása.]
   TOP:=1, STACK[1]:=NULL, PTR:=ROOT.
2. [A bal szélső útvonal ráhelyezése a STACK-re.]
   Repeat 3. to 5. lépés while PTR . NULL:
3. TOP:=TOP+1, STACK[TOP]:=PTR.
   [A PTR ráhelyezése a STACK-re.]
4. If RIGHT[PTR] . NULL, then: [Ráhelyezés a STACK-re.]
   TOP:=TOP+1, STACK[TOP]:=-RIGHT[PTR]
   [Az If szerkezet vége.]
5. PTR:=LEFT[PTR]. [A PTR mutató aktualizálása.]
   [A 2. lépésben elkezdődött ciklus vége.]
6. PTR:=STACK[TOP], TOP:=TOP-1.
   [A csomópont leemelése a STACK-ről.]
7. Repeat while PTR>0:
1. A PROCESS alkalmazása az INFO[PTR] csomópontra.
2. PTR:=STACK[TOP], TOP:=TOP-1.
   [A csomópont leemelése a STACK-ről.]
   [A ciklus vége.]
8. If PTR<0, then:
1. PTR:=-PTR.
2. Go to 2. lépés.
   [Az If szerkezet vége.]
9. Exit.




4. Eljárás: FIND(INFO, LEFT, RIGHT, ROOT, ITEM, LOC, PAR). Legyen adott a T bináris, rendezett fa a memóriában, valamint az ITEM információ. Az eljárás a T fában megkeresi az ITEM helyét (LOC), valamint az ITEM szülőjének helyét (PAR). Három különleges eset létezik:
1. A LOC . NULL és a PAR = NULL azt jelzi, hogy üres a fa;
2. A LOC . NULL és a PAR = NULL azt jelzi, hogy az ITEM a T gyökerében helyezkedik el;
3. A LOC = NULL és a PAR . NULL azt jelzi, hogy az ITEM nem fordul elő a T-ben, ezért - a PAR helyen lévő N csomópont gyermekeként - hozzá kell kapcsolni a T-hez.
1. [Üres fa?]
   If ROOT = NULL, then LOC:=NULL, PAR:=NULL, Return.
2. [Az ITEM a gyökérben van?]
   If ITEM=INFO[ROOT], then LOC:=ROOT, PAR:=NULL, Return.
3. [A PTR és a SAVE mutató inicializálása.]
   If ITEMPTR:=LEFT[ROOT], SAVE:=ROOT.
   Else:
   PTR:=RIGHT[ROOT], SAVE:=ROOT.
   [Az If szerkezet vége.]
4. Repeat 5. and 6. lépés while PTR. NULL:
5. [Megvan az ITEM tétel?] If ITEM=INFO[PTR], then LOC:=PTR, PAR:=SAVE, Return.
6. If ITEMSAVE:=PTR, PTR:=LEFT[PTR].
   Else:
   SAVE:=PTR, PTR:=RIGHT[PTR].
   [Az If szerkezet vége.]
   [A 4. lépésben elkezdődött ciklus vége.]
7. [Sikertelen keresés.] LOC:=NULL, PAR:=SAVE.
8. Return.




5. Algoritmus: INSBST(INFO, LEFT, RIGHT, ROOT, AVAIL, ITEM, LOC). Legyen adott a memóriában a T bináris, rendezett fa, valamint az ITEM információ! Az algoritmus megkeresi a T-ben az ITEM tétel LOC helyét, vagy az ITEM tételt - új csomópontként - beszúrja a T fa LOC helyére.
1. Call FIND(INFO,LEFT, RIGHT, ROOT, ITEM, LOC, PAR).
   [A IV. eljárás.]
2. If LOC . NULL, then Exit.
3. [Az ITEM bemásolása az AVAIL lista első szabad csomópontjába.]
1. If AVAIL=NULL, then: Write: TÚLCSORDULÁS, Exit.
2. NEW:=AVAIL, AVAIL:=LEFT[AVAIL], INFO[NEW]:=ITEM.
3. LOC:=NEW, LEFT[NEW]:=NULL, RIGHT[NEW]:=NULL.
4. [Az ITEM beszúrása a fába.]
   If PAR=NULL, then_
   ROOT:=NEW.
   Else if ITEMLEFT[PAR]:=NEW.
   Else:
   RIGHT[PAR]:=NEW.
   [Az If szerkezet vége.]
5. Exit.




6. Eljárás: CASE(INFO, LEFT, RIGHT, ROOT, LOC, PAR). Az eljárás törli a LOC helyen lévő N csomópontot, ha az N csomópontnak nulla vagy egy gyermeke van. A PAR mutató megadja az N-hez tartozó szülő csomópont helyét, vagy jelzi - a PAR=NULL feltétellel -, hogy az N a gyökércsomópont. A CHILD mutató megadja az N csomópont gyermekének helyét, vagy jelzi - a CHILD=NULL feltétellel - hogy az N-nek nincs gyermeke.
1. [A CHILD mutató inicializálása.]
   If LEFT[LOC]=NULL and RIGHT[LOC]=NULL, then:
   CHILD:=NULL.
   Else if LEFT[LOC].NULL, then:
   CHILD:=LEFT[LOC].
   Else:
   CHILD:=RIGHT[LOC].
   [Az If szerkezet vége.]
2. If PAR.NULL, then:
   If LOC=LEFT[PAR], then:
   LEFT[PAR]:=CHILD.
   Else:
   RIGHT[PAR]:=CHILD.
   Else:
   ROOT:=CHILD.
   [Az If szerkezet vége.]
3. Return.




7. Eljárás: CASEB(INFO, LEFT, RIGHT, ROOT, LOC, PAR). Az eljárás törli a LOC helyen lévő N csomópontot, ha az N csomópontnak két gyermeke van. A PAR mutató megadja az N-hez tartozó szülő csomópont helyét, vagy jelzi - a PAR=NULL feltétellel -, hogy az N gyökércsomópont. A SUC mutató megadja az N-et szimmetrikus sorrendben követő elem helyét, a PARSUC pedig tárolja az N-et szimmetrikus sorrendbe követő elem szülőjének helyét.
1. [A SUC és a PARSUC elem megkeresése.]
1. PTR:=RIGHT[LOC], SAVE:=LOC.
2. Repeat while LEFT[PTR] . NULL:
   SAVE:=PTR, PTR:=LEFT[PTR].
   [A ciklus vége.]
3. SUC:=PTR, PARSUC:=SAVE.
2. [A szimmetrikus sorrend szerint következő elem törlése a VI. Eljárás segítségével.]
   Call CASEA(INFO, LEFT, RIGHT, ROOT, SUC, PARSUC).
3. [Az N csomópont felcserélése az N-et szimmetrikusan követő elemmel.]
1. If PAR.NULL, then:
   If LOC=LEFT[PAR], then:
   LEFT[PAR]:=SUC.
   Else:
   RIGHT[PAR]:=SUC.
   [Az If szerkezet vége.]
   Else:
   ROOT:=SUC.
   [Az If szerkezet vége.]
2. LEFT[SUC]:=LEFT[LOC], RIGHT[SUC]:=RIGHT[LOC].
4. Return.




8. Algoritmus: DEL(INFO, LEFT, RIGHT, ROOT, AVAIL, ITEM). Legyen adott a T bináris, rendezett fa a memóriában, valamint az ITEM információ! Az algoritmus törli a fából az ITEM-et tartalmazó csomópontot.
1. [Az ITEM információt tartalmazó csomópont és a hozzá tartozó szülő helyének megkeresése a IV. eljárás segítségével.]
   Call FIND(INFO, LEFT, RIGHT, ROOT, ITEM, LOC, PAR).
2. [Az ITEM szerepel a fában?]
   If LOC=NULL, then Write: az ITEM nem szerepel a fában.
   Exit.
3. [Az ITEM-et tartalmazó csomópont törlése.]
   If RIGHT[LOC].NULL and LEFT[LOC].NULL, then:
   Call CASEB(INFO, LEFT, RIGHT, ROOT, LOC, PAR).
   Else:
   Call CASEA(INFO, LEFT, RIGHT, ROOT, LOC, PAR).
   [Az If szerkezet vége.]
4. [A törölt csomópont visszakapcsolása az AVAIL listába.]
   LEFT[LOC]:=AVAIL, AVAIL:=LOC.
5. Exit.




9. Eljárás: INSHEAP(TREE, N, ITEM]. Legyen adott az N elemet tartalmazó H halom - ezt a TREE tömb tárolja -, valamint az ITEM információ! Az eljárás az ITEM-et beszúrja a H halomba. A PTR az éppen aktuális helyet tárolja az ITEM léptetése közben, a PAR pedig az ITEM szülőjének helyét.
1. [Az új csomópont hozzákapcsolása a fához és a PTR inicializálása.]
   N:=N+1, PTR:=N.
2. [Az ITEM helyének megkeresése.]
   Repeat 3. to 6. lépés while PTR>1.
3. Set PAR:=[PTR/2] [A szülő csomópont helye.]
4. If ITEM<=TREE[PAR], then:
   TREE[PTR]:=ITEM, Return.
   [Az If szerkezet vége.]
5. TREE[PTR]:=TREE[PAR]. [A csomópont lefelé léptetése.]
6. PTR:=PAR. [A PTR aktualizálása.]
   [A 2. lépésben elkezdődött ciklus vége.]
7. [Az ITEM beállítása a H gyökerére.]
   TREE[1]:=ITEM.
8. Return.




10. Eljárás: DELHEAP(TREE, N, ITEM). Az N elemű H halmot a TREE tömb tárolja. Az eljárás a H halom TREE[1] gyökerét hozzárendeli az ITEM változóhoz, és a megmaradó elemekből újból felépíti a halmot. A LAST változó a H eredetileg utolsó csomópontjának értékét tárolja. A PTR, a LEFT és a RIGHT mutató megadja a LAST, valamint a LAST-hoz tartozó jobb és bal oldali gyermekek helyét (a LAST közben egyre lejjebb kerül a fában).
1. ITEM:=TREE[1]. [A H gyökerének eltávolítása.]
2. LAST:=TREE[N], N:=N-1. [A H utolsó csomópontjának eltávolítása.]
3. PTR:=1, LEFT:=2, RIGHT:=3. [A mutatók inicializálása.]
4. Repeat 5. to 7. lépés while RIGHT<=N:
5. If LAST>=TREE[LEFT] and LAST>=TREE[RIGHT], then:
   TREE[PTR]:=LAST, Return.
   [Az If szerkezet vége.]
6. If TREE[RIGHT]<=TREE[LEFT], then:
   TREE[PTR]:=TREE[LEFT], PTR:=LEFT.
   Else:
   TREE[PTR]:=TREE[RIGHT], PTR:=RIGHT.
   [Az If szerkezet vége.]
7. LEFT:=2*PTR, RIGHT:=LEFT+1.
   [A 4. lépésben elkezdődött ciklus vége.]
8. If LEFT=N and LAST
9. TREE[PTR]:=LAST.
10. Return.




11. Algoritmus: HEAPSORT(A, N). Legyen adott az N elemet tartalmazó A tömb. Az algoritmus rendezi az A tömb elemeit.
1. [A H halom felépítése a IX. eljárás segítségével.]
   Repeat for J=1 to N-1:
   Call INSHEAP(A, J, A[J+1]).
   [A ciklus vége.]
2. [Az A rendezése a H gyökerének ismételt törlésével, amire a X. algoritmust használjuk.]
   Repeat while N>1:
1. Call DELHEAP(A, N, ITEM).
2. A[N+1]:=ITEM.
3. Exit.


Egy szintet vissza, vagy vissza a főmenübe.