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