binarny strom

stewe · Napísal **stewe**: 24.02.2009 11:59

zdravim

mam taky problemik, mam binarny strom v c++.
udaje tam vkladam tak, ze v lavom podstrome
mam vzdy mensie hodnoty ako v rodicovy a v
pravom podstrome vacsie.

Kód:

chapeme sa.

teraz ide o to, ze to mozem cez inorder
vypisat podla velkosti.

v uzle ale uchovavam aj hodnotu, kolko tych
cisel je (napr. sestku som nacital 5 krat,
stvork tri razy atd).

teraz chcem vypisat ten strom od najvacieho
po najmensi pocet tych cisiel.

ale ako na to???

nemozem to zoradovat tak ako to nacitavam, pretoze
este neviem,ake cisla budem mat. (a uz vobec nie kolko)

napadlo ma, ze si zistim pocet uzlov, alokujem take pole,
dvoj rozmerne, kde prva zlozka bude cislo a druha ich pocet.

a toto zoradim podla toho poctu.

ale to je asi nosenie dreva do lesa. potom ten strom akosi straca zmysel.

dik

//edit
este ma napadlo, ze by som mohol prebehnut ten strom inorder, a vzdy precital pocet tych veci v uzle. a nasledne by som paralelne robil druhy strom s tym, ze by som usporaduval podla poctu veci v uzloch.

to je ok az na to, ze co sa stane, ked niektorych cisiel bude take iste mnozstvo ^^

//nabuduce pouzi edit. suchy

neutronmind · Napísal **neutronmind**: 24.02.2009 14:27

Co ja viem, podla mna si si vybral zlu datovu strukturu, binarny strom sa na to moc nehodi. Netvrdim, ze by sa to nedalo, ale je mozne, ze by si mal vacsiu casovu zlozitost ako trebars pri pouziti pola. :rolleyes:

p360t · Napísal **p360t**: 24.02.2009 20:16

Povedal by som, že to záleží od toho, na čo ďalšie ešte ten strom používaš. Ak ho potrebuješ ešte na nejaké iné algoritmy, tak si pridaj pole, alebo spájaný zoznam a tie počty si pamätaj v tom. A ak ho nepotrebuješ, tak ho nahraď len tým poľom/zoznamom.

Výpis binárneho vyhľadávacieho stromu podľa satelitných dát a nie kľúčov je O(n^2) (v najhoršom prípade n-krát navštívime všetkých n vrcholov), efektívne usporiadanie a následný výpis poľa je O(n lg n), čo je teoreticky rýchlejšie, ale v praxi záleží na množstve a povahe tvojich dát a konkrétnych implementáciách algoritmov.

Alebo to môžeš ešte otočiť, udržiavať si binárnu haldu kde kľúčmi budú počty, udržiavať si pointer na nejaký zoznam a tam si pamätať satelitné dáta... Riešení je viac, ale nenapísal si, čo ďalej chceš robiť atď, takže ťažko sa háda "to najlepšie".

stewe · Napísal autor témy **stewe**: 24.02.2009 22:32

mam slovensky text zbaveny diakritiky a medzier. pismena su vsetky velke. ide o to najst frekvenciu pismen, dve pismena spolu, tri pismena spolu.

spravil som ten binarny strom, nezalezi na pocte pismen, ktore nacitam, cize j to univerzalne. v strome udrziavam vsetky vyskyty tych pismen ci skupin. cize napr. mam v koreny stromu "ra" a v lavom dietati "ab" a v pravom "za". a tak dalej. teraz ide o to, zistit pocetnost tej ktorej skupiny znakov. tj. pocet konkretnych dvojic deleno vsetkych dvojic. v node si udrziavam informaciu o pocte vyskytov jednotlivych dvojic (napr. ak nacitam druhy krat "za", tak nespravim dalsi nod, len premennu "count" v triede node zvysim o jedna). takto prebehnem cely text. potom zratam vsetky dvojice (inorder a pripocitavam "count") a takto prebehnem strom a pocty "count" vydelim poctom dvojic. a zistim tu relativnu pocetnost. ide ale o to, ze sice to mam v inorder podla abecedy, ale nemam to od najmensieho po najvacsie podla relativnosti vyskytu (cislo od 0-1).

ono napadlo ma, ze cele to je s tym stromom asi zbytocne. ale zasa, je to rychlejsie zatriedit. kebyze mam zoznam spajany, tak by som musel prebehnut vzdy vsetky prvky toho zoznamu a spytat sa, ci sa tam uz taka kombinacia znakov nenachadza, hmmm, alebo ani nemusel, stacilo by to to pole "delit stale dvoma" a pytal by som sa, ci to je vacsie alebo mensie. cize ta ista zlozitost ako pri strome.

a potom by som to podelil, a to by som zoradil podla tej relativnej pocetnosti.

fuuu no to je na dlho pisat nie este nakodit

no a teraz ma este napadlo

ved ja nepotrebujem v tom spajanom zozname riesit, aby to bolo zoradnene podla abecedy. ved ja to chcem len podla toho vyskytu, takze mi je suma-fuk, ci to mam zoradene. zoradim to len vtedy, ked to idem vypisat. cize si jedno zoradenie usetrim. (a nemusim riesit, aby som vkladal prvky zoznamu od najmensieho po najvacsi (lexikograficky)

stewe · Napísal autor témy **stewe**: 25.02.2009 21:18

spravil som to do spajaneho zoznamu

hlavna funkcia na pridavanie do zoznamu vyzera nasledovne

Kód:

void addItemToList(Node *&start_ptr, string _name) {

   Node *temp, *temp2, *temp3;

   temp = new Node(_name);
   bool vlozene = false;

   if (start_ptr == NULL) {  //ak je list prazdny, zvysime o jedna a priradime vkladane "meno" do prvej polozky
      ++(temp->count);
      start_ptr = temp;
   }
   else { //ak nie je list prazdny
      temp2 = start_ptr;
      do { //prebehni zoznam, ak najdes uzol, ktoreho meno sa rovna s vkladanym, zvys o jedna a skonci
         if (temp2->name == temp->name) {
            ++(temp2->count);
            vlozene = true; //nastav premennu "vlozene" na true
            break;
         }
         temp3 = temp2;
         temp2 = temp2->next;
      }
      while(temp2 != NULL);

      if (!vlozene) { //ak nie je vlozene, (sme na konci zoznamu), tak na konci vloz
         temp3->next = temp;
         temp3->next->count = 1;
      }
   }
}

este treba ale tento zoznam zoradit podla tej frekvencie vyskytu
frekvencia sa pocita ako som napisal v prispevku hore.

neviete niekto ako zoradit zlinkovany zoznam ?

binarny strom

Podobné témy