---

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

---

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

---

"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

---

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