Naloga: Fibonaccijevo drevo

Iz MaFiRaWiki

Napiši funkcijo fibonaccijevoDrevo[n_], ki bo vrnila n-to fibonaccijevo drevo Fn.

Fibonaccijevo drevo je dvojiško drevo definirano na naslednji način:

  • F0 in F1 sta prazni drevesi.
  • Drevo Fn za n > 1 ima v korenu število fn, levi sin je Fn − 1, desni sin pa Fn − 2, v katerem vse podatke povečamo za fn (podatke povečamo samo v desnem poddrevesu), kjer je fn običajno Fibonaccijevo zaporedje definirano na naslednji način:
    • f1 = f2 = 1,
    • fn = fn − 1 + fn − 2 za n > 2.


Zgled:

Fibonaccijevo drevo F[6]:

Rešitev

Glej tudi

Osebna orodja