Cvičení 4 - lineární datové struktury III; BST I

Témata

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

Úkoly

1. Z minula máte implementovány strukutry 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áseldují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áváací strom (uzel stromu node; strom tree - obsahující ukazatel na kořen). Strom bude obsahovat hodnoty typu int.
3. Implementujte náseldují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)