Határidő: 2022-05-10 24:00

• Ebben a feladatban egy bináris keresőfa adatszerkezetet fogunk készíteni. A binfa.py programban megadtuk a keresőfa implementációjának egy részét.
  1. A bináris fát a BinarisFa osztály reprezentálja. A fa gyökere a gyoker tagváltozóban van tárolva. Ha a fa üres, ennek értéke None, egyébként a gyökér a FaCsucs osztály egy példánya.
  2. A csúcsok a FaCsucs osztály példányai. A bal és jobb tagváltozók értéke vagy None, ha az adott gyerek nem létezik, vagy a gyerekcsúcsot reprezentáló FaCsucs példány.
  3. A fához tartozó műveletek a BinarisFa osztály beszur, keres, szintszam és preorder_nyomtat metódusai. Ezek ellenőrzik, hogy van-e a fának gyökere, majd továbbhívnak a FaCsucs osztály megfelelő, rekurzióval megvalósított metódusaira.
  4. A beszur és keres műveletek közös rekurzív része a FaCsucs csucsot_keres metódusa. Ez bejárja a fát a paraméterül kapott értéket keresve, és visszaadja azt a csúcsot, ahol a bejárás elakad. Ez vagy az a csúcs, amelyik tartalmazza a keresett értéket, vagy ha az érték nincs a fában, akkor az a csúcs, melynek az új értéket tartalmazó csúcs a közvetlen gyereke kell legyen.
  5. A főprogram egész számokat olvas be parancssori argumentumként megadott nevű egysoros fájlból, majd beszúrja őket a bináris fába. Ezután preorder sorrendben a standard kimenetre írja a fában tárolt értékeket, és kiszámítja és kiírja a fa szintjeinek a számát.
• Egészítsük ki a binfa.py programot az implementáció hiányzó részeivel!
  1. A BinarisFa beszur metódusában szúrjuk be a kapott értéket a fába. Ehhez segítségül hívhatjuk a FaCucs csucsot_keres metódusát, amely azt a csúcsot adja vissza, amely vagy tartalmazza a keresett értéket, vagy a keresett értéket a csúcs közvetlen gyerekeként kell beszúrni. Ennek a metódusnak a használatát mutatja be a BinarisFa keres metódusa is. Ügyeljünk arra, hogy a beszúrás üres bináris fán is működjön, illetve olyanon is, amely már tartalmazza a beszúrni kívánt értéket, ekkor már nem kell beszúrni, vagyis a beszúrás idempotens.
  2. A FaCsucs preorder_nyomtat metódusában írjuk ki a fa csúcsait rekurzió segítségével preorder sorrendben a standard kimenetre.
  3. A FaCsucs szintszam metódusában szintén rekurzió segítségével határozzuk meg a fa szintjeinek a számát.
• Az elkészült programot próbáljuk ki a binfa1.text fájlban és a binfa2.text fájlban található bemenettel és teszteljük saját egysoros fájlokkal is!