Cvičenie č.6

Ciele
  1. Porozumieť dodanej implementácii ADT binárny strom a implementácii operácí pre prechod stromom.
  2. Podľa pokynov doplniť dodanú implementáciu.
  3. Porozumieť dodanej implementácii ADT ternárny strom.
  4. Doplnenie implementácie rekurzívneho prechodu ternárnym stromom.
Úvod
    Náplňou cvičenia je implementácia ADT binárny strom a ADT ternárny strom, ako aj implementácia operácií prechodu týmito stromami rôznymi stratégiami s využitím rekurzie i bez jej využitia.
Postup
  1. Implementácia ADT binárny strom a operácií jeho prechodu.
    Poznámka: Binárny strom je reprezentovaný 3 celočíselnými poliami - prvé uchováva hodnoty uložené vo vrcholoch, druhé uchováva index koreňa ľavého podstromu (0 - ak podstrom neexistuje), tretie uchováva index koreňa pravého podstromu (0 - ak podstrom neexistuje).

    Príklad: Strom zobrazený na obrázku je reprezentovaný pomocou polí value[], left[] a right[] nasledovne:

    Postupnosti prvkov získané využitím jednotlivých stratégií prechodov binárnym stromom:
        INORDER: 4 7 2 8 5 1 6 9 3 
        PREORDER: 1 2 4 7 5 8 3 6 9 
        POSTORDER: 7 4 8 5 2 9 6 3 1 
        LEVEL-ORDER: 1 2 3 4 5 6 7 8 9
            
    Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte. Výsledný program spustite.

    Pripravený archív obsahuje tieto súbory:

    • bintree.h - definičný modul pre prechod binárneho stromu.
    • bintree.c - implementačný modul pre prechod binárneho stromu.
    • test.c - modul pre testovanie. Obsahuje aj funkciu main.
    • fatal.h - definičný modul pre ošetrenie chýb.
    • stacka.h - definičný modul ADT Stack.
    • stacka.c - implementačný modul ADT Stack. (Z cvičenia č.4)
    Poznámka: Dôkladne preštudujte dodaný kód. V prípade nejasností sa s konkrétnou otázkou obráťte na cvičiaceho.
  2. Doplnenie implementácie.
    Úloha: Pridajte podporu nerekurzívneho prechodu stratégiou PREORDER.
    Prototypy operácií (súbor bintree.h):
        void preorderNR(int v);
            
    Úloha: Pridajte podporu prechodu stratégiou LEVEL-ORDER. Zvážte využite ADT Queue (cvičenie č.4).
    Prototypy operácií (súbor bintree.h):
        void levelorder(int v);
            
  3. Implementácia ADT ternárny strom. Prechod ternárnym stromom.
    Poznámka: Ternárny strom je reprezentovaný 4 celočíselnými poliami - jedno uchováva hodnoty uložené vo vrcholoch, druhé uchováva index koreňa ľavého podstromu (0 - ak neexistuje podstrom), tretie uchováva index koreňa prostredného podstromu (0 - ak neexistuje podstrom), štvrté uchováva index koreňa pravého podstromu (0 - ak neexistuje podstrom).

    Príklad: Pre strom zobrazený na obrázku platí:

        PREORDER: 1 2 4 9 5 10 6 3 7 11 12 13 8 14 
        POSTORDER: 9 4 10 5 6 2 11 12 13 7 14 8 3 1
            
  4. Doplnenie implementácie rekurzívneho prechodu ternárnym stromom.
    Úloha: Pridajte implementáciu operácie SetTT pre inicializáciu ternárneho stromu a podporu rekurzívneho prechodu ternárnym stromom operáciami preorderTT a postorderTT.
    Prototypy operácií (súbor bintree.h):
        void preorderTT(int root);
        void postorderTT(int root);
        void SetTT(int* V,int* L,int* M,int* R);
            
Zdroje
  1. Binary Tree Traversal - vizualizácia prechodov binárnym stromom.
Doplňujúce úlohy
    Úloha: Navrhnite a implementujte operáciu levelorderNQ prechodu LEVEL-ORDER binárnym stromom bez využitia ADT Queue, ak výška stromu je jej parametrom.
comments powered by Disqus