@CStoll: Baumstruktur als Level-Down Liste

BorisDieKlinge

Hallo CStoll,

wie bisher schon mitbekommen hast weist ja um was geht, um meine dämliche Baumstruktur;)
Da hast du in einem meiner andere thread erwähnt das du die Knoten des Baumen im Level-Down format aufbauen würdest. Nun ist die frage wie ich das organisiere?? beim knoten anfügen löschen etc. Bei meiner Prinzip das ganze etwas einfacher zu gestalten, aber bei deiner tu ich mir schwer...

Grüße

CStoll

Ich sagt nicht "Level-down", sondern Level-Order (sprich: erst die Wurzel, danach alle Kinder der Wurzel, dann die Enkel etc). Der Trick dabei besteht darin, daß die Kinder eines gegebenen Knotens hintereinander in der Verwaltungsliste untergebracht sind - da brauchst du nur zwei list<node>::iterator'en, die den betroffenen Bereich eingrenzen:

struct node
{
  list<node>::iterator father,sons_begin,sons_end;
  ...

  void insert_son(node s);
};

list<node> treedata;

void node::insert_son(node s)
{
  s.father=/*ermittle Iterator auf *this*/
  treedata.insert(sons_end,s);
}

(beim Löschen müsstest du eventuell darauf aufpassen, die Wirkungsbereiche der betroffenen Vater-Knoten anzupassen)

BorisDieKlinge

ich dachte so in der art:

Baum:
------- root ---------
-----/----|----\------
----A-----B----C------
--/--\----|---/-|-\---
-A1--A2--B1-C1-C2-C3--

Liste:

root,A,B,C,A1,A2,B1,C1,C2,C3

oder?

CStoll

Ja, das sieht gut aus - und jetzt kann z.B. der Knoten C die Iteratoren auf C1 und treedata.end() aufheben und hat den Bereich seiner Kinder.

BorisDieKlinge

nehmen wir an die liste sieht anfangst so aus

root,A,B,C

wohin zeigen und son_beginm udn son_end von A,B,C??

wenn die liste nun so aussiehst?

root,A,B,C,B1

wohin zeigen und son_beginm udn son_end von A,C??

CStoll

BorisDieKlinge schrieb:

nehmen wir an die liste sieht anfangst so aus

root,A,B,C

wohin zeigen und son_beginm udn son_end von A,B,C??

außer bei root (sb==A, se==end()) alle auf end().

wenn die liste nun so aussiehst?
root,A,B,C,B1

root:A und B1
A: B1 und B1
B: B1 und end()
C: end() und end()

(sons_begin zeigt auf die erste Position der Liste, wo ein Kind reinpassen könnte, sons_end auf die letzte entsprechende Position - bei Blättern gilt sons_begin==sons_end)

BorisDieKlinge

ok gut verstanden danke;)... ist ne feine sache mit Iteratoren bei listen..

nun welceh vorteile bittet dein Anordung der knoten gegenüber meiner, ausser das alle kinder-Knoten in einer ebene sind??
grüße

CStoll

BorisDieKlinge schrieb:

ausser das alle kinder-Knoten in einer ebene sind??

Die Kindknoten sind per Definition in einer Ebene

Der Vorteil ist, daß alle Kinder am Block in der list<> stehen. Das bedeutet, daß der Knoten sich nicht merken muß, wo sein Bruder steckt - der Bruder ist (wenn er existiert) IMMER der Nachfolger in der Liste.