Trenger hjelp til oppg. angående binært tre

[xyz2yb]

Trenger hjelp til å få skrevet binærtreet mitt ur i synkende rekkefølge, jeg har skrevet det ut en gang ved hjelp av en slags "att-fram-rekursiv-in-order-traversering", men trenger hjelp til å skrive det ut ved å putte alle nodene inn på en stakk for å så skrive dem ut fra stakken.

Trenger også hjelp til oppgave c.

 

Oppgaven.

-----------------------------------------------------------------------------------------------

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.

-----------------------------------------------------------------------------------------------

 

Her er min Javakode AVLtre

-----------------------------------------------------------------------------------------------

 

 

public class AVLTre {

 

/** Rotnoden til treet */

private AVLNode root;

/** en kø representert ved en lenka liste */

private Liste ko;

 

public AVLTre() {

 

root = null;

ko = new Liste();

}

 

/**

* Sjekker om treet tilfredstiller kravene som stilles til

* et binærtre.

*/

public void isBest(){

// treet er tomt!

if (root == null) {

System.out.println("Sorry, dette treet har endt opp som ved!");

}else{

if (root.left.x < root.x && root.right.x > root.x){

System.out.println("Treet tilfredstiller kravene. " + "\n");

}else{

System.out.println("Systemet tilfredstiller ikke kravene. ");

}

 

}

}

 

/**

* Rerutnerer høden til en gitt node

* Returnerer -1 dersom noden ikke eksisterer

* @param a (node)

* @return (høyde)

*/

private int hoyde(AVLNode a) {

if (a != null) {

return a.h;

} else {

return -1;

}

}

 

/**

* Klaffs inn en ny node

*

* @param x (innhold)

*/

public void add(int x) {

root = add(x, root);

}

 

/**

* Klaffs inn en ny node

*

* @param x (innhold)

* @param ny (AVLNode)

* @return (AVLNode)

*/

private AVLNode add(int x, AVLNode ny) {

 

// sjekker om treet er tomt..

if (ny == null) {

ny = new AVLNode(x, null, null);

 

} else if (x < ny.x) {

ny.left = add(x, ny.left);

if (hoyde(ny.left) - hoyde(ny.right) == 2) {

if (x < ny.left.x) {

ny = roterVS(ny);

} else {

ny = DBLroterVS(ny);

}

}

} else if (x > ny.x) {

ny.right = add(x, ny.right);

if (hoyde(ny.right) - hoyde(ny.left) == 2) {

if (x > ny.right.x) {

ny = roterHS(ny);

} else {

ny = DBLroterHS(ny);

}

}

} else{

 

}

// Kalkulerer h�yden til den nye noden(AVLNoden)

ny.h = Math.max(hoyde(ny.left), hoyde(ny.right)) + 1;

 

return ny;

}

 

/**

* Me lyt sveiva til venstre!

* Metode for å balansere treet

* @param ny

* @return

*/

private AVLNode roterVS(AVLNode ny) {

AVLNode nyere = ny.left;

ny.left = nyere.right;

nyere.right = ny;

ny.h = Math.max(hoyde(ny.left), hoyde(ny.right)) + 1;

nyere.h = Math.max(hoyde(nyere.left), ny.h) + 1;

 

return nyere;

}

 

/**

* Me tek han ein gong te, karar!!

* Metode for å balansere treet

* @param ny

* @return

*/

private AVLNode DBLroterVS(AVLNode ny) {

ny.left = roterHS(ny.left);

return roterVS(ny);

}

/**

* Andre veien!!

* Metode for å balansere treet

* @param ny

* @return

*/

private AVLNode roterHS(AVLNode ny) {

AVLNode nyere = ny.right;

ny.right = nyere.left;

nyere.left = ny;

ny.h = Math.max(hoyde(ny.left), hoyde(ny.right)) + 1;

nyere.h = Math.max(hoyde(nyere.left), ny.h) + 1;

 

return nyere;

}

/**

* Enda meir andre veien!!

* Metode for å balansere treet

* @param ny

* @return

*/

private AVLNode DBLroterHS(AVLNode ny) {

ny.right = roterVS(ny.right);

return roterHS(ny);

}

/**

* Første versjon Skriver ut treet i synkende rekkefølge

* ved hjelp av rekursjon

*

*/

public void print1() {

// treet er tomt!

if (root == null) {

System.out.println("Sorry, dette treet har endt opp som ved!");

 

// treet er IKKE tomt

} else {

print1(root);

}

}

 

/**

* Nei d e d denne som gjør! Skriver ut treet i en slags

* "att-fram-rekursiv-in-order-traversering"

*

* @param x (den noden vi skal begynne i)

*

*/

private void print1(AVLNode g) {

 

// Ja, enn gang må d jo ta slutt....

if (g != null) {

 

print1(g.right);

System.out.print(g.x + ", ");

print1(g.left);

}

}

 

/**

* Skriver ut treet i synkende rekkefølge, uten rekursjon.....

*

*/

public void print2(){

// Her trenger jeg HJELP!

// Bruk en stakk, stapp alle verdian på stakken, og skriv dem ut fra stakken!!

}

 

/**

*

* Skriver ut treet fra toppen(rota) og nedover fra venstre mot

* høyre.........

*

*/

public void print3() {

 

if (root != null) {

print3(root);

} else {

// Treet er tomt!

System.out.println("En eller annen fjått har hugget ned treet!");

}

}

 

/**

* Skriver ut treet fra "kvasirota" og nedover.....

*

* @param x (kvasi root)

*/

private void print3(AVLNode g) {

// skriv ut nodens innhold

System.out.print(", " + g.x);

 

// har noden et venstre-barn?

if (g.left != null) {

// i så fall sett det i kø...

ko.add(g.left);

}

// har noden et h�yre-barn?

if (g.right != null) {

// i så fall sett det i kø...

ko.add(g.right);

}

try {

// prøver å hente første node i køen, og kalle print på den!

print3(ko.pop());

 

} catch (Exception s) {

// Ja, da va lista tom.....

}

}

 

/**

* Finner høyden av treet!

* @return

*/

public int getHoyde(){

return root.h;

}

 

 

-----------------------------------------------------------------------------------------------

Bekalger koden

Endret 14. november 2006 av xyz2yb

[qualbeen]

rediger det du har skrevet, og putt [spoiler] før koden din, og [/spoiler] etter. På den måten slipper man milelang post...

(Dette innlegget blir forøvrlig skrevet inni en code-blokk fordi det er eneste mulighet å nevne [spoiler]-funksjonen uten å få en spoiler selv..)

[pgdx]

Hva mener du? Inni [spoiler] og [/spoiler] ?

[sim]

I oppgave C kan du bruke et bredde først-søk, eller bredde først-traversering. Dette implementeres med en FIFO-kø. For hver node du behandler legger til til alle barna i køen. Les mer på wikipedia.