Cvičení 4 - BST I; dynamické alokace v seznamu

Témata

• implementace seznamu s dynamickou alokací uzlů
• binární vyhledávací stromy (BST)

Úkoly

• Úkol 1 už někteří možná mají z minula, pro ostatní by to měla být snadná úprava.

1. Z minula máte implementovány struktury a základní procedury pro práci se seznamem. Modifikujte je tak, abyste uzly vytvářeli a rušili dle potřeby dynamicky. Tj. všechny procedury budou místo uzlů k přidání/odebrání dostávat jen hodnoty k přidání/odebrání a potřebné uzly budou vytvářeny/rušeny dynamicky. Seznam bude obsahovat hodnoty typu int. Napište takto následující procedury:
   • zjištění délky seznamu: int length(list seznam)
   • výpis prvků (tj složka s daty struktury node) seznamu oddělených čárkou: void print_list(list seznam)
   • přidávání hodnoty na začátek seznamu: void add_start(list *seznam, int data)
   • přidávání hodnoty na konec seznamu: void add_end(list *seznam, int data)
   • přidávání hodnoty na zadané místo v seznamu (nebo na konec, pokud se daná pozice v seznamu nevyskytuje): void add_position(list *seznam, int data, int position)
   • odebírání hodnoty ze začátku seznamu: int remove_start(list *seznam) - vrátí 0, pokud se něco smazalo, a -1 jinak
   • odebírání hodnoty z konce seznamu: int remove_end(list *seznam) - vrátí 0, pokud se něco smazalo, a -1 jinak
   • vyhledávání hodnoty v seznamu - int search(list seznam, int data) - vrátí (první) pozici hledané hodnoty v seznamu, nebo -1 pokud tam není
   • odebírání zadané hodnoty (prvního výskytu) ze seznamu - int remove(list *seznam, int data) - vrátí 0, pokud hodnota byla odebrána, a -1 jinak
2. Implementujte vhodné struktury pro binární vyhledávací strom (uzel stromu node; strom tree - obsahující ukazatel na kořen). Strom bude obsahovat hodnoty typu int.
3. Implementujte následující procedury pro práci s BST:
   • přidání prvku do stromu void add(tree *t, int data)
   • vypsání prvků ve stromě ve vzestupném pořadí void print_in_order(tree t)
   • výpočet hloubky stromu int depth(tree t)