@CStoll: Hilfe von deiner Kompetenz (Dynamischer Datenstruktur Baum)

CStoll

BorisDieKlinge schrieb:

ok.. und wies sieht der Konstruktor des Iterators aus?

Ich würde mal vermuten, daß du erst einmal den Knoten in in der Nachfolgeliste seines Vaters suchen mußt, um deinen Ansatzpunkt zu finden. (oder du initialisierst den Baum-Iterator direkt mit einem list<node>::iterator)

wenn ich den Operator ++ audführe springt er erst mal zum letzen (linkesten) Blatt des baumes richtig? und das ist der erste Travesions Wert?

Nein, er springt zum nächst"jüngeren" Bruder des aktuellen Knoten und überprüft dabei, ob dieser existiert (wenn du bei father->children.end() angekommen bist, gab es keinen jüngeren Bruder). Wenn nicht, arbeitet er sich durch zum Cousin.

In deinem Beispiel werden so nur die Blätter travesiert?

Ja. Aber wenn du unbedingt alle Knoten traversieren willst, kannst du das entsprechend anpassen - bei prä-order (erst der Vater, danach alle seine Kinder) lässt du den Abschnitt "nach unten" weg und setzt ein if(!pos->children.empty()){pos=pos->children.begin();return *this;} an den Anfang des op++; für post-order (erst die Kinder und zuletzt der Vater) brauchst du statt des Durchhangelns zum Cousin nur rauf zum Vater zu gehen und führst die Schritte 2 und 3 am Anfang des op++ aus.

BorisDieKlinge

bin immer mehr verwirrt.. du sagst es werden nur die Blätter iteriert (was für mich auch erstmal reicht) aber dann sagst du das er bei der ersten iterationen NICHT zum untersten ,linkesten Blatt springt.. Wiederspruch

und der father iterator variable im Knoten ist quasie die Postion den Knotens welche im Vaterknoten gesetzt ist?

Konstruktor :

baum_iterator(node *p) {

		//Vaterknoten Iterator mit Zeiger des Kindknotens verlgeichen und setzen
		for(p->father = p->children.begin(); p->father != p ; p->father++);
	}

CStoll

Ich fürchte, jetzt hast du es auch geschafft, mich endgültig zu verwirren

Also nochmal langsam:

Wenn du das erste Blatt im Baum als Startpunkt der Iteration verwenden willst, mußt du von der Wurzel bis ganz nach unten durchlaufen.

Wenn du von irgendeinem Blatt zum Nachfolger gehen willst (das macht der op++), kannst du als erstes nachsehen, ob es einen Bruder hat:

pos_type father=pos->father;
//'father' ist ein Listen-Iterator, der auf den Vater des aktuellen Knotens zeigt
++pos;
if(pos!=father->children.end()
  return *this;

Wenn das nicht geht, mußt du den Umweg gehen:

//nach oben bis zu einem Onkel
do
{
  pos=father;
  father=pos->father;
  ++pos;
  if(is_root(pos) return *this;
}
while(pos==father->children.end());

//nach unten bis zum Blatt
while(!pos->children.empty())
  pos=pos->children.begin();

return *this;

Da mußt du nur noch erkennen, wenn du die Wurzel erreicht hast (dort oben die Funktion is_root()).

BorisDieKlinge

ok gut.. aber der Konstruktor des iterator.. was wird da intialisiert? wenn ich jetzt nicht bei der wurzel beginne zu iterieren.. dann muss da doch sicher was geamcht werden?

CStoll

Was genau übergibst du diesem Ctor? (und von wo aus wird der aufgerufen?)

-> Wenn du ihn verwenden willst, um den begin()-Iterator deines Baums zu besorgen, mußt du dort auch den Weg "nach unten bis zum Blatt" gehen.

-> Wenn du einen Iterator direkt auf den übergebenen (Blatt)Knoten erzeugen willst, mußt du in p->father.children nach dem übergebenen Knoten suchen.

BorisDieKlinge

und wie wird dann "pos" intialisiert!

naja ich will quasie im C-Tor

iterator(node *pCurNode)......

den Start Knoten übergben.. war da mein Konstruktor im 2t letzen post ok?

CStoll

Also pCurNode ist das Blatt, bei dem du mit dem Travarsieren beginnen willst?

pos=find(pCurNode->father->children.begin(),pCurNode->father->children.end(),pCurNode);

BorisDieKlinge

pCurNode kann auch ein Ast sein....

CStoll

Wenn du irgendwo im Baum bist, mußt du nach unten bis zum ersten Blatt des aktuellen Knoten:

if(pCurNode->children.empty())
  //Startpunkt ist Blattknoten
  pos=find(pCurNode->father->children.begin(),pCurNode->father->children.end(),pCurNode);
else
{
  //Wurzel bzw. mitten im Baum
  pos=pCurNode->children.begin();
  while(!pos->children.empty())
    pos=pos->children.begin();
}

BorisDieKlinge

ich gebs auf.. ich war jetzt 3-4 tage damit beschäftig.. bekomm das nich auf die reihe...

@CStoll: wenn du mir keine funktionieren Code postest.. wird das glaub nix mehr...

NERV