Výška binárního vyhledávacího stromu – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Výška binárního vyhledávacího stromu – C / C++ – Fórum – Programujte.comVýška binárního vyhledávacího stromu – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Dave-CZ0
Návštěvník
29. 4. 2010   #1
-
0
-

Hoy potřeboval bych pomoc nevím si vůbec rady s tímto příkladem:


Máte dáno přirozené číslo n. Vygenerujte všech n! permutací čísel 0; 1; 2; : : : ; n-1 a pro každou takto vygenerovanou permutaci
vytvořte binární vyhledávací strom.
A u tohoto stromu změřte jeho výšku.
Celkem dostanete n! výšek (nemusí být pochopitelně všechny rùzné). Změřené
výsledky zpracujte do tabulky.
Poznámky
- Pro systematické generování všech permutací lze vymyslet jednoduchý rekurzivní algoritmus pracující s polem.
- Permutace není nutné nejprve vygenerovat a pak z nich vytvářet binárnístromy. Proces vytváření stromu mùžete spustit ihned, jakmile budete mít k dispozici další permutaci. Vytvoříte strom, změříte jeho výšku, kterou
si zaznamenáte. Poté mùžete strom smazat a přejít k vytváření další permutace.
- Strom z permutace vytvoříme tak, že prvky z permutace postupně vložíte do stromu ve stejném pořadí v jakém jsou zapsány v permutaci. Například, je-li permutace (1342) vloříte do stromu nejprve prvek 1, pak 3, pak 4 a nakonec 2.
- Není potřeba implementovat například mazání prvku ze stromu. Naopak ale musíte vymyslet jak spočítat výšku stromu.
- Pro testování použijte základní nevyváženou variantu binárního stromu.
- Program otestujte aspoň pro n = 10, n! = 3628800.


udělal nebo pomohl by mi někdo? diky

Nahlásit jako SPAM
IP: 212.47.23.–
Reklama
Reklama
liborb
~ Redaktor
+18
Guru
29. 4. 2010   #2
-
0
-

A co z toho neumíš? Generovat permutace nad polem čísel? Vytvořit binární strom? Nebo změřit jeho výšku? (kterou můžeš "počítat" už při vytváření stromu ...)

Nahlásit jako SPAM
IP: 91.203.96.–
liborb
~ Redaktor
+18
Guru
29. 4. 2010   #3
-
0
-

A co z toho neumíš? Generovat permutace nad polem čísel? Vytvořit binární strom? Nebo změřit jeho výšku? (kterou můžeš "počítat" už při vytváření stromu ...)

Nahlásit jako SPAM
IP: 91.203.96.–
Dave-CZ0
Návštěvník
29. 4. 2010   #4
-
0
-

To liborb : ten strom :-(

Nahlásit jako SPAM
IP: 212.47.23.–
liborb
~ Redaktor
+18
Guru
29. 4. 2010   #5
-
0
-

Uzel stromu tvoří struktura, která obsahuje hodnotu a pointery na levou a pravou větev. Do levé větve se ukládají čísla menší než v daném uzlu a do pravého větší. Toto platí pro každý uzel. Lepší?

Nahlásit jako SPAM
IP: 91.203.96.–
Dave-CZ0
Návštěvník
29. 4. 2010   #6
-
0
-

hm tak nevim nejak mi to nedje vubec, nevim co mam udelat driv :-( kaslu uz dneska na to nad se zitra bude daril vic

Nahlásit jako SPAM
IP: 212.47.23.–
add
~ Anonymní uživatel
2 příspěvky
30. 4. 2010   #7
-
0
-

To Dave-CZ : jetsli chces tu mas nerekurzivni vyhledavaci strom (sem se ho nejak pokusil vytvorit), je trochu delsi a nevim jetsli funguje poradne snad jo

Nahlásit jako SPAM
IP: 77.48.244.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
30. 4. 2010   #8
-
0
-

Nebo změřit jeho výšku? (kterou můžeš "počítat" už při vytváření stromu ...)

tahle cast by me zajimala, nevim totiz jak tu vysku pocitat "za behu".

Nahlásit jako SPAM
IP: 85.70.201.–
liborb
~ Redaktor
+18
Guru
30. 4. 2010   #9
-
0
-

Když si vezmeš třeba ten kód, co se dal add (mimochodem je v něm malá chybička, která se v tomto případě nikdy neprojeví :smile1: ), tak můžeš při vkládání nového prvku počítat, jak hluboko už se v tom procházení dostal. U kořene je to 1, další patro +1 atd.

Nahlásit jako SPAM
IP: 85.207.166.–
anonym
~ Anonymní uživatel
429 příspěvků
30. 4. 2010   #10
-
0
-

bol by niekto tak dobry a hodil by tu cely kompletny kod (hlavne tu vysku), ako by to malo vypadat?diky moc ak..

Nahlásit jako SPAM
IP: 195.39.122.–
Anonymný užívatel
~ Anonymní uživatel
1 příspěvek
30. 4. 2010   #11
-
0
-

A ešte by ma zaujímalo, ako z tých permutácii (algoritmus pre tvorbu permutácii mam hotový) mam prechádzat na tvorbu nového stromu?dik za odpoveď

Nahlásit jako SPAM
IP: 195.39.122.–
add
~ Anonymní uživatel
2 příspěvky
30. 4. 2010   #12
-
0
-

To liborb : prosimtě mohl bys mi napsat jaka chyba ..diky

Nahlásit jako SPAM
IP: 77.48.244.–
Dave-CZ0
Návštěvník
30. 4. 2010   #13
-
0
-

To Anonymný užívatel : nechces poslat ten kod na permutaci?

Nahlásit jako SPAM
IP: 212.47.23.–
liborb
~ Redaktor
+18
Guru
30. 4. 2010   #14
-
0
-

To anonym : Před while daš výška=1, hned za while výška+=1 a za cyklem máš poslední "nalezenou" výšku. Tu porovnáš s uloženým maximem a případně uložíš nové.
Nový strom začneš tak, že předchozí smažeš.

To add : Nastavuješ tree=kořen po použití, ale jenom při vkládání. Při vstupu 5, 2, 6, 6, 1 se ti ta 1 vloží vlevo vedle 6. Nastavení tree=kořen by stačilo jednou, ale před vstupem do cyklu. Tu nejsou stejná čísla, takže by se to neprojevilo.

Nahlásit jako SPAM
IP: 91.203.96.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
30. 4. 2010   #15
-
0
-

to Dave-CZ: algoritmus na permutaciu mam ale nedari sa mi z tych permutacii vytvorit nove stromy..ak by si vedel viac tak mi to mozes sendnut pls? sak napis na icq 496495365 a mozme to poriesit

Nahlásit jako SPAM
IP: 195.39.122.–
2. 5. 2010   #16
-
0
-

v zadání máš napsáno:

"Zdrojový kód k binárnímu vyhledávacímu stromu je ve skriptech"

tak využij ten kód. Pravděpodobně bys mohl použít funkci pro přidání, která tam zcela jistě je.
Já jsem použil zdroják stromu ze cvika a přidávám do tam takhle:

add_strom(tr, hod);

Nahlásit jako SPAM
IP: 93.99.61.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
2. 5. 2010   #17
-
0
-

To JiříSedláček : jasne uz to mam...ostal mi uz len posledny problem..a tym je ta vyska..vypisuje mi to vysku kazdeho uzlu no neviem to spravit tak aby mi program vypisoval len absolutnu vysku stromu..je to tym ze tu vysku zistujem v metode InsertNode();..nejako sa mi nedari vybrat z nej tu "najvyssiu vysku" uzlu... :/ ak vies ako na to mohli by sme sa poradit popripade..icq 496495365

Nahlásit jako SPAM
IP: 195.39.122.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
9. 5. 2010   #18
-
0
-

AHoj,

nemuze mi poslat nekdo zkompilovany tento program pro porovnani vlastnich vysledku?

binarnistrom@seznam.cz

dik

Nahlásit jako SPAM
IP: 89.176.203.–
Dave-CZ0
Návštěvník
10. 5. 2010   #19
-
0
-

hoy pomohl by mi nekdo objasnit tuto fci- jakym stylem to funguje a co se tam deje???



int PridejUzel(strom* st, int x) //Přidá prvek do stromu
{
prvek* n;
n = (prvek*)malloc(sizeof(prvek));
n->uzel = x;
n->kam[0] = NULL;
n->kam[1] = NULL;
prvek** p;
p = &(st->koren);
while (*p)
p = &((*p)->kam[x>(*p)->uzel]);
*p = n;
return 0;
}

vubec nevim o co tam jde pomuze mi nekdo objasnit muj problem a co znamenaji ty *
diky moc za kazdou pomoc

Nahlásit jako SPAM
IP: 212.47.23.–
liborb
~ Redaktor
+18
Guru
11. 5. 2010   #20
-
0
-

Vytvoříš nový prvek stromu (n) a uložíš do něj hodnotu (následovníci jsou NULL).

Potom procházíš strom. Využívá se tam toho, že porovnání hodnot (x a v právě procházeném uzlu (*p)->uzel) má výsledek 0 nebo 1.

Nakonec vkládáš nový prvek (uložíš si pointer na pro něj alokovanou paměť).

* označuje pointer (ukazatel) viz třeba zde http://programujte.com/?akce=clanek&cl=2005060502-c++-9-lekce

Nahlásit jako SPAM
IP: 85.207.166.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
11. 5. 2010   #21
-
0
-

ja mam trochu jiny problem mam uz strukturu stromu udelanou ale nevim jak zjistim jeho vysku nekde jsem zjistil toto:

function height($tree=null, $subkoren){
$h=1;
if($tree==null) return -1;
$hl=height($tree, $tree[$subkoren]['left']); // left
$hr=height($tree, $tree[$subkoren]['right']); // right
$h+=max($tree[$subkoren]['left'], $tree[$subkoren]['right']);
return $h;
}

jendoduseji receno, jak jednoduse zjistim vysku stromu kdyz uz ho mam sestaveny?

ale to mi pripada hodne masochysticke..

Nahlásit jako SPAM
IP: 89.176.203.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
11. 5. 2010   #22
-
0
-

http://www.comp.dit.ie/rlawlor/Alg_DS/searching/3.%20%20Binary%20Search%20Tree%20-%20Height.pdf

tady je to zjistovani height

Nahlásit jako SPAM
IP: 89.176.203.–
Dave-CZ0
Návštěvník
20. 5. 2010   #23
-
0
-

Hoy lidi nutne potrebuju pomoc.....
Udelal jsem program, ale......
1. má to být pro všechna "n" a ja to mam jen pro "n=1 - 10"
2. potřebuju nejak udělat jednodušei tu výsku(s tim jak to mam ja mi pomahal kamoš a ja tomu nerozumím)


Pomohl by mi nekdo???
moc díky

Nahlásit jako SPAM
IP: 212.47.23.–
liborb
~ Redaktor
+18
Guru
21. 5. 2010   #24
-
0
-

add 1) Dynamická alokace paměti. Zadáš n, potom:



int* myints = new int[n];
for (int i = 1;i <= n;i++) myints[i] = i;


Stejně musíš alokovat paměť pro pole s "histogramem" výšek (c). Vynulovat ho můžeš for cyklem nebo přes memset.


add 2) To počítání výšky se mi moc nelíbí, udělal bych to nějak takto:


