[alg] Vanuit een Tree alle volgende items achterhalen

[riezebosch]

item 1
   |--item 1.1
   |    |--item 1.1.1
   |    |--item 1.1.2
   |    |    |--item 1.1.2.1
   |    |--item 1.1.3
   |
   |--item 1.2
   |    |--item 1.2.1
   |    |--item 1.2.2
   |    |--[b]item 1.2.3[/b]
   |    |    |--item 1.2.3.1
   |    |--item 1.2.4
   |
   |--item 1.3
   |    |--item 1.3.1
   |    |--item 1.3.2
   |         |--item 1.3.2.1

Nu is mijn vraag: hoe converteer ik dit naar een lijst, met als uitgangspunt item 1.1.2, met daarvoor alle parents, daarna alle children, en daarna ook nog alle volgende children van de parents:

1, 1.2, [b]1.2.3[/b], 1.2.3.1, 1.2.4,1.3, 1.3.1, 1.3.2, 1.3.2.1

Ik zat erover te denken om de items kennis te geven van het volgende item op hetzelfde niveau, en dan vanuit het geselecteerde child de lijst van de parent en de volgende items op te bouwen. Deze bouwt dan recursief de lijst van zijn parent en volgende items op, tot aan het hoogste niveau. Alleen dan loop ik vast dat ik niet dieper kom dan m'n eigen niveau. Plus dat ik dan eerst 1.3 terugkrijg voordat ik mezelf ertussen heb kunnen voegen

[Juup]

Hmmm je omschrijft het wel erg vaag. Je wil dus een tree in een lijst proppen. Vele voor jou hebben dat ook gewild, meestal om ze in een database te kunnen duwen. (Zie bv. http://searchoracle.techt...3,sid13_gci537290,00.html )
Wat je ook kan doen is aan elk item een referentie aan zijn parent meegeven. Dan zit de treedata uniek en niet-redundant in de list.

[riezebosch]

Dat idee ken ik, maar het niet m'n bedoeling het in een database te stoppen. In feite wil ik ook niet echt een lijst hebben. Ik wil vanaf een bepaald punt alle acties in de Tree uit kunnen voeren, maar daarbij ook alles wat er na die actie komt. En daarbij is het ook van belang dat alle bovenliggende dingen ook eerst uitgevoerd wordt. Maar dus niet de voorgaande

edit:

Een Tree omzetten naar een lijst is ook niet zo'n punt voor me. Alleen ga je dan normaliter uit van de root. Nu dus niet. Het probleem waar ik met name tegenaan loop is het skippen van voorgaande items.

[ Voor 24% gewijzigd door riezebosch op 19-05-2005 10:24 ]

[JaWi]

Naast de reactie van Jaaap, zou een oplossing kunnen zijn (efficient is anders, maar goed):

1. vanuit de huidige node een depth-search naar de root-node;
2. vanuit de huidige node een depth-search naar de laatste node;
3. voor elke node uit het resultaat van stap 2 een breath-first search;
4. de resultaat lijst opbouwen = resultaat stap 1 + oorspronkelijke node + resultaat stap 3.

[MrBucket]

Je hebt het idee al bijna. Je weet hoe je de hele tree als lijst af kan werken toch? Nl. recursief de children van elke node afgaan. Om je uitgangspunt te vinden kan je dit zelfde principe gebruiken: recursief alle childnodes verkennen totdat je je node gevonden hebt.

Omgekeerd is het makkelijker: Recursief alle nodes afgaan en ze allemaal rapporteren, tenzij je je target-node nog niet hebt gevonden, dan rapporteer je geen nodes.
Op het moment dat je je target-node vindt, moet je eerst het pad van je target naar de root rapporteren, en dan kan je weer verdergaan.

Pseudo-code wordt dan zoiets:

code:

bFound <- false

void Explore(Node n){
  if bFound = false and n = target{
    bFound <- true
    //Report path from root upto but not including n
  }
  if bFound = true{
    //Report n
  }
  for each child of n{
    Explore(n)
  }
}

[ Voor 28% gewijzigd door MrBucket op 19-05-2005 16:22 . Reden: Rapport -> Report :X ]

[riezebosch]

Heb nu zelf het idee om alle "leafs" een (dubbele) verwijzingte geven naar de volgende leaf. Op deze manier kan ik zeer eenvoudig de Tree gladstrijken tot een List. Alleen het toevoegen of tussenvoegen van nieuwe items wordt dan wat ingewikkeld.

[ Voor 13% gewijzigd door riezebosch op 19-05-2005 15:32 ]

[MrBucket]

Ehh, wat is er niet goed aan mijn idee, als ik vragen mag?

[Guldan]

Recursief is namelijk de ideale manier om een tree af te lopen. Het geeft je misschien qua programmeren een raar gevoel maar het is wel de snelste manier...

[riezebosch]

Sorry, wilde je niet negeren

Het gaat me dus niet om het zoeken van een bepaalde node, maar om het "langsgaan" van alle "volgende" nodes in de lijst. Niet alleen op het huidige niveau, maar ook alles wat volgt op het niveau van de parent, enz... Als 1.2.2 dus mijn node is, wil ik naast 1.2.3, 1.2.3.1 en 1.2.4 ook alles wat onder 1.3 hangt (zoals in het lijstje in de openingspost).

Je vraag beantwoord? Ik weet niet of ik jouw post helemaal begrijp, maar het leek me er met name om te gaan dat ik ermee een bepaalde node terug kon vinden. Mijn uitgangspunt is dus niet (per definitie) de root, maar een bepaalde node...

Guldan schreef op donderdag 19 mei 2005 @ 15:54:
Recursief is namelijk de ideale manier om een tree af te lopen. Het geeft je misschien qua programmeren een raar gevoel maar het is wel de snelste manier...

Ik weet wel wat recursief programmeren is hoor Alleen heeft recursiviteit meer zin als je van boven naar beneden wilt. Niet als je ergens halverwege erin springt.

[ Voor 28% gewijzigd door riezebosch op 19-05-2005 15:58 ]

[MrBucket]

riezebosch schreef op donderdag 19 mei 2005 @ 15:57:
Sorry, wilde je niet negeren

Je vraag beantwoord? Ik weet niet of ik jouw post helemaal begrijp, maar het leek me er met name om te gaan dat ik ermee een bepaalde node terug kon vinden. Mijn uitgangspunt is dus niet (per definitie) de root, maar een bepaalde node...

(...) Ik weet wel wat recursief programmeren is hoor Alleen heeft recursiviteit meer zin als je van boven naar beneden wilt. Niet als je ergens halverwege erin springt.

No problem. Maar mijn code doet volgens mij precies wat jij vraagt, nl. eerst het pad van de root naar jouw target-node rapporteren, en vanaf de target-node alle nodes volgende nodes rapporteren(met hogere "hoofdstuknummers").

Globaal werkt mijn code nl. als volgt: het loopt recursief alle nodes af, zodat de nodes in volgorde van opeenvolgende "hoofdstuknummers" behandeld worden. Dit is ook de volgorde waarin je de nodes wilt zien, maar dan beginnende vanaf jouw target node. Correct?
Oplossing: begin pas met nodes rapporteren (zeg maar: afdrukken) vanaf het moment dat je (tijdens die recursie) de target-node tegenkomt. Tot die tijd doe je niks met de nodes.
Maar: als je de target-node eenmaal tegenkomt wil je (voordat je vanaf daar alle volgende nodes rapporteert) ook alle parent nodes rapporteren. Dwz als je je target-node 1.2.2. tegenkomt, dan wil je eerst 1 en 1.2 rapporteren. Dit kan door vanaf je target-node de links terug te volgen naar de root.

Ik hoop dat dit makkelijker te volgen is? Zie ook mijn pseudo-code, trouwens

[Paul]

Dat is toch simpel?

Schrijf een boolean functie die bepaalt of je node boven of onder je "grens" ligt en werk recursief in volgorde je tree af waarbij je steeds test of je al voorbij je grens zit

Delphi:

function VoorbijGrens(Node, Grens: TNode):boolean;
begin
   // complete bool eval moet uitstaan, anders herschrijven
  result :=  (Node.Major > Grens.Major) or 
            ((Node.Major = Grens.Major) and (Node.Minor > Grens.Minor));
end;

procedure DoorloopTree(Root, Grens: TNode)
begin
  if not VoorbijGrens(Root, Grens) then
    begin
      Root.DoeActie;
      for i := 0 to Root.Items.Count - 1 do
        begin
          DoorloopTree(Root.Items[i], Grens);
        end;
    end;
end; 

[ Voor 16% gewijzigd door Paul op 19-05-2005 16:32 . Reden: Debug :P + scope Grens aangepast van global naar parameter + goede .Items gepakt ]

[riezebosch]

Maar dat wordt wel een zwaar proces dan, want voor elk child ga je opnieuw alle parents aflopen...

Hmmm... Ik zie sowieso nog niet hoe jouw code goed de grens bepaald? Of zit dat verborgen in de vergelijking van de TNodes (en gebruik je standaard functionaliteit van de TNodes)?

[ Voor 49% gewijzigd door riezebosch op 19-05-2005 16:31 ]

[Paul]

riezebosch schreef op donderdag 19 mei 2005 @ 16:29:
Maar dat wordt wel een zwaar proces dan, want voor elk child ga je opnieuw alle parents aflopen...

Mijn fout, Items moet een propertie van je TNode zijn

Hmmm... Ik zie sowieso nog niet hoe jouw code goed de grens bepaald? Of zit dat verborgen in de vergelijking van de TNodes (en gebruik je standaard functionaliteit van de TNodes)?

Bestaan er default TNode's? Ik schijf mijn bomen eigenlijk meestal vanaf de grond zelf

De .Items en de .DoeActie die ik gebruik is dus zwaar afhankelijk van je huidige klasse, dit is slechts een voorbeeld, zelfde met die Major en die Minor, ik heb geen idee hoe je de diepte opslaat of wilt vergelijken Deze versie kan zelfs maar 2 levels aan (de rootnode zelf even niet meegenomen)

[riezebosch]

Paul Nieuwkamp schreef op donderdag 19 mei 2005 @ 16:36:
[...]
De .Items en de .DoeActie die ik gebruik is dus zwaar afhankelijk van je huidige klasse, dit is slechts een voorbeeld, zelfde met die Major en die Minor, ik heb geen idee hoe je de diepte opslaat of wilt vergelijken Deze versie kan zelfs maar 2 levels aan (de rootnode zelf even niet meegenomen)

Dan was dat dus het probleem. Die van mij moet onbepaalde diepte hebben En dan ga je met zo'n vergelijking dus bij iedere stap alle parents tot aan de root opnieuw vergelijken...

[Paul]

riezebosch schreef op donderdag 19 mei 2005 @ 16:40:
[...]


Dan was dat dus het probleem. Die van mij moet onbepaalde diepte hebben

Euh, niets dat je in de weg staat om mijn code aan te passen hoor Als jij je DoeActie, je Items of je diepte-aanduiding anders geimplementeerd hebt zul je dat zelfs wel moeten
Overigens, onbepaald gaat je tot een bepaald niveau wel lukken, met een "oneindig" niveau loop je op gegeven moment tegen een stack overflow aan

En dan ga je met zo'n vergelijking dus bij iedere stap alle parents tot aan de root opnieuw vergelijken...

Dat is de 2e keer dat je dat zegt, maar de vorige keer dacht ik dat je het over de .Items had? Dus: waar zie je staan dat er voor ieder item opnieuw de hele tree doorlopen wordt? Er staat slechts 1 vergelijking in, die per item in je tree precies 1x wordt aangeroepen?
Edit: minder zelfs, zodra je de grens berijkt hebt stopt hij met doorlopen (alleen de items van de laatste branch worden nog doorlopen omdat i gewoon doorloopt ook als een vorige items[i] de grens was, maar dat valt volgens mij niet te stoppen zonder inefficienter te gaan werken. Iedere iteratie een keer extra testen kost iig meer cycles dan nog een paar keer na je grens testen, tenzij 90% van alle items aan 1 node hangen en je grens aan het begin van die node zit ).

[ Voor 22% gewijzigd door Paul op 19-05-2005 16:59 ]

[riezebosch]

De vergelijking voor de grens. De grens wordt bepaald vanaf de bepaalde Node tot aan al z'n parents. Maar als je dus uitgaat van de root, en alle childs die binnen het bereik (onder de grens) vallen langs wilt gaan (met DoeActie), zal telkens opnieuw de hele grens gecontroleerd (en opgebouwd) moeten worden.

Of je moet de grens opbouwen van de geselecteerde Node tot aan de root, en van daaruit weer teruggaan alle kinderen langs met als parameter het lijstje met de Nodes van de grens. Maar dat is ook vrij complex.

Op zich vind ik wat dat betreft mijn Tree die ook als List te benaderen is helemaal zo slecht nog niet. Alleen het tussenvoegen van nieuwe childs is een probleem omdat de references naar het volgende child geupdate moet worden.

[bigbeng]

Andere oplossing:
Je kunt bijvoorbeeld een lijst met beginpunten samenstellen voor die onderdelen in de boom waar je niet "bovenin" begint. Dit zijn er maximaal N, waarbij N de diepte van je boom is.

Vervolgens stap je door de Tree heen vanaf de root, waarbij je continu test tegen je lijst of je een node wel of niet wilt afhandelen. Zo kun je dus een lijst opbouwen. Overigens stapt dit ook op de in de TS gegeven volgorde door de boom heen, dus kun je overwegen om dit algorithme te gebruiken voor het uitvoeren van de acties, ipv het eerst in een lijst te plaatsen.

edit:
dit leunt er wel op dat je vanuit een gegeven treenode kunt bepalen dat deze onder of boven een andere treenode valt

edit:
edit2: iets duidelijker omschreven wat ik bedoelde

[ Voor 63% gewijzigd door bigbeng op 19-05-2005 17:08 ]

[Paul]

riezebosch schreef op donderdag 19 mei 2005 @ 16:56:
De vergelijking voor de grens. De grens wordt bepaald vanaf de bepaalde Node tot aan al z'n parents. Maar als je dus uitgaat van de root, en alle childs die binnen het bereik (onder de grens) vallen langs wilt gaan (met DoeActie), zal telkens opnieuw de hele grens gecontroleerd (en opgebouwd) moeten worden.

Of je moet de grens opbouwen van de geselecteerde Node tot aan de root, en van daaruit weer teruggaan alle kinderen langs met als parameter het lijstje met de Nodes van de grens. Maar dat is ook vrij complex..

Ik snap je echt niet?

Grens is een instantie van TNode die je gebruikt om de gewenste diepte aan te geven. Eenmaal geinstantieerd wordt deze niet meer veranderd (tenzij je de pointer naar een bestaande node opgeeft, maar goed, in mijn code wordt er aan Grens iig niets veranderd). Dit is dus 1 actie, die eenmalig uitgevoerd wordt.

Dan het doorlopen zelf. Ga van EEN root uit (en daar waar jij hem zelf aanroept in je OnClick of zo vul je daar dus DE root in, er vanuit gaande dat je alles vanaf het begin tot aan je grens wilt hebben). Vervolgens wordt er gecontroleerd of je al voorbij de grens bent (afhankelijk van je implementatie dus, maar in princiepe niet meer dan een "if getal1 < getal2".
Zit je nog voor de grens ga dan verder, anders doe niet (einde procedure).
Dat verdergaan bestaat uit het uitvoeren van de gewenste actie, gevolgd door het aflopen van alle nodes die aan je huidige node hangen. Dat aflopen is dus per node die aan je huidige node hangen deze alinea weer doorlopen.

Ik zie daar nergens het opbouwen of afbreken of meermaals doorlopen van je complete boom tussen staan?

Als ik er het lijstje van de topicstart bijpak en je wilt 1.2.3 als grens hebben dan doet hij dus het volgende

1: Ik zit nog niet voorbij de grens
1: DoeActie
1.1: Ik zit nog niet voorbij de grens
1.1 DoeActie
1.1.1: Ik zit nog niet voorbij de grens
1.1.1: DoeActie
1.1.2: Ik zit nog niet voorbij de grens
1.1.2: DoeActie
1.1.2.1: Ik zit nog niet voorbij de grens
1.1.2.1: DoeActie
1.1.3: Ik zit nog niet voorbij de grens
1.1.3: DoeActie
1.2: Ik zit nog niet voorbij de grens
1.2: DoeActie
1.2.1: Ik zit nog niet voorbij de grens
1.2.1: DoeActie
1.2.2: Ik zit nog niet voorbij de grens
1.2.2:DoeActie
1.2.3: Ik zit nog niet voorbij de grens
1.2.3:DoeActie
1.2.3.1: Ik zit voorbij de grens
1.2.4: Ik zit voorbij de grens
1.2.5: Ik zit voorbij de grens
1.2.6: Ik zit voorbij de grens
1.2.7: Ik zit voorbij de grens
1.3: Ik zit voorbij de grens
1.4: Ik zit voorbij de grens
1.5:: Ik zit voorbij de grens
2: Ik zit voorbij de grens
3: Ik zit voorbij de grens
4: Ik zit voorbij de grens

Ik zie nu dat het dus nog een klein beetje slimmer kan, maar het is dus echt niet zo dat voor ieder item opnieuw je hele boom doorlopen wordt?

Delphi:

public procedure DoorloopTotGrens(Grens: TNode)
begin
  if not IsVoorbijGrens(TreeRootNode, Grens) then
    DoorloopTree(TreeRootNode, Grens);
end;

private function IsVoorbijGrens(Node, Grens: TNode):boolean;
begin
   // complete bool eval moet uitstaan, anders herschrijven
  result :=  (Node.Major > Grens.Major) or 
            ((Node.Major = Grens.Major) and (Node.Minor > Grens.Minor));
end;

private procedure DoorloopTree(Root, Grens: TNode)
var i: integer;
begin
  Root.DoeActie;
  i := 0;
  while (i < Root.Items.Count) and (not IsVoorbijGrens(Root.Items[i], Grens) do
    begin
        DoorloopTree(Root.Items[i], Grens);
        inc(i);
    end;
end;

Delphi kent geen private en public statements op die positie, maar om hier de hele klasse uit te schrijven gaat me net te ver Je snapt ze wel denk ik

bigbeng schreef op donderdag 19 mei 2005 @ 16:57:

edit:
dit leunt er wel op dat je vanuit een gegeven treenode kunt bepalen dat deze onder of boven een andere treenode valt

Dat doe ik ook, dat is mijn IsVoorbijGrens()

[ Voor 5% gewijzigd door Paul op 19-05-2005 17:19 ]

[Verwijderd]

Misschien lees ik over dit alles grandioos over, maar over welke taal heb je het?

VB6
VB.Net

Stel dat het .Net is. Dan kun je toch heel makkelijk een foreach schrijven?

[alienfruit]

Het lijkt gezien de code op Delphi.

[Paul]

_mijn_ code is wel Delphi, maar de topicstarter heeft nog geen code geplaatst

[Verwijderd]

Kun je de leaf niet op twee manieren linken.
- in de vorm van een list met een pointer naar de volgende
- in de vorm van een tree met een verwijzing naar de parent.

Dus iets van

code:

item1  Parent=null, Next=item1.1
  |--- Item1.1 Parent=item1, Next=Item1.2
  |--- Item1.2 Parent=item1, Next=Item1.2.1
  |       |-- Item1.2.1 Parent= Item1.2 Next =Item1.3
  |-- Item 1.3 Parent=Item1 Next=Item1.3.1
  |       |-- Item1.3.1 Parent= Item1.2 Next =Item1.3.2
  |       |-- [b]Item1.3.2 Parent= Item1.3 Next =Item1.3.3[/b]
  |       |-- Item1.3.2 Parent= Item1.3 Next =Item1.4
  |-- Item 1.4 Parent=Item1 Next=null

Bij item 1.3.2 weet je eenvoudig de parents terug te vinden door de Parent lijst terug te lopen en de resterende items door de next lijst verder af te gaan
Tussenvoegen van een record is niet zo heel groot probleem. Je moet toch al weten wat de parent is en bijhouden in welke volgorde leafs op een bepaald niveau staan. Feitelijk link je die lijst gewoon door over de leafs heen.

Toevoegen werkt dan ongeveer als volgt:

Delphi:

function zoekvolgende(item Tobject):TObject;

begin
  result:=item.Next;
end;

procedure voegtoeaanparent(Parent TObject,NieuwObject:TObject);

var
  voorgaand,
  volgende: TObject;
begin 
  volgende:=null;
  voorgaand:=Parent;
  repeat 
    if (volgende<>null) then voorgaand:=volgende;
    volgende=zoekvolgende(voorgaand);
  until volgende.Parent<>Parent or volgende=null;
  NieuwObject.Parent:=Parent;
  NieuwObject.Next:= volgende;
  voorgaand.Next:=NieuwObject;
end;

[ Voor 26% gewijzigd door Verwijderd op 20-05-2005 01:18 ]

[riezebosch]

Paul Nieuwkamp schreef op donderdag 19 mei 2005 @ 17:18:
[...]
Ik snap je echt niet?

Grens is een instantie van TNode die je gebruikt om de gewenste diepte aan te geven. Eenmaal geinstantieerd wordt deze niet meer veranderd (tenzij je de pointer naar een bestaande node opgeeft, maar goed, in mijn code wordt er aan Grens iig niets veranderd). Dit is dus 1 actie, die eenmalig uitgevoerd wordt.

Dan het doorlopen zelf. Ga van EEN root uit (en daar waar jij hem zelf aanroept in je OnClick of zo vul je daar dus DE root in, er vanuit gaande dat je alles vanaf het begin tot aan je grens wilt hebben). Vervolgens wordt er gecontroleerd of je al voorbij de grens bent (afhankelijk van je implementatie dus, maar in princiepe niet meer dan een "if getal1 < getal2".
Zit je nog voor de grens ga dan verder, anders doe niet (einde procedure).
Dat verdergaan bestaat uit het uitvoeren van de gewenste actie, gevolgd door het aflopen van alle nodes die aan je huidige node hangen. Dat aflopen is dus per node die aan je huidige node hangen deze alinea weer doorlopen.

Ik zie daar nergens het opbouwen of afbreken of meermaals doorlopen van je complete boom tussen staan?

Als ik er het lijstje van de topicstart bijpak en je wilt 1.2.3 als grens hebben dan doet hij dus het volgende

1: Ik zit nog niet voorbij de grens
1: DoeActie
1.1: Ik zit nog niet voorbij de grens
1.1 DoeActie
1.1.1: Ik zit nog niet voorbij de grens
1.1.1: DoeActie
1.1.2: Ik zit nog niet voorbij de grens
1.1.2: DoeActie
1.1.2.1: Ik zit nog niet voorbij de grens
1.1.2.1: DoeActie
1.1.3: Ik zit nog niet voorbij de grens
1.1.3: DoeActie
1.2: Ik zit nog niet voorbij de grens
1.2: DoeActie
1.2.1: Ik zit nog niet voorbij de grens
1.2.1: DoeActie
1.2.2: Ik zit nog niet voorbij de grens
1.2.2:DoeActie
1.2.3: Ik zit nog niet voorbij de grens
1.2.3:DoeActie
1.2.3.1: Ik zit voorbij de grens
1.2.4: Ik zit voorbij de grens
1.2.5: Ik zit voorbij de grens
1.2.6: Ik zit voorbij de grens
1.2.7: Ik zit voorbij de grens
1.3: Ik zit voorbij de grens
1.4: Ik zit voorbij de grens
1.5:: Ik zit voorbij de grens
2: Ik zit voorbij de grens
3: Ik zit voorbij de grens
4: Ik zit voorbij de grens

1.1.1 moet dus juist niet uitgevoerd worden Moet juist het omgekeerde hebben.

Verwijderd schreef op donderdag 19 mei 2005 @ 17:26:
Misschien lees ik over dit alles grandioos over, maar over welke taal heb je het?

VB6
VB.Net

Stel dat het .Net is. Dan kun je toch heel makkelijk een foreach schrijven?

Taal is juist totaal onbelangrijk Of je nou een foreach of een for schrijft...

Verwijderd schreef op vrijdag 20 mei 2005 @ 00:59:
Kun je de leaf niet op twee manieren linken.
- in de vorm van een list met een pointer naar de volgende
- in de vorm van een tree met een verwijzing naar de parent.

Dus iets van

code:

item1  Parent=null, Next=item1.1
  |--- Item1.1 Parent=item1, Next=Item1.2
  |--- Item1.2 Parent=item1, Next=Item1.2.1
  |       |-- Item1.2.1 Parent= Item1.2 Next =Item1.3
  |-- Item 1.3 Parent=Item1 Next=Item1.3.1
  |       |-- Item1.3.1 Parent= Item1.2 Next =Item1.3.2
  |       |-- [b]Item1.3.2 Parent= Item1.3 Next =Item1.3.3[/b]
  |       |-- Item1.3.2 Parent= Item1.3 Next =Item1.4
  |-- Item 1.4 Parent=Item1 Next=null

Bij item 1.3.2 weet je eenvoudig de parents terug te vinden door de Parent lijst terug te lopen en de resterende items door de next lijst verder af te gaan
Tussenvoegen van een record is niet zo heel groot probleem. Je moet toch al weten wat de parent is en bijhouden in welke volgorde leafs op een bepaald niveau staan. Feitelijk link je die lijst gewoon door over de leafs heen.

Toevoegen werkt dan ongeveer als volgt:

Delphi:

function zoekvolgende(item Tobject):TObject;

begin
  result:=item.Next;
end;

procedure voegtoeaanparent(Parent TObject,NieuwObject:TObject);

var
  voorgaand,
  volgende: TObject;
begin 
  volgende:=null;
  voorgaand:=Parent;
  repeat 
    if (volgende<>null) then voorgaand:=volgende;
    volgende=zoekvolgende(voorgaand);
  until volgende.Parent<>Parent or volgende=null;
  NieuwObject.Parent:=Parent;
  NieuwObject.Next:= volgende;
  voorgaand.Next:=NieuwObject;
end;

Zie m'n plaatje, dat is dus ook precies mijn idee

[ Voor 4% gewijzigd door riezebosch op 20-05-2005 08:59 ]

[Glimi]

Kun je iets duidelijker zijn over de datastructuur waar je het over hebt? Als het echt een tree is, waarom heb je daar eigenlijk voor gekozen? Wil je er snel in kunnen zoeken, of moet het toevoegen juist snel gaan?

Ik ga nu even uit van een tree waarbij de childeren pointers hebben naar de parents en de parents naar de children, zodat je twee kanten uit kunt lopen.
De snelste manier om dan van de root naar het centrale punt van de lijst te komen (item 1.2.3 in je voorbeeld) is dmv een zoekactie. Je begint bij de root en je weet onder welk child de Node zou moeten zitten, dus vervolg je de weg volgens die node. Elke node die je vervolgens visit voordat je bij het centrale punt bent, sla je op in de lijst.
Als je dan het centrale punt bereikt ga je verder in een preorder traversel, waarbij elke Node wordt toegevoegd.
Het zou makkelijker en sneller gaan als je een verwijzing had naar het laatste punt. Dan is het gewoon een kwestie van teruglopen in de boom.

[Paul]

riezebosch schreef op vrijdag 20 mei 2005 @ 08:57:
[...]


1.1.1 moet dus juist niet uitgevoerd worden Moet juist het omgekeerde hebben.

Dat idee ken ik, maar het niet m'n bedoeling het in een database te stoppen. In feite wil ik ook niet echt een lijst hebben. Ik wil vanaf een bepaald punt alle acties in de Tree uit kunnen voeren, maar daarbij ook alles wat er na die actie komt. En daarbij is het ook van belang dat alle bovenliggende dingen ook eerst uitgevoerd wordt. Maar dus niet de voorgaande

Die heb ik een beetje over het hoofd gezien geloof ik... Euh, hoe wil je wel de bovenliggende, maar niet de voorgaande items uitvoeren? Alles wat boven je zit in de tree (mits je root bovenaan zit) is toch voorgaand?

Je wilt vanaf een bepaald punt eerst alle parents van dat punt uitgevoerd zien (maar weer niet alle children van die parents), en vervolgens de rest van de tree?

Ik denk dat dan het simpelste is om inderdaad naast de tree-info een linked list te hebben waar je tree in volgorde instaat, en in iedere node de variabele "parent" te hebben.
Het bijhouden van de linked list is dan nog het (relatief ) lastigste, de lijst doorloop je met:

Delphi:

procedure TTree.DoorloopTree(Grens: TNode);
var CurrentNode: TNode;
begin
  Grens.ParentsDoeActie;

  CurrentNode := Grens;
  while Assigned(CurrentNode.Volgende) do
    begin
      CurrentNode := CurrentNode.Volgende;
      CurrentNode.DoeActie;
    end;
end;

procedure TNode.ParentsDoeActie;
begin
  if Assigned(Parent) then
    Parent.ParentsDoeActie;
  DoeActie;
end;

[ Voor 5% gewijzigd door Paul op 20-05-2005 09:39 ]

[riezebosch]

Glimi schreef op vrijdag 20 mei 2005 @ 09:31:
Kun je iets duidelijker zijn over de datastructuur waar je het over hebt? Als het echt een tree is, waarom heb je daar eigenlijk voor gekozen? Wil je er snel in kunnen zoeken, of moet het toevoegen juist snel gaan?

Ik ga nu even uit van een tree waarbij de childeren pointers hebben naar de parents en de parents naar de children, zodat je twee kanten uit kunt lopen.
De snelste manier om dan van de root naar het centrale punt van de lijst te komen (item 1.2.3 in je voorbeeld) is dmv een zoekactie. Je begint bij de root en je weet onder welk child de Node zou moeten zitten, dus vervolg je de weg volgens die node. Elke node die je vervolgens visit voordat je bij het centrale punt bent, sla je op in de lijst.
Als je dan het centrale punt bereikt ga je verder in een preorder traversel, waarbij elke Node wordt toegevoegd.
Het zou makkelijker en sneller gaan als je een verwijzing had naar het laatste punt. Dan is het gewoon een kwestie van teruglopen in de boom.

Ben bezig met een soort macrotool. Hierin maak ik (onder andere) onderscheidt tussen een Window welke ik bij het afspelen weer kan identificeren, en de keyboard-acties die op dit Window zijn uitgevoerd. Een Window kan meerdere (child-) Windows bevatten. En voor iedere keyboard-actie is ook bekend op welk control die uitgevoerd moet worden, adhv relatieve coördinaten tov zijn Window. Een groepje controls hoort dus echt bij een bepaald Window. Maar als de gebruiker ergens halverwege de keyboard-acties van een Window de test wil starten, moet ook eerst het bijbehorende Window geïdentificeerd worden. En daarna wil ik niet alleen de keyboard-acties van dat Window uitvoeren, maar ook wat er verder nog allemaal in dat script staat.

Vandaar dat ik de elementen standaard in een Tree gegoten heb (ze moeten soms ook acties van hun parent eerst uitvoeren), maar voor de totale uitvoering graag weer op een List manier wil werken. Het is nog iets uitgebreider, want ik heb ook gemaakt dat je meerdere Scripts in een Set kan onderbrengen, en Sets ook weer uit meerdere Sets laten bestaan (genest). Ook hierbij wil ik graag dat wanneer op een bepaald punt gestart wordt, ook alle Scripts die "volgen" ook uitgevoerd worden. Zodat je niet, wanneer je op een bepaald niveau de test gestart hebt, telkens opnieuw moet starten als je de rest ook uit wilt voeren.

Duidelijk zo?

[riezebosch]

Ok, een klein kickje voor degenen die meegedacht hebben:

Na lang denken ben ik nu toch op een nog eenvoudiger oplossing uitgekomen:

C#:

public class Tree
{
    Tree next, prev;
    ArrayList list;

    public Tree Next { get { return next; } }
    public Tree Prev { get { return prev; } }

    public void Insert(int Index, Tree t)
    {
        list.Insert(Index, l);

        l.parent = this;

        if (Index > 0)
        {
            l.prev = (TreeList) list[Index -1];
            l.prev.next = l;
        }

        if (Index < list.Count -1)
        {
            l.next = (TreeList) list[Index +1];
            l.next.prev = l;
        }
    }
}

C#:

public class Item : Tree
{
    public string name;

    public void Play()
    {
        Console.WriteLine(name);

        if (List.Count > 0)
            ((Item) List[0]).Play();
        else
            PlayNext();
    }

    public void PlayNext()
    {
        if (Next != null)
            ((Item) Next).Play();
        else if (Parent != null)
            ((Item) Parent).PlayNext();
    }
}

Op deze manier is het mogelijk iteratief door de boom te wandelen, en ook ergens halverwege te starten. Om alle parents uit te voeren voordat een item uitgevoerd wordt, is niet persé (meer) noodzakelijk, daar ik ga voorzien in functies in de parent die een child kan aanroepen als hij extra informatie nodig heeft (met daarbij een bij het starten van een test gegenereerde PlayId, zodat een parent voor meerdere childs niet iedere keer opieuw een actie hoeft te doen maar direct een waarde kan returnen).

In ieder geval bedankt allen