Legfennebb hány levél-csúcsa lehet egy 15 csomópontot tartalmazó gyökeres fának?

Bináris-fának ugye azt hívjuk, ahol minden elágazásnál egy végpont kettő, azaz kettő új végpontra válik szét. A bináris ugye kettes számrendszerűt jelent. (bi=kettős lásd: bicikli, binokulár, bipoláris, bicepsz…)

Mint írtam az első hozzászólásomban: A kérdésre adott válasz attól függ, hogy van-e valami megkötés, hogy egy csomópontban maximum hány felé ágazhat el a fa.

Ha nincs ilyen megkötés, akkor egyetlen csomópont akár végtelenfelé is ágazhat, tehát a kérdésnek nincs értelme, illetve a válasz: végtelen.

Mint írtam: Mivel programozás rovatban tetted fel a kérdést, így feltételezem, hogy minden csomópont pontosan kétfelé ágazik. (Azaz logikusan következtetve: bináris fáról van szó.)

* * *

Amennyiben nem bináris számról van szó, de korlátozott a csomópontokból induló ágak száma – jelöljük ezt m betűvel –, akkor is az elv ugyanaz:

- A csomópont nélküli fának 1 levele van.

- Minden csomópont megszüntet egy végpontot (levél csúcsot), de ezzel keletkezik helyette m darab új végpont.

- Az előbbiből következően minden csomópont (m-1) új végpontot ad hozzá a rendszerhez.

n darab csomópont tehát 1+n*(m-1) maximális végpontot eredményez.

Itt is segít a rajzolás. Pl. ha megpróbálod felrajzolni 4-es elágazásokkal, figyeled a végpontok számát, és megérted, mi történik egy új elágazás rajzolásánál.