int Uzel::NajdiVysku()
{
int vyskaL = 1;
int vyskaP = 1;

if (leva != NULL) vyskaL = leva->NajdiVysku() + 1;
if (prava != NULL) vyskaP = prava->NajdiVysku() + 1;

return(max(vyskaL, vyskaP));
}


a následně počítání četnosti (pro počet prvků 10 to bude vracet hodnoty 4 až 10):


int vyska = Strom->NajdiVysku();
// buď takto nebo pro c alokovat n + 1 prvků a může tam být jen [vyska]
c[vyska - 1]++;


A dále ... mazání stromu. Smažeš pouze kořen, ostatní alokovaná paměť zůstane nesmazaná - udělej destruktor, kde smažeš i další prvky toho stromu (opět jeho procházením).

No a poslední připomínka ... goto ... jeho použití je sice možné, ale musí proto být hodně dobrý důvod. To není tento případ. Místo odskoku přes goto, tam vlož to hlášení, co máš na konci a program ukonči třeba return(-1);

Nahlásit jako SPAM
IP: 85.207.166.–
Dave-CZ0
Návštěvník
21. 5. 2010   #25
-
0
-

To liborb : diky za pomoc ;)

Nahlásit jako SPAM
IP: 212.47.23.–
Dave-CZ0
Návštěvník
21. 5. 2010   #26
-
0
-

To liborb : hm ale jaksi mi to nejde :-(
nemohl bys mi to prepsat v tom mojem programu a poslat?? ja nevim co a jak :-(

Nahlásit jako SPAM
IP: 212.47.23.–
liborb
~ Redaktor
+18
Guru
21. 5. 2010   #27
-
0
-

Tak sem dej zase tvůj pokus (výpis + zip) a uvidíme, kde je problém. Ale klidně ti to sem v pondělí hodím a možná mě někdo předběhne :-).

Nahlásit jako SPAM
IP: 195.189.143.–
Dave-CZ0
Návštěvník
21. 5. 2010   #28
-
0
-

tak uz mi to jde ale jeste mi nejde aby se mi ta vyska zapsala do cetnosti a vypis.....

Nahlásit jako SPAM
IP: 212.47.23.–
Dave-CZ0
Návštěvník
21. 5. 2010   #29
-
0
-

No nejhorší je, že to potřebuju do neděle poslat.. :-(

Nahlásit jako SPAM
IP: 212.47.23.–
Dave-CZ0
Návštěvník
21. 5. 2010   #30
-
0
-

Tady to je, jen mi nejde ten vypis na obrazovku a jesšte musim vymyslet permutace

Nahlásit jako SPAM
IP: 212.47.23.–
liborb
~ Redaktor
+18
Guru
21. 5. 2010   #31
-
0
-

Permutace si tam měl, ne? A výpis, stejně jako všechno pro N hodnot, musíš dělat v cyklu.

Nahlásit jako SPAM
IP: 195.189.143.–
Dave-CZ0
Návštěvník
21. 5. 2010   #32
-
0
-

no nejak to zkusim

Nahlásit jako SPAM
IP: 212.47.23.–
Dave-CZ0
Návštěvník
21. 5. 2010   #33
-
0
-

ale stale se pokousim a nic mi nejde :-(

Nahlásit jako SPAM
IP: 212.47.23.–
Dave-CZ0
Návštěvník
21. 5. 2010   #34
-
0
-

Tak ted uz mi jde Permutace ale stale mi nejde ta vyska do cetnosti :-(

Nahlásit jako SPAM
IP: 212.47.23.–
Dave-CZ0
Návštěvník
21. 5. 2010   #35
-
0
-

Tak mi zase nejde tam Permutace.... mam ji danou jako



for (int p=1;p<=n;p++) Permutace=Permutace+cetnost[p];

ale problem bude asi s tou cetnosti že?(nic v ni nemam

Nahlásit jako SPAM
IP: 212.47.23.–
Dave-CZ0
Návštěvník
22. 5. 2010   #36
-
0
-

Hoy lidi potřebuju nutne pomoct... .stale mi nejde dat ta vyska do cetnosti... pomuze mi nekdo?

Nahlásit jako SPAM
IP: 212.47.23.–
liborb
~ Redaktor
+18
Guru
22. 5. 2010   #37
-
0
-

Do archivu se nemůžu podívat ... dej sem výpis toho programu.

Nahlásit jako SPAM
IP: 195.189.143.–
Dave-CZ0
Návštěvník
22. 5. 2010   #38
-
0
-

jo uz to jde uz jsem to vyresil..... diky za pomoc ;)

Nahlásit jako SPAM
IP: 212.47.23.–
Sushi
~ Anonymní uživatel
1 příspěvek
12. 5. 2014   #39
-
0
-

Potřeboval bych pomoct se zjištěním výšky vyhledávacího binárního stromu.

Nahlásit jako SPAM
IP: 85.70.239.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 63 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý