VIK Wiki

„Dinamikus adatszerkezetek tutorial” változatai közötti eltérés

← Régebbi szerkesztésÚjabb szerkesztés →
VizuálisWikiszöveges
Ferrero (vitalap | szerkesztései)
1 561 szerkesztés
Ferrero (vitalap | szerkesztései)
1 561 szerkesztés
351. sor: 351. sor:
A következő fv megszámolja, hány elemnek van jobb oldali gyermeke!
A következő fv megszámolja, hány elemnek van jobb oldali gyermeke!


%CODE{"cpp"}%
<pre>
  int gyerekek (pBIFA fa) {
int gyerekek (pBIFA fa) {
  int n=0;
int n=0;


  if (fa==NULL) return -1; // üres a fa!
if (fa==NULL) return -1; // üres a fa!


  if (fa->jobb !=NULL ) { // el lehet menni jobbra
if (fa->jobb !=NULL ) { // el lehet menni jobbra
n = n + 1;  // a fának van jobb oldali gyereke, így növeljük a számlálót
n = n + gyerekek(fa->jobb); // megszamoljuk a jobb oldali reszt (n=n+ rövidebb verziója az n+=)
}


  n = n + 1;  // a fának van jobb oldali gyereke, így növeljük a
if (fa->bal !=NULL ) // el lehet menni balra
  // számlálót
n = n + gyerekek(fa->bal); // megszamoljuk a bal oldali reszt
 
return n; // visszaterunk az eredmennyel
  n = n + gyerekek(fa->jobb);  // megszamoljuk a jobb oldali reszt (n=n+ rövidebb verziója az n+=)
}
 
}
  }
</pre>
  if (fa->bal !=NULL ) // el lehet menni balra
  n = n + gyerekek(fa->bal); // megszamoljuk a bal oldali reszt
 
  return n; // visszaterunk az eredmennyel
  }
%ENDCODE%


Mit csináltunk itt? Fontos először is tudnunk, hogy a függvény egyszerre csak az aktuális elemmel törődik, s nem látja annak gyerekeinek gyerekeit. Annyit tud, hogy jobbra és balra el lehet-e menni. Ennyi elég, mert ha egyik irányba el lehet menni, akkor meghívja önmagát azzal az elemmel, ami a kívánt irányban van. Amikor visszatér, az előző függvényhíváshoz tér vissza, s ezzel átadja a lentebb fekvő gyerekek értékeit. Bonyolult.
Mit csináltunk itt? Fontos először is tudnunk, hogy a függvény egyszerre csak az aktuális elemmel törődik, s nem látja annak gyerekeinek gyerekeit. Annyit tud, hogy jobbra és balra el lehet-e menni. Ennyi elég, mert ha egyik irányba el lehet menni, akkor meghívja önmagát azzal az elemmel, ami a kívánt irányban van. Amikor visszatér, az előző függvényhíváshoz tér vissza, s ezzel átadja a lentebb fekvő gyerekek értékeit. Bonyolult.
377. sor: 374. sor:


<pre>
<pre>
(a)
(a)
/ \
/ \
(b) (c)
    (b)   (c)
/ \
    /     \
(d) (e)
  (d)       (e)
\
    \
  (f)
    (f)
</pre>
</pre>


390. sor: 387. sor:
hozzáadódik (a) számlálójához, ami így már 3.
hozzáadódik (a) számlálójához, ami így már 3.


Ha fenti bírod követni, akkor nem érted a rekurziót, ülj neki, és ha megvan, akkor gyere vissza. (_Ahhoz hogy megértsd a rekurziót, előbb meg kell értened a rekurziót :D_)
Ha fenti bírod követni, akkor nem érted a rekurziót, ülj neki, és ha megvan, akkor gyere vissza. (''Ahhoz hogy megértsd a rekurziót, előbb meg kell értened a rekurziót :D'')


Remélem érthető tehát a bináris fák bejárása. Ha nem a gyerekek számát, hanem mondjuk a fában tárolt adatok összegét kell meghatározni, akkor értelemszerűen azokat kell az n-hez adni, s azzal kell visszatérni. Pl.:
Remélem érthető tehát a bináris fák bejárása. Ha nem a gyerekek számát, hanem mondjuk a fában tárolt adatok összegét kell meghatározni, akkor értelemszerűen azokat kell az n-hez adni, s azzal kell visszatérni. Pl.:


%CODE{"cpp"}%
<pre>
  int osszeg (pBIFA fa) {
int osszeg (pBIFA fa) {
  int n;
int n;
  if (fa==NULL) return -1;
if (fa==NULL) return -1;


  n=fa->adat;
n=fa->adat;


  if (fa->jobb !=NULL ) n = n + osszeg(fa->jobb);
if (fa->jobb !=NULL ) n = n + osszeg(fa->jobb);
  if (fa->bal !=NULL )  n = n + osszeg(fa->bal);
if (fa->bal !=NULL )  n = n + osszeg(fa->bal);


  return n; // visszaterunk az eredmennyel
return n; // visszaterunk az eredmennyel
  }
}
%ENDCODE%
</pre>


===Fa rendezett kiíratása===
===Fa rendezett kiíratása===
A lap eredeti címe: „https://vik.wiki/Dinamikus_adatszerkezetek_tutorial”