C/C++ & Visual C++

DatovΘ struktury a algoritmy (13.)

┌vodem  |  DatovΘ struktury |  Kurz DirectX  |  Downloads  |  Otßzky a odpov∞di

Ji₧ v ·vodnφm dφlu o stromech jsme se zmφnili o pr∙chodu uzly stromu a to jak binßrnφho, tak i obecnΘho. V dneÜnφm pokraΦovßnφ se budeme touto problematikou zab²vat podrobn∞ji a to jak s pomocφ rekurzivnφho charakteru datovΘ struktury stromu, tak i s vyu₧itφm d°φve implementovan²ch struktur - zßsobnφku a fronty.

13.1. Pr∙chod stromem do hloubky - rekurzivn∞

Pr∙chodem stromu rozumφme postupnΘ projitφ vÜech uzl∙ stromu a provedenφ urΦitΘ operace nad datov²mi prvky jednotliv²ch uzl∙ - m∙₧e to b²t bu∩ jednoduÜe vypsßnφ, ale m∙₧e to b²t i zm∞na vÜech uzl∙ pomocφ n∞jakΘ funkce. My si ukß₧eme vÜechny metody v prvnφ verzi (tedy v²pis prvk∙ stromu) a pak si °ekneme, jak se dß napsat funkce pr∙chodu stromem pro obecn∞ definovanou funkci. Zab²vat se budeme pro jednoduchost binßrnφm vyhledßvacφm stromem, ale metody by se velice podobn∞ implementovaly i pro obecnΘ stromy. Podle toho, v jakΘ fßzi funkce pr∙chodu stromem budeme zpracovßvat datov² Φlen uzl∙ se rozliÜujφ t°i verze pr∙chodu, kterΘ si nynφ implementujeme:

    template<class T> void CBinStrom<T>::PruchodPre(CUzel<T>* _lpUzel)
    {
        if(_lpUzel)
        {
            cout << _lpUzel->VratData() << " ";
            PruchodPre(_lpUzel->VratLevy());
            PruchodPre(_lpUzel->VratPravy());
        }
    }

JeÜt∞ obslu₧nß funkce pro pr∙chod cel²m stromem:

    template<class T> void CBinStrom<T>::PruchodStromem1()
    {
        PruchodPre(m_lpKoren);
    }

Metoda je zalo₧ena na rekurzi, vstoupφme do prvnφho uzlu zpracujeme prvnφ Φlen. PotΘ rekurzivn∞ vstoupφme do levΘho podstromu, op∞t zpracujeme uzel. To pokraΦuje tak dlouho, dokud existujφ dalÜφ levΘ podstromy. Dostaneme se tedy do nejlev∞jÜφho listu, z n∞j se pak funkce vracφ o patro v²Ü a zpracuje prav² podstrom. M∙₧e se tedy stßt, ₧e ka₧d² uzel stromu navÜtφvφme t°ikrßt - p°i sestupu (vykonßnφ operace), p°i nßvratu z levΘho podstromu a koneΦn∞ p°i nßvratu z pravΘho podstromu. Tento zp∙sob pr∙chodu stromu se naz²vß preorder - akci vykonßvßme toti₧ p°i prvnφm vstupu do uzlu. Ukß₧eme si v²stup pro konkrΘtnφ strom. Strom bude vytvo°en nßsledujφcφm k≤dem:

    CBinStrom<int> *lpStrom = new CBinStrom<int>;

    lpStrom->Vloz(8);
    lpStrom->Vloz(5);
    lpStrom->Vloz(9);
    lpStrom->Vloz(13);
    lpStrom->Vloz(4);
    lpStrom->Vloz(7);
    lpStrom->Vloz(11);

 Tak₧e v grafickΘ interpretaci bude strom vypadat nßsledovn∞:

Po zavolßnφ metody pro preorder pr∙chod dostaneme posloupnost: 8 5 4 7 9 13 11.

To, ₧e jsme provedli operaci nad datov²m prvkem p°i vstupu do uzlu nenφ jedinß mo₧nost. Ukß₧eme si tedy zb²vajφcφ dv∞ metody a takΘ posloupnosti, kterΘ nßm dajφ:

    template<class T> void CBinStrom<T>::PruchodIn(CUzel<T>* _lpUzel)
    {
        if(_lpUzel)
        {
            PruchodIn(_lpUzel->VratLevy());
            cout << _lpUzel->VratData() << " ";
            PruchodIn(_lpUzel->VratPravy());
        }
    }

    template<class T> void CBinStrom<T>::PruchodStromem2()
    {
        PruchodIn(m_lpKoren);
    }

Tato metoda tedy provßdφ akci p°i druhΘm vstupu do uzlu a naz²vß se inorder. V²slednß posloupnost mß pak tvar: 4 5 7 8 9 11 13.

T°etφ metoda provßdφ operaci nad uzlem a₧ v poslednφm vstupu a proto nese nßzev postorder. Jejφ k≤d naleznete v p°ilo₧en²ch zdrojov²ch souborech. V²slednß posloupnost mß tvar: 4 7 5 11 13 9 8.

VÜechny tyto t°i metody se dajφ nap°. pou₧φt k reprezentaci matematick²ch v²raz∙ v pam∞ti poΦφtaΦe, o Φem₧ si povφme v n∞kterΘm z dalÜφch dφlu.

Nynφ se podφvßme na to, jak napsat metodu pr∙chodu stromem tak, aby se s ka₧d²m datov²m prvkem provedla n∞jakß nßmi definovanß operace - nap°. se pokusφme hodnoty vÜech datov²ch prvk∙ vynßsobit dv∞ma:

    template<class T> void CBinStrom<T>::PruchodPre(CUzel<T>* _lpUzel,
       void (*operace)(CUzel<T> *_lpParam))
    {
        if(_lpUzel)
        {
            operace(_lpUzel);
            PruchodPre(_lpUzel->VratLevy(), operace);
            PruchodPre(_lpUzel->VratPravy(), operace);
        }
    }

    template<class T> void CBinStrom<T>::PruchodStromem1(void (*operace)(CUzel<T> *_lpParam))
    {
        PruchodPre(m_lpKoren, operace);
    }

Nynφ u₧ si jen v hlavnφm programu definujeme funkci pro vynßsobenφ datovΘho Φlenu dv∞mi nßsledujφcφm zp∙sobem:

    void VynasobDvema(CUzel<int> *_lpUzel)
    {
        _lpUzel->NastavData(_lpUzel->VratData() * 2);
    }

PotΘ u₧ ji jen pou₧ijeme ve funkci main() takto:

    lpStrom->PruchodStromem1(VynasobDvema);

Zb²vajφcφ dv∞ metody se op∞t liÜφ jen po°adφm provedenφ operace a jsou obsa₧eny v implementaci projektu.

K≤d naleznete v sekci Downloads (projekt Strom).

13.2. Pr∙chod stromem do hloubky - nerekurzivn∞

Nynφ se podφvßme na to, jak napsat tyto funkce bez pou₧itφ rekurzivnφho volßnφ. Pokud bychom uzly stromu implementovali tak, ₧e by obsahovaly i odkaz na svΘ rodiΦe, pak by bylo mo₧nΘ napsat funkci pro pr∙chod pomocφ n∞kolika cykl∙. To ovÜem nenφ nßÜ p°φpad a proto se podφvßme na jinou mo₧nost - vyu₧ijeme nßmi d°φve stvo°enΘ t°φdy pro zßsobnφk a p°φÜt∞ i pro frontu. My jsme si tyto dv∞ t°φdy implementovali jako statickΘ a o dynamick²ch jsme si jen pov∞d∞li, jak je naprogramovat. V tomto p°φpad∞ se nßm budou hodit dynamickΘ implementace, nebo¥ p°edem nevφme kolik prvk∙ (vnit°nφch uzl∙) strom mß. Tak₧e nynφ malß odboΦka a ukß₧eme si jednoduchou implementaci jednΘ z t∞chto t°φd (CDynZasob):

#ifndef CDYNZASOB_H
    #define CDYNZASOB_H

    template<class T> class CPrvek {
    private:
        T m_Data;
        CPrvek<T> *m_lpDalsi;
    public:
        CPrvek() : m_lpDalsi(NULL) { }
        CPrvek(const T& _Data) : m_Data(_Data), m_lpDalsi(NULL) { }

        T VratData() const { return m_Data; }
        CPrvek<T>* VratDalsi() const { return m_lpDalsi; }
        void NastavDalsi(CPrvek<T> *_lpDalsi) { m_lpDalsi = _lpDalsi; }
        void NastavData(const T& _Data) { m_Data = _Data; }
    };

    template<class T> class CDynZasob {
    private:
        CPrvek<T> *m_lpVrchol;
    public:
        CDynZasob() : m_lpVrchol(NULL) { }
        ~CDynZasob() { if(!JePrazdny()) { SmazZasob(); } }

        void VytvorPrazdny();

        bool SmazZasob();

        bool JePrazdny() { return (m_lpVrchol == NULL); }

        bool Vloz(const T& _Data); // vklada na zacatek
        bool Vyjmi(T &_Vyber); // odebere prvni prvek
    };

    template<class T> void CDynZasob<T>::VytvorPrazdny()
    {
        if(m_lpVrchol)
        {
            SmazZasob();
        }

        m_lpVrchol = NULL;
    }

    template<class T> bool CDynZasob<T>::SmazZasob()
    {
        bool bNavrat = false;

        if(!JePrazdny())
        {
            CPrvek<T> *lpMazany;

            while(m_lpVrchol)
            {
                lpMazany = m_lpVrchol;
                m_lpVrchol = m_lpVrchol->VratDalsi(); // posun na dalsi prvek
                delete lpMazany;
            }

            bNavrat = true;
        }

        return bNavrat;
    }

    template<class T> bool CDynZasob<T>::Vloz(const T& _Data)
    {
        bool bNavrat = false;

        // jen vlozime prvek do zasobniku
        CPrvek<T> *lpNovy = new CPrvek<T>(_Data);

        if(lpNovy)
        {
            lpNovy->NastavDalsi(m_lpVrchol); // novy prvek bude ukazovat na puvodni zacatek

            m_lpVrchol = lpNovy; // a presuneme novy zacatek

            bNavrat = true;
        }

        // opet novy prvek nemazeme

        return bNavrat;
    }

    template<class T> bool CDynZasob<T>::Vyjmi(T &_Vyber)
    {
        bool bNavrat = false;

        if(!JePrazdny())
        {
            _Vyber = m_lpVrchol->VratData();

            CPrvek<T> *lpMazany = m_lpVrchol;
            m_lpVrchol = m_lpVrchol->VratDalsi();

            delete lpMazany;

            bNavrat = true;
        }

        return bNavrat;
    }

#endif

K≤d nenφ t°eba probφrat, je to jen pou₧itφ lineßrnφho spojovΘho seznamu. My tento zßsobnφk pou₧ijeme pro uchovßnφ uzl∙ naÜeho binßrnφho stromu v metod∞ PruchodStromem4():

    template<class T> void CBinStrom<T>::PruchodStromem4()
    {
        // musime si pomoci, abychom mohli pouzit sablonu jako parametr sablony
        typedef CUzel<T> LPTCUZEL;

        CDynZasob<LPTCUZEL> Zasob;

        Zasob.Vloz(*m_lpKoren);

        CUzel<T> Zpracovani;

        cout << endl << "Nerekurzivne! :" << endl;

        while(!Zasob.JePrazdny())
        {
            if(Zasob.Vyjmi(Zpracovani))
            {
                cout << " " << Zpracovani.VratData();
                if(Zpracovani.VratPravy()) { Zasob.Vloz(*Zpracovani.VratPravy()); }
                if(Zpracovani.VratLevy()) { Zasob.Vloz(*Zpracovani.VratLevy()); }
            }
        }
    }

JednoduÜe vyjdeme z ko°ene, kter² ulo₧φme do zßsobnφku jako prvnφ, vstoupφme do cyklu, kter² skonΦφ a₧ v okam₧iku, kdy bude zßsobnφk prßzdn². V cyklu nejprve vyjmeme vrchol ze zßsobnφku (p°i prvnφm pr∙chodu cyklem to je ko°en), zpracujeme data obsa₧enß v tomto uzlu a ulo₧φme na zßsobnφk nßslednφky tohoto uzlu. Uklßdßme je v po°adφ prav² a pak lev², tφm docφlφme toho, ₧e strom bude prochßzen zleva doprava. Do levΘho se toti₧ dφky charakteru zßsobnφku dostaneme d°φve. Pokud nßm vÜak nezßle₧φ na po°adφ navÜtφvenφ jednotliv²ch vrchol∙, m∙₧eme °ßdky klidn∞ prohodit.

JeÜt∞ dodßm ke k≤du, ₧e definici jinΘho jmΘna pro Üablonu CUzel<T> by bylo lepÜφ umφstit vn∞ t°φdy. Zde je to jen proto, aby byla vid∞t definice. Samoz°ejm∞ by bylo mo₧nΘ metodu upravit tak, aby umo₧≥ovala provedenφ n∞jakΘ operace nad daty obsa₧en²mi v uzlu jako jsme to ud∞lali u rekurzivnφch metod.

K≤d naleznete v sekci Downloads (projekt Strom2).

13.4. Co bude p°φÜt∞

P°φÜt∞ si povφme jeÜt∞ o pr∙chodu stromem do Üφ°ky a takΘ budeme °eÜit velice znßmou ·lohu o koni na Üachovnici, kterß nßm ukß₧e vyu₧itφ metody pr∙chodu stromem. Nadefinujeme si n∞kterΘ vlastnosti strom∙ a podφvßme se na datovou strukturu p°φbuznou strom∙m, kterß se naz²vß halda.