---

Skall man bruge en dubbellänkad lista för att göra en sådan implementering
i Java?

Har väldigt svårt att komma igång. Sitter och funderar på om jag kanske ska
ha en array eller vektor istället...

Detta var INTE lätt...

Hoppas på något svar.

---

On Mon, 03 Mar 2003 21:44:12 GMT, "Sussi Svensson"
<042.187716@telia.com> wrote:

> Skall man bruge en dubbellänkad lista för att göra en sådan implementering
> i Java?

Det er en mulighed at skrive sin egen linkede træstruktur. Om det er
fornuftigt/svært afhænger vel af dit behov. Jeg har dog hørt at man i
praksis stort set altid bruger et array/vector. Jeg har absolut ingen
dokumentation eller argumenter for den påstand :)

> Har väldigt svårt att komma igång. Sitter och funderar på om jag kanske ska
> ha en array eller vektor istället...

Med et array er det ikke så svært. Således nummererer du dine knuder:
Lad v være en vilkårlig knude - lad f være en funktion der giver den
indgang i array'et hvor knudens værdi står. Så skal flg. gælde:

Hvis v er rod -> f(v) = 1
Hvis v er venstre barn af knude u -> f(v) = 2*f(u)
Hvis v er højre barn af knude u -> f(v) = 2*f(u)+1

Så er det drønhurtigt at finde børn, forældre osv. Det kan dog godt
koste en del hukommelse hvis den ene del af træet er kæmpehøj og en
anden del af det er meget lav.

Ellers stiller java vel også nogle træstrukturer til rådighed... Hvad
er dit konkrete behov?

--

Rune Simonsen

---

"Sussi Svensson" <042.187716@telia.com> wrote:

> Skall man bruge en dubbellänkad lista för att göra en sådan implementering
> i Java?

Du kan bruge en klasse til at repræsentere knuderne, fx noget i stil med:

class Knude {
   private Knude venstre;
   private Knude højre;
   ...
}

Hvor man kan lade venstre og højre være null hvis knuden ikke har nogen
børn i den retning.

Ellers har Java i java.util.TreeMap implementeret et selvbalancerede
rød-sort-søgetræ.

--
Niels, The Offspring Mailinglist www.image.dk/~teglsbo

---

Sussi Svensson <042.187716@telia.com> skrev:
>Skall man bruge en dubbellänkad
>lista för att göra en sådan
>implementering
>i Java?
>
>Har väldigt svårt att komma igång.
>Sitter och funderar på om jag kanske ska
>ha en array eller vektor istället...
>
>Detta var INTE lätt...
>
>Hoppas på något svar.


Her har du et eksempel. Der er 3 klasser. En person klasse, et
start klasse og en binaertræ klasse. Kig engang lidt på det :)
*******************************************************************

import java.sql.*;
import java.io.*;
public class BinaertTrae
{
   class Element
   {
      String s;      //den gemte værdi

      Element v_son;   //reference til v. søn
      Element h_son;   //reference til h. søn
      Element far;      //reference til far
      Person v;

      Element(String s)
      {
         this.s