Destruktivní sjednocení a průnik BVS (okomentované řešení)

[Pája]

Ahoj!
Sice som nechodil k vam na cvicenia z programovania, ale chcel by som
vas poprosit o pomoc. Tak ako aj viaceri 'kolegovia' nemam este skusku
z programovania. Pri uceni som pouzil aj vasu zbierku uloh z
programovania. Chcel by som vas poprosit, ci by ste nemohli este
napisat 2 tie male priklady a to: destruktivny prienik a destruktivne
zjednotenie BVS. Tieto priklady mi pridu ako velmi tazke, pokusam sa
ich naprogramovat, ale vobec mi to nejde...
Ak by ste si teda nasli cas, bol by som vam velmi vdacny'

pomocná procedura

Kód: Vybrat vše

procedure vlozUzel(var koren: UKUzel; uzel: UkUzel);
begin
    if (koren = nil) then begin
        koren := uzel;
        koren^.left := nil;
        koren^.right := nil;
    end else if (uzel^.info < koren^.info) then begin
        vlozUzel(koren^.left, uzel);
    end else if (uzel^.info > koren^.info) then begin
        vlozUzel(koren^.right, uzel);
    end else begin
        dispose(uzel);
    end;
end;

Sjednocení

Kód: Vybrat vše

(*
 * Do stromu, jehoz korenem je "korenA" prida vsechny prvky ze stromu,
 * jehoz korenem je "korenB". Po provedeni procedury bude tedy strom
 * s korenem "korenA" obsahovat sjednoceni puvodnich mnozin prvku stromu A a B.
 * Po provedeni procedury bude strom B prazdny ("korenB" bude nil).
 *)
procedure destruktivniSjednoceni(var korenA, korenB: UkUzel);
var
    levyPodstrom, pravyPodstrom: UkUzel;
begin
    if korenB = nil then
        exit;
    levyPodstrom := korenB^.left;
    pravyPodstrom := korenB^.right;
    vlozUzel(korenA, korenB);
    destruktivniSjednoceni(korenA, levyPodstrom);
    destruktivniSjednoceni(korenA, pravyPodstrom);
    korenB := nil;
end;

Průnik

Kód: Vybrat vše

(*
 * Ze stromu, jehoz korenem je "korenB", odstrani vsechny prvky, ktere se
 * nenachazeni ve strome, jehoz korenem je "korenA". Strom s korenem "korenA"
 * zustane po provedeni procedury nedotcen.
 *)
procedure destruktivniPrunik(var korenA, korenB: UkUzel);
begin
    if korenB <> nil then begin
        destruktivniPrunik(korenA, korenB^.left);
        destruktivniPrunik(korenA, korenB^.right);
        if not (jeTam(korenA, korenB^.info)) then
            odstranKoren(korenB);
    end;
end;

Sjednocení je triviální, průnik v podstatě taky, byť uvedené řešení není nejgeniálnější. Po provedení průniku možná budete chtít na strom s kořenem korenA zavolat toto:

Kód: Vybrat vše

(*
 * Odstrani ze stromu, jehoz koren je "koren", vsechny prvky a odalokuje
 * pamet, kterou zabiraly.
 * Po skonceni procedury bude mit "koren" hodnotu nil.
 *)
procedure smazCelyStrom(var koren: UkUzel);
begin
    if koren = nil then
        exit;
    smazCelyStrom(koren^.left);
    smazCelyStrom(koren^.right);
    dispose(koren);
    koren := nil;
end;

Jak vidíte, s pomocí rekurze se dá mnohé vykouzlit. Pokud vám rekurze činí potíže, zkuste si pohrát s touto kravinkou: http://vyuka.pavel-rimsky.cz/programs/zgr.zip.