7. Bináris keresőfa

Ebben a feladatban egy bináris keresőfa adatszerkezetet fogunk készíteni. A bintree.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 bintree.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 bintree1.text fájlban és a bintree2.text fájlban található bemenettel és teszteljük saját egysoros fájlokkal is!