Izpitno vprašanje RAČ2PRA 9200

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka SonjaValenčič.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Sestavi algoritem, ki iz premega in vmesnega obhoda dvojiškega drevesa rekonstruira drevo.

Odgovor

Drevo lahko enolično rekonstruiramo, če so vsi njegovi elementi različni.

DvDrevo rekonstrukcija(premi pregled, vmesni pregled){
  //premi in vmesni pregled istega drevesa imata enako št. 
  //elementov, zato sta oba hkrati prazna
  če je premi pregled prazen{
    vrni novo prazno DvDrevo
  }
  sicer{
    zapomni si prvi element(koren) v premem pregledu in ga poišči v vmesnem pregledu
    vmesni_levi = elementi iz vmesnega pregleda, ki so levo od korena, v prvotnem vrstnem redu
    vmesni_desni = elementi iz vmesnega pregleda, ki so desno od korena, v prvotnem vrstnem redu
    dolzinaVL = št. elementov v vmesni_levi
    dolzinaVD = št. elementov v vmesni_desni
    premi_levi = elementi od vključno drugega do vključno (1+dolzinaVL)-tega iz premega pregleda
    premi_desni = elementi od vključno (2+dolzinaVL)-tega do (1+dolzinaVL+dolzinaVD)-tega iz
                  premega pregleda
    DvDrevo levo = rekonstrukcija(premi_levi,vmesni_levi)
    DvDrevo desno = rekonstrukcija(premi_desni,vmesni_desni)
    vrni sestavi(levo,koren,desno) //iz dvojiških dreves levo in desno in podatka koren sestavimo
                                   // novo dvojiško drevo 
  }
}
Osebna orodja