/ Forside / Teknologi / Udvikling / Java / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Java
#NavnPoint
molokyle 3688
Klaudi 855
strarup 740
Forvirret 660
gøgeungen 500
Teil 373
Stouenberg 360
vnc 360
pmbruun 341
10  mccracken 320
Binær træ, og sletning af en selv bestemt ~
Fra : Rune Klausen


Dato : 25-11-02 21:14

Hejsa alle Java-hajer :)

Jeg har et lille problem med at få slette en selv valgt node i et binær træ
Jeg har tænke at gøre det som noget i retningen af

public void slet(int nr, Node temp)
{
Node right, left;

if(temp != null)
{
slet(nr, temp.getLeftNode());
if(nr == temp.getMedlem().getMedlemsnummer())
{
//Hvis det er roden som slettes

if(rod.getLeftNode() != null)
{

right = rod.getRightNode();
rod.setRightNode(null);
rod = rod.getLeftNode();
Indsaet(right.getMedlem(), right);
}
else
{
left = rod.getLeftNode();
rod.setLeftNode(null);
rod = rod.getRightNode();
Indsaet(left.getMedlem(), left);
}



//Hvis det er en af de nederste i træet
if((temp.getLeftNode().getLeftNode() == null) &&
(temp.getLeftNode().getRightNode() == null))
temp.setLeftNode(null);
else if((temp.getRightNode().getLeftNode() == null) &&
(temp.getRightNode().getRightNode() == null))
temp.setRightNode(null);
}
slet(nr, temp.getRightNode());
}
}

public Node Indsaet(Medlem medlem, Node temp)
{
if(temp == null)
{
temp = new Node(medlem);
return temp;
}

else
{
if(temp.vej(medlem.getMedlemsnummer()))
temp.setLeftNode(Indsaet(medlem, temp.getLeftNode()));
else
temp.setRightNode(Indsaet(medlem, temp.getRightNode()));
return temp;
}
}

Men jeg kan godt se der er noget galt :(
Jeg er snart løbet tør for ider til hvordan jeg kan løse det, og ikke en af
dem virker...

Men er det noget med at jeg skal have en peger til at pege på den node som
ligger over node som jeg står i ?

så jeg kan gå en tilbage før den som skal slettes, og så lave noget i
retningen af

f.eks. above.setLeftNode(null);

eller hvordan ?

håber der en nogen som kan hjælpe mig

-Rune





 
 
Ulrik Magnusson (25-11-2002)
Kommentar
Fra : Ulrik Magnusson


Dato : 25-11-02 22:56



Rune Klausen wrote:

> Hejsa alle Java-hajer :)
>
> Jeg har et lille problem med at få slette en selv valgt node i et binær træ
> Jeg har tænke at gøre det som noget i retningen af

<snip>

Nu har jeg ikke kigget så meget på din kode, men en fremgangsmåde
kunne være:

Node slet( int nr, Node root )
{
if( root.getNr() == nr )
{
// hvis der er flest knuder i venstre undertræ (hvor alle knuder < rod)

// så træk største knude i venstre undertræ op som rod
if( root.leftNode().countChildren() > root.rightNode().countChildren()
)
{
newRoot = maxNode( root.leftNode() )
}
// ellers hvis der er flest knuder i højre undertræ (hvor alle knuder >
rod)
// så træk mindste knude i venstre undertræ op som rod
else
{
newRoot = minNode( root.RightNode() )
}
newRoot.setLeftNode( root.leftNode() );
newRoot.setRightNode( root.rightNode() );
return newRoot;
}
else if( root.getNr() < nr ) // søg kun videre i højre undertræ
{
// ny højre er den rod som er resultatet af sletning i højre undertræ
root.setRightNode( slet( nr, root.rightNode() ) );
// roden i dette undertræ er den samme som før
return root;
}
else// root.getNr() > nr - søg kun videre i venstre undertræ
{
// ny venstre er den rod som er resultatet af sletning i venstre
undertræ
root.setLeftNode( slet( nr, root.leftNode() ) );
// roden i dette undertræ er den samme som før
return root;
}
}

//kald af slet:
root = slet( 42, root );


setLeftNode() og setRightNode() er sikkert ikke vildt dyre og
kaldstakkens størrelse er i logaritmisk forhold til træets størrelse
og derfor ikke vildt dyr. En ikke-rekursiv fremgangsmåde er sikkert
alligevel noget hurtigere i store træer - jeg kunne dog ikke lige koge
én sammen - eller "This is left as an exercise for the reader"
(hint: brug en stak i stedet for rekursivt kald ).

Ulrik Magnusson


Rune Klausen (26-11-2002)
Kommentar
Fra : Rune Klausen


Dato : 26-11-02 07:47


"Ulrik Magnusson" <ulrikm@yahoo.com> wrote in message
news:3DE29C5B.A062AE1A@yahoo.com...
> setLeftNode() og setRightNode() er sikkert ikke vildt dyre og
> kaldstakkens størrelse er i logaritmisk forhold til træets størrelse
> og derfor ikke vildt dyr. En ikke-rekursiv fremgangsmåde er sikkert
> alligevel noget hurtigere i store træer - jeg kunne dog ikke lige koge
> én sammen - eller "This is left as an exercise for the reader"
> (hint: brug en stak i stedet for rekursivt kald ).

tak skal du have, der er lidt at kigge på i aften :)

-Rune



Lasse Westh-Nielsen (26-11-2002)
Kommentar
Fra : Lasse Westh-Nielsen


Dato : 26-11-02 14:56

Betyder ordningen af knuderne i dit træ noget?

For hvis nu det er et binært søgetræ, så er det ikke helt simpelt bare at
slette en knude... Kig evt. på rød/sorte søgetræer.

Hvis det er ligemeget, så kan du "kigge-nedad": du står i en knude, og
spørger til dens børn. Hvis et af børnene skal slettes, skal du egentlig
bare finde den nye rod blandt "sletteknudens" børn, og sætte den knude du
står i til at pege på den.

Mvh Lasse



"Rune Klausen" <rune.klausen@paradis.dk> wrote in message
news:3de28490$0$82067$edfadb0f@dtext01.news.tele.dk...
> Hejsa alle Java-hajer :)
>
> Jeg har et lille problem med at få slette en selv valgt node i et binær
træ
> Jeg har tænke at gøre det som noget i retningen af
>
> public void slet(int nr, Node temp)
> {
> Node right, left;
>
> if(temp != null)
> {
> slet(nr, temp.getLeftNode());
> if(nr == temp.getMedlem().getMedlemsnummer())
> {
> file://Hvis det er roden som slettes
>
> if(rod.getLeftNode() != null)
> {
>
> right = rod.getRightNode();
> rod.setRightNode(null);
> rod = rod.getLeftNode();
> Indsaet(right.getMedlem(), right);
> }
> else
> {
> left = rod.getLeftNode();
> rod.setLeftNode(null);
> rod = rod.getRightNode();
> Indsaet(left.getMedlem(), left);
> }
>
>
>
> file://Hvis det er en af de nederste i træet
> if((temp.getLeftNode().getLeftNode() == null) &&
> (temp.getLeftNode().getRightNode() == null))
> temp.setLeftNode(null);
> else if((temp.getRightNode().getLeftNode() == null) &&
> (temp.getRightNode().getRightNode() == null))
> temp.setRightNode(null);
> }
> slet(nr, temp.getRightNode());
> }
> }
>
> public Node Indsaet(Medlem medlem, Node temp)
> {
> if(temp == null)
> {
> temp = new Node(medlem);
> return temp;
> }
>
> else
> {
> if(temp.vej(medlem.getMedlemsnummer()))
> temp.setLeftNode(Indsaet(medlem, temp.getLeftNode()));
> else
> temp.setRightNode(Indsaet(medlem, temp.getRightNode()));
> return temp;
> }
> }
>
> Men jeg kan godt se der er noget galt :(
> Jeg er snart løbet tør for ider til hvordan jeg kan løse det, og ikke en
af
> dem virker...
>
> Men er det noget med at jeg skal have en peger til at pege på den node som
> ligger over node som jeg står i ?
>
> så jeg kan gå en tilbage før den som skal slettes, og så lave noget i
> retningen af
>
> f.eks. above.setLeftNode(null);
>
> eller hvordan ?
>
> håber der en nogen som kan hjælpe mig
>
> -Rune
>
>
>
>



Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste