[ tacka @ 04.02.2009. 12:14 ] @
ima li ko code za binarno drvo.
sa neta sam poskidao na desetine ali nijedan neradi kako treba.
treba za niz od n brojeva napraviti bdrvo.
ovaj kod doda prvi levo i desno a sve ostale onda smesti ispod njih desno.
package bs;


import java.lang.Math;

public class Stablo {
class Cvor {
Cvor manji;
int vrednost;
Cvor veci;

public Cvor(int vrednost) {
this.vrednost = vrednost;
this.manji = this.veci = null;

}

public void dodaj(int d) {
if (d < vrednost) {
if (manji == null) {
manji = new Cvor(d);
} else {
manji.dodaj(d);
}
} else if (d > vrednost) {
if (veci == null) {
veci = new Cvor(d);
} else {
veci.dodaj(d);
}
}
}
}
private Cvor root;

public Stablo() {
root = null;
}

public void dodajCvor(int d) {
if (root == null)
root = new Cvor(d);
else
root.dodaj(d);
}

private void inOrderDriver(Cvor cvor) {
if (cvor == null)
return;
else {
inOrderDriver(cvor.manji);
System.out.print(" " + cvor.vrednost + " -> ");
inOrderDriver(cvor.veci);
}
}

public void inOrderTraversal() {
inOrderDriver(root);
}

public static void main(String[] args) {
Stablo novoStablo = new Stablo();
int i, j, k;
int duz = 15;
for (i = 0; i < duz; i++) {
j = (int)(100 * Math.random());
System.out.print(j + " ");
novoStablo.dodajCvor(j);
}
System.out.println("\n\n");

System.out.println("Traversal : ");
System.out.println(" ");
novoStablo.inOrderTraversal();
System.out.println(" ");
System.out.println("\n *****************\n");
System.out.println("\n");
}
}
[ tacka @ 22.02.2009. 13:12 ] @
evo resenje ako kome bude trebalo
[ narko @ 23.02.2009. 14:35 ] @
Koliko znam, zar BST stablo ne bi trebalo da ima i transformacije zbog ravnoteze (visina levog i desnog pod stabla da se ne razlikuju za vise od 1)??? To ovde nigde ne vidim..
[ grizzly @ 23.02.2009. 20:01 ] @
Nema potreba za transformacijama. BST stablo koje je balansirano (znaci transformacijama se odrzava ista) je AVL stablo.
[ Sapphire @ 23.02.2009. 20:26 ] @
Mozda malo offtopic, ali vjerujem da moze biti jako korisno... Knjiga iz koje sam ja ucio algoritme i strukture podataka ( od listi, preko red-black i 2-3-4 stabala, pa do hash tabela i grafova -- ima i algoritam trazenja najkraceg i najoptimalnijeg puta tezinskog grafa) je

Data structures & Algorithms in Java - Robert Lafore.

Knjiga je puna primjera, super objasnjeno sve, + u Javi je sto je tebi dodatna pogodnost.
[ tacka @ 23.02.2009. 22:46 ] @
hvala svima na javljanju.
zadatak se svodio da se pri samom punjenju stabla, odmah vrsi pravilno rasporedjivanje.
ukoliko je dalje potrebno brisanje ili dodavanje elemenata - onda ovo nebi bilo ok i biolo bi potrebno napraviti avl stablo koje je samo balansirajuce.
u svakom slucaju hvala na javljanju.
probacu da nahvatam gornju knjigu da je skinem.
pozdrav svima.

nasao knjigu - hvala

[Ovu poruku je menjao tacka dana 24.02.2009. u 00:02 GMT+1]
[ narko @ 24.02.2009. 16:02 ] @
Citat:
grizzly: Nema potreba za transformacijama. BST stablo koje je balansirano (znaci transformacijama se odrzava ista) je AVL stablo.


a da.. ja nesto prevideo.. hvala

Tacka, ajde, ako ti nije problem, posalji mi tu knjigu na mail.. [email protected]
Zeleo bih da je proucim :)

hvala unapred

[Ovu poruku je menjao narko dana 24.02.2009. u 17:27 GMT+1]
[ Dejan Lozanovic @ 24.02.2009. 16:36 ] @
Ako ti treba zbog ucenja jave onda ok , ali ako prakticno nesto koristis pogledaj java.util.Map interface, a imas java.util.TreeMap kao jednu od implementacija koja vrednosti uzima kao drvo i pogodna je za velicine do recimo 1000 elemenata, sve preko toga java.util.HashMap.
[ narko @ 25.02.2009. 13:43 ] @
vise mi treba za ucenje.. lako cu nesto implementirati ako ga prvo dobro naucim :)
[ Sapphire @ 25.02.2009. 14:56 ] @
U danasnjem svijetu programiranja, vrlo je mala mogucnost da ce ti ikada zatrebati da rucno pravis bilo sta od ovoga. Uz genericse, template ili koji god vec nacin programiranja, to je sve vec implementirano u hrpi biblioteka, virtuelno za skoro sve moguce programske jezike. Gdje god da se okrenes, imas gotove hash tabele, vezane liste... mislim da standardne nizove vise nitko i ne koristi (na platformama kao sto su .NET ili Java, ne mislim na C++ ili neke druge "nize" jezike).
Zasto onda da ucis bilo sta od toga, kad imas sve gotovo?

Najbolja investicija u svoje sposobnosti kao programer, je bas da ucis ovakve low level "gluposti". Mnogi programerski problemi ce ti biti mnogo jednostavniji za rijesiti, i razbijanje glave oko nekog tamo grafa ce ti se visestruko isplatiti. Ucenjem ovakvih stvari, uz design patterne, neke metodologije programiranja (kao npr. Test Driven Development, i neke odredjene platforme za rad (again: .NET, Java itd..); imas sve potrebno da budes vrlo uspjesan i kvalitetan.

P.S. da dodam, kad sam gore spominjao "u danasnjem svijetu programiranja", mislio sam na najcesce poslove oko programiranja. Pod tim ne smatram te iste ljude koji pisu te biblioteke, rad na embedded ili realtime sistemima (gdje radi nekog razloga moze zatrebati da sam napises neku vrlo slozenu strukturu podataka) itd...

EDIT: btw, napisite i kako vam se svidja knjiga

[Ovu poruku je menjao Sapphire dana 25.02.2009. u 16:21 GMT+1]
[ Bl4nky_vu @ 24.03.2009. 20:09 ] @
...ili TreeSet, ili HashSet.

Samo sto se tice TreeSet, performance mu i nisu bas najjaca strana....negdje log(n)0