Cvičení 6 - BST II

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

• 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). Dnes přidejte následující procedury:

1. 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 maximu budou vždy existovat.
2. 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.
3. Výpis prvků stromu v pořadí průchodu stromem do šířky: void print_bft(tree *t).
4. (*) 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).

Úkoly označené (*) nejsou povinné (nemusíte je odevzdávat).