Hjelp til oppgave om binære søketrær

[xyz2yb]

Jeg trenger sårt den hjelpen jeg kan få til å løse denne oppga.

 

Oppgaven gjelder Binære søketrær.

 

Oppgaven:

 

For at et binærtre skal være et binært søketre må vi for alle nodene ha følgende kriterium tilfredsstilt: alle nodene i venstre subtre har nøkkelverdi som er mindre enn denne nodens nøkkelverdi og alle nodene i høyre subtre ha en nøkkelverdi som er større enn denne.

 

**** A. Skriv en rekursiv metode, isBST(), som sjekker om det gitte binærtreet

tilfredsstiller dette kravet. (Ta gjerne utgangspunkt i BinarySearchTree og BinaryNode)

 

 

Når du skriver ut elementene i et binært søketre i ”in-order” rekkefølge, får du skrevet dem sortert i stigende rekkefølge.

 

**** B. Beskriv to måter å få skrevet ut elementene i et BST sortert i synkende

rekkefølge. Diskuter plassbruk og tidskompleksitet. Implementer begge.

 

 

Av og til kommer du opp i situasjoner hvor du ønsker å behandle nodene i et binærtre nivå-vis. Det vil si at du behandler rota først, så alle nodene med dybde 1, deretter alle med dybde 2 osv..

 

**** C. Beskriv hvordan du kan få til en slik traversering av treet – implementer dette

deretter i java.

 

 

Du skal nå utvide klassen BinarySearchTree med en metode for å returnere høyden i treet. Du kan, på samme måte som Weiss, la denne (offentlige) metoden kalle en privat, rekursiv metode i klassen eller la den kalle en rekursiv metode i klassen BinNode.

 

**** D. Beskriv først hvordan du tenker deg å løse dette og programmer så en av

(/gjerne begge) løsningene.

 

 

Vi skal nå se på effekten av å balansere søketrær.

 

**** E. Generer en tilfeldig sekvens av 10000 heltall og konstruer et BST og et AVL-

treet ved å sette inn disse elementene i rekkefølge hhv. i et tomt BST og et tomt AVL-tre. Finn høyden i de to trærne. Forklar funnene.

Trekk så ut 10 tilfeldige element fra den opprinnelige sekvensen og gjør oppslag på disse (find) i begge trærne. Finn på nytt høyden i de to trærne. Forklar funnene.

 

edit: forandret på emnefeltet. Les notis fra moderator under for regler ang emnefelt

Endret 9. november 2006 av macfjott

[pgdx]

Dette er riktignok et diskusjons- og hjelpeforum, men vi har ikke for vane å løse hele skoleoppgaver. Hvis du har ett og ett spørsmål, kan vi selvsagt hjelpe til, men ikke forvent at dette er skolehjelp (selv om det stort sett har vært det i det siste).

[martbo]

Emnetittelen i denne tråden er ikke god nok, det er ikke mulig å forstå hva tråden omhandler utifra emnetittelen. En god emnetittel er en tittel som forklarer godt hva innholdet i posten din går ut på. En bruker bør kunne skaffe seg oversikt over hovedinnholdet i posten bare ut fra å lese tittelen. Vennligst forsøk å ha dette i tankene neste gang du starter en tråd, og orienter deg om hva vår nettikette sier om dårlig bruk av emnetitler.

 

Bruk -knappen i første post for å endre emnetittelen.

 

(Vennligst ikke kommenter dette innlegget.)

 

Siden du er ny her på forumet har jeg fikset emnefeltet for deg.

[Zolo]

http://en.wikipedia.org/wiki/Binary_search_tree