☰

» »

[C#] Iskalno Drevo

[C#] Iskalno Drevo

Ciklamen ::

Živjo, spet se javljam z nalogo za faks :)

Ni mi najbolj jasno kaj točno je treba naredit, upam da mi kdo lahko pomaga razumeti (nočem kode, samo razlago kako naj se zadeve lotim)

Torej zadeva je sledeča, imamo class IskalnoDrevo, v njem pa class Vozlisce

    public class IskalnoDrevo
    {
        class Vozlisce
        {
            private float podatek;
            private Vozlisce levo;
            private Vozlisce desno;

            public Vozlisce(float podatek)
            {
                this.podatek = podatek;
                levo = null;
                desno = null;
            }

            public Vozlisce(Vozlisce original)
            {
                this.podatek = original.podatek;
                levo = null;
                desno = null;

                if (original.levo != null)
                    levo = new Vozlisce(original.levo);
                if (original.desno != null)
                    desno = new Vozlisce(original.desno);
            }

            public void vstavi(float podatek)
            {
                if (podatek < this.podatek)
                {
                    if (levo == null)
                        levo = new Vozlisce(podatek);
                    else
                        levo.vstavi(podatek);
                }
                else {  //when (podatek >= this.podatek)
                    if (desno == null)
                        desno = new Vozlisce(podatek);
                    else
                        desno.vstavi(podatek);
                }
            }

            public int size()
            {
                //TODO: implementation
                return -1;  //HACK: dummy return
            }

            public float najvecji()
            {
                //TODO: implementation
                if (desno == null)
                    return float.NaN;

                Vozlisce v = desno;

                while (v != null)
                    v = desno.desno;
                return v.podatek;   //HACK: dummy return
            }

            public float najmanjsi()
            {
                //TODO: implementation

                if (levo == null)
                    return float.NaN;

                Vozlisce v = levo;

                while (v != null)
                    v = levo.levo;
                return v.podatek; //HACK: dummy return
            }

            public void narascajocaVrsta(Queue<float> vrsta)
            {
                //TODO: implementation
            }

            public void padajocaVrsta(Queue<float> vrsta)
            {
                //TODO: implementation
            }

            public void prefixQueue(Queue<float> vrsta)
            {
                //TODO: implementation

                vrsta.Enqueue(podatek);
                if (levo != null)
                    levo.prefixQueue(vrsta);
                if (desno != null)
                    desno.prefixQueue(vrsta);
            }

            public void infixQueue(Queue<float> vrsta)
            {
                if (levo != null)
                    levo.infixQueue(vrsta);
                vrsta.Enqueue(podatek);
                if (desno != null)
                    desno.infixQueue(vrsta);
            }

            public void postfixQueue(Queue<float> vrsta)
            {
                //TODO: implementation

                if (levo != null)
                    levo.postfixQueue(vrsta);
                if (desno != null)
                    desno.postfixQueue(vrsta);
                vrsta.Enqueue(podatek);
            }
        }   //end class Vozlisce

        //lastnosti
        Vozlisce koren;

        //privzeti konstruktor
        public IskalnoDrevo()
        {
            this.koren = null;
        }

        //kopirni konstruktor
        public IskalnoDrevo(IskalnoDrevo original)
        {
            koren = new Vozlisce(original.koren);
        }

        public void vstavi(float podatek)
        {
            if (empty())
                koren = new Vozlisce(podatek);
            else
                koren.vstavi(podatek);
        }

        public bool empty()
        {
            return (koren == null);
        }

        public int size()
        {
            if (koren == null/*empty()*/)
                return 0;
            else
                return koren.size();
        }

        //metode za dodatno funkcionalnost
        public float najvecjiElement()
        {
            //TODO: implementation

            Vozlisce v = koren;



            return float.NaN;   //HACK: dummy return
        }

        public float najmanjsiElement()
        {
            //TODO: implementation
            return float.NaN;   //HACK: dummy return
        }

        public Queue<float> narascajocaVrsta()
        {
            Queue<float> narascajoca = new Queue<float>();
            if (koren != null)
                koren.narascajocaVrsta(narascajoca);
            return narascajoca;
        }

        public Queue<float> padajocaVrsta()
        {
            Queue<float> padajoca = new Queue<float>();
            if (koren != null)
                koren.padajocaVrsta(padajoca);
            return padajoca;  //HACK: dummy return
        }


        public Queue<float> prefixQueue()
        {
            //TODO: implementation
            return new Queue<float>();  //HACK: dummy return
        }

        public Queue<float> infixQueue()
        {
            //TODO: implementation
            return new Queue<float>();  //HACK: dummy return
        }
        public Queue<float> postfixQueue()
        {
            //TODO: implementation
            return new Queue<float>();  //HACK: dummy return
        }
    }   //end class IskalnoDrevo


Implementirat moram(o) metode, ki imajo //TODO: implementation v njih.

Se pravi, ni mi najbolj jasno zakaj 2x postfixQueue, infix, prefix, najvecji, padajocaVrsta, narascajocaVrsta itd.

Upam, da mi kdo lahko pomaga z razlago (nisem na skripti od profesorja in na googlu našel nič koristnega, zato smetim tukaj) - še enkrat nočem kode, samo želim razlago ker trenutno sem malo v temi :)
- End of the Post ->

amdsup5 ::

Predvidevam, da se gre za binarno iskalno drevo (BST).

Najmanjšega poiščeš preprosto tako, da slediš levim dokler ne naletiš na null potem se vrneš enega višje.

Analogno največjega poiščeš tako, da slediš desnim sinovom dokler ne naletiš na null in se vrneš enega višje.

Zanima me sledeče, a je to tvoja ideja uporabit vrsto ali imate tako v navodilih?

Zgodovina sprememb…

  • spremenilo: amdsup5 ()

Ciklamen ::

Gre za binarno iskalno drevo ja :)

Sem poizkusil, naredil tako za najmanjšega (in tudi največji ne more bit drugače)


            public float najmanjsi()
            {
                //TODO: implementation

                if (levo == null)
                    return float.NaN;

                Vozlisce v = levo;

                while (v.levo != null)
                    v = levo;
                return v.podatek; //HACK: dummy return
            }


Pa mi cikla v while zanki, ker najmanjša vrednost nima naslednjega vozlišča null

Vrsta je že podana, vbistvu vse metode ki so napisane so že podane, mi jih moramo samo dopolnit da bo delovalo :)
- End of the Post ->

amdsup5 ::

Ja je en trik v tem in sicer tako.

Ti potrebuješ en kazalec na root , ki se pomika skupaj s trenutnim

Točno tako kot praviš najmanjši element nima levega.

Zato potrebuješ nek mehanizem, da vrneš to vozlišče

Vozlisce * root = root // nastaviš na null
najdemo recimo prvega levega npr. L1

L1.parent = root
L1.leftchild = L2

potem
L2.parent = root
L2.leftchild = L3

Glej da imaš tako relacijo, da lahko vedno dostopaš do očeta vozlišča preko kazalca root

Na tak način prideš recimo do L5 ki je npr. minimalen
potem pač vrneš ta to narediš tako
Vozlisce * min = (L5.parent).leftchild

Zgodovina sprememb…

  • spremenilo: amdsup5 ()

Ciklamen ::

Sem rešil tega z rekurzijo, bolj elegantno kot pointerji v C# :)

Zanima me še za padajoca pa narascajoca vrsta, kako naj se tega lotim? Ima kdo idejo?
- End of the Post ->

Ciklamen ::

Tudi to rešil, vbistvu čist simpl, zanima me še samo size()? Probal sem že marsikaj, pa ne dela. Gre preko null reference, trenutno imam tak

                if (levo.levo == null && desno.levo == null)
                    return 1;
                else
                    return levo.size() + desno.size();
- End of the Post ->

amdsup5 ::

ustvari števec, nastavi na 0

Vsako vozlišče ima lahko kvečjemu dva sinova.

recimo za levo poddrevo dokler ne prideš do listov, preveri ali trenutno vozlišče ima nastavljenega levega in desnega sina, če ima oba povečaj števec za 2 sicer za 1

isto ponovi za desno poddrevo dokler ne naletiš na list preglejuj leve in desne sinove in popravljaj števec.

Na koncu prištej še 1 (root).

Kako veš, da si dosegel list?
Oba sinova morata biti nastavljena na null, kar je ekvivalentno temu, da sinov ni.

Zgodovina sprememb…

  • spremenilo: amdsup5 ()

Spura ::

Ciklamen je izjavil:


Pa mi cikla v while zanki, ker najmanjša vrednost nima naslednjega vozlišča null

Potem imas pa narobe drevo. Iskanje najmanjse vrednosti bi moralo bit trivialno implementirat brez rekurzije.

Ciklamen ::

Povej to asistentu :)
- End of the Post ->

Ciklamen ::

Malo sem lenaril čez počitnice, pa mi še ni ratalo tega naredit.

Skratka, ko kličem metodo size() iz main-a, kjer imam polje float-ov takšno

float[] zaporedje = { 1.1f, -9.9f, 16.16f, -25.25f, -1.1f, 4.4f, 36.36f, -16.16f, -4.4f, .0f, 9.9f, 25.25f, 49.49f, -3.3f, -3.5f, 2.5f, 22.3f, 378.3f, -22.4f, 15.8f, 15.9f };


mi vrača size 6. (ne glede ali spreminjam kar koli - dodajam, odvzemam elemente)

Kodo za size() znotraj razreda Vozlišče imam pa takšno, kot je vsepovsod na internetu za najti:

                if (levo == null || desno == null)
                    return 0;
                else
                    return 1 + levo.size() + desno.size();


Ima kdo kak predlog kaj naj naredim? Ne uspem nikakor stvari razvozlat, imam pa še manj kot 2 dni za oddajo naloge :)

EDIT: Pisal sem še asistentu in mi je to odgovoril (glede tega kaj naj bi metoda size() počela)

metoda size() (, ki je že implementirana) znotraj razreda IskalnoDrevo vrne število vozlišč celotnega iskalnega drevesa (metoda deluje nad korenom).
Metoda size() (, ki jo je potrebno implementirati) znotraj razreda Vozlisce pa vrne število vozlišč (pod)drevesa, katerega >>koren<< je trenutno vozlišče.
- End of the Post ->

Zgodovina sprememb…

  • spremenil: Ciklamen ()

c-lox ::

Si zrisal drevo za tisto zaporedje? Ni res globine 6?

Kaj pa za zaporedje { .1f, .2f, .3f, .4f }, vrača 4?
!not my imagination.

Ciklamen ::

c-lox ne iščem globine, iščem število vseh vozlišč v drevesu, če prav razumem kaj je asistent hotel povedat

za tvoje podano zaporedje ne vrača 4 ampak 0.
- End of the Post ->

c-lox ::

Šteje ti samo vozlišča, ki imajo obe vozlišči polni.

if(levo != null && desno != null) return 1 + levo.size() + desno.size();
else if(levo == null) return 1 + desno.size();
else if(desno == null) return 1 + levo.size();
else return 1;
!not my imagination.

Zgodovina sprememb…

  • spremenilo: c-lox ()

Ciklamen ::

Malo si preveč posplošil c-lox, je bilo še treba nekaj dodati da zadeva deluje, vsekakor pa hvala ti! Imaš pivo v dobrem :)
- End of the Post ->

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Predstavitev dvojiškega drevesa z seznamom

Oddelek: Programiranje		141952 (1552) ktka
»

[C++] Iskalno drevo implementacija

Oddelek: Programiranje		52309 (1867) eXoo
»

Za programerske teoretike

Oddelek: Programiranje		478817 (5619) Jerry000
»

C# LinkedList

Oddelek: Programiranje		91195 (1046) PoPon2
»

pomoc pri skladu

Oddelek: Programiranje		51331 (1256) NoUse4AName

Več podobnih tem