Cvičení 5 - BST II

Informatici (cvičení v C)

Téma: binární vyhledávací stromy II

• minimum a maximum v zadaném podstromu
• mazání hodnot ze stromu
• průchod do šířky

Úkoly

Z minula máte strukutry a procedury pro základní prácí s BST (přidávání, výpis v pořadí, hloubka stromu). Tj.

1. 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.
2. 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)

Dnes přidejte následující procedury:

3. Hledání minima a maxima v (kořenovým uzlem) zadaném podstromu: int tree_max(node *root) a int tree_min(node *root). Můžete předpokládát, že procedury nikdy nebudou volány s root == NULL, tj. minimum i maximum budou vždy existovat.
4. Odebírání prvku ze stromu: int tree_remove(tree *t, int data) vracející 1 pokud něco bylo smazáno a 0 jinak.
5. Výpis prvků stromu v pořadí průchodu stromem do šířky: void print_bft(tree *t).
6. V předchozím úkolu potřebujete frontu, naprogramujte obousměrný seznam a použijte jej k implementaci fronty s operacemi enqueue i dequeue pracujícími v O(1).

Učitelé (cvičení v Pythonu)

Téma: binární vyhledávací stromy

• binární vyhledávací stromy (BST)
• minimum a maximum v zadaném podstromu
• mazání hodnot ze stromu
• průchod do šířky

Úkoly

1. Implementujte vhodné struktury pro binární vyhledávací strom (uzel stromu node; strom tree - obsahující kořen stromu). Můžete předpokládat, že strom bude obsahovat pouze celá čísla.
2. Implementujte procedury:

• Vyhledávání v BST.
• Přidávání do BST.
• Výpočet výšky BST.
• Průchody stromem do hloubky i do šířky.
• Hledání minima a maxima v BST.
• Mazání z BST.