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

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.

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 ...)

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 ...)

To liborb : ten strom :-(

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ší?

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

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

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

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.

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

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ď

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

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

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.

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

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);

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

AHoj,

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

binarnistrom@seznam.cz

dik

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;

}

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

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..

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

tady je to zjistovani height

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

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

int* myints = new int[n];

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

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));

}

int vyska = Strom->NajdiVysku();

// buď takto nebo pro c alokovat n + 1 prvků a může tam být jen [vyska]

c[vyska - 1]++;

To liborb : diky za pomoc ;)

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

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 :-).

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

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

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

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

no nejak to zkusim

ale stale se pokousim a nic mi nejde :-(

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

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

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

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

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

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

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