Unen wrote:
> Hej!
>
> Jeg har oprettet en træstruktur. Problemmet er at det først oprettede
> element er roden, hvilket kan resulterer i at, der er mange venstre-sønner
> og kun få højre-sønner eller omvendt. Spørgsmålet er så hvorledes der er
> muligt at få balance i træ-strukturen, så der er lige mange sønner til hver
> side?
Du kan lave et preorder gennemløb hvor du gemmer elementerne i en liste.
Denne liste gennemløber du så hvor du starter med det midterste element som
sættes til rod og den venstre halvdel indsættes i venstre undertræ til denne og
den
højre i højre - nogenlunde således:
preorderBalancing( preorderArray, start, end )
{
half = (end-start) / 2;
node = preorderArray[half];
node.left = preorderBalancing( preorderArray, start, half-1 );
node.right = preorderBalancing( preorderArray, half+1, end );
return node;
}
root = preorderBalancing( preorderArray, 0, preorderArray.length );
Ellers kan du kigge på rød-sorte træer og rotationer.
> Jeg har hørt, der skulle være en API, der skulle kunne klare det meste.
Prøv java.util.TreeMap i JDK 1.2 og over
Ulrik Magnusson
--
"What a surprise! A look of terminal shock in your eyes.
Now things are really what they seem."
Pink Floyd - "Sheep", Animals 1977
Visit my home page:
http://www.geocities.com/ulrikm