Predstavljanje i implementacija stabla

Definicija stabla i terminologija
Stablo se definiše preko sebe samog, u krajnjem slučaju stablo može da se svede samo na koren. Ovakav tip stabla se naziva korenim stablom (rooted tree). Nasuprot korenom je slobodno stablo kao posebna vrsta grafa.
Često se za grane koje spajaju čvorove stabla pretpostavlja implicitno usmerenje od korena ka podstablima. Tada je moguće razlikovati ulazni i izlazni stepen čvora.
Ulazni stepen je broj grana koje ulaze u čvor. Može da ima samo dve vrednosti: 0 za koren i 1 za sve ostale čvorove.
Izlazni stepen je broj grana koje izlaze iz čvora.
Kada se kaže stepen čvora obično se misli na izlazni stepen. Ako je m maksimalni izlazni stepen nekog čvora, za stablo se kaže da ima stepen m ili m-arno stablo.
Za odnose između čvorova u stablu uobičajeno se koristi terminologija iz genealogije i botanike. Tako se čvorovi sa nultim izlaznim stepenom nazivaju listovima i terminalnim čvorovima, a ostali čvorovi sa nenultim izlaznim stepenom su neterminalnim ili čvorovi grananja.
Čvor od kojeg se dalje granaju podstabla, naziva se ocem čvorova koji predstavljaju korene tih podstabala, a oni njegovim sinovima. Svaki sin ima samo jednog oca. Sinovi istog oca nazivaju se braćom. Putem (ni,…,nk) se naziva skup čvorova takav da je čvor ni otac čvora ni+1 za .
Dužina puta je za jedan manja od broja čvorova na putu i predstavlja broj grana na njemu. U stablu postoji samo po jedan put između korena i svakog drugog čvora.
Preci nekog čvora su svi čvorovi koji se nalaze u njegovim podstablima.
Koren je jedini čvor koji nema predaka, a listovi nemaju potomka.
Stablo je višenivoska struktura kod koje se nivoom čvora smatra broj grana na putu od korena do njega. Koren je na nivou 0, a zatim svaki sin na nivou za 1 veći od oca.
Visina ili dubina stabla se određuje kao maksimalna vrednost nivoa listova u stablu i to je najveća udaljenost lista u stablu od korena.
Šuma je skup nepovezanih stabla. Šuma se može dobiti od stabla uklanjanjem korena i grana koje izlaze iz njega. Od šume se može dobiti stablo uvođenjem novog korena i spajanjem sa korenima stabala šume.
Za dva stabla se kaže da su slična ako imaju istu strukturu, što znači isti broj čvorova i grana, kao i istu topologiju.
Za dva stabla se kaže da su ekvivalentna ako su slična, a odgovarajući čvorovi imaju isti sadržaj.
Uređeno stablo je stablo u kojem podstabla svakog čvora čine uređen skup (u suprotnom neuređen).
Poziciona stabla stepena m su ona stabla kod kojih je svakom podstablu nekog čvora pridružena jedinstvena pozicija označena rednim brojem od 1 do m.
Interna dužina puta stabla se definiše kao zbir dužina puteva od korena do svih čvorova u stablu