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

BorisDieKlinge

Hallo CStoll,

wie du schon in einiger meiner anderen threads Hilfe geleistet hast,

hast du mir den tipp gegenen bein dynamischer Baum mit hilfe
der std::list umzusetzen, und diesen dann zu iterieren.

Dein Hilfe- Code war:

class node 
{ 
  list<node> children; 
  list<node>::iterator father; 
  ... 
}; 

class baum_iterator 
{ 
  typedef list<node>::iterator pos_type; 
  pos_type pos; 
public: 
  baum_iterator& operator++() 
  { 
    post_type father = pos->father; 
    ++pos; 
    if(pos==father->children.end()) 
      durchhangeln zum nächsten Cousin 
    return *this; 
  } 
};

Nun bin ich da stunden dran gesessen dies hinzukriegen, aber mein Horizont hats nich geschafft.. meinst du könntest mit das mal näche erleutern bzw, implementiere damit ich mal weiter komme:

Danke

CStoll

Woran hängt es denn? An dem Teil "durchhangeln bis zum nächsten Cousin"?

Wenn ja: Du mußt so lange den father-"Zeigern" folgen, bis du zu einem Vorfahren kommst, der nicht am Ende der entsprechenden Liste steht (der Test verläuft analog zu dem obigen). Dann wechselst du zu dessen jüngeren Bruder und gehst so lange über pos->children.begin() nach unten, bis du bei einem Blattknoten ankommst (Blattknoten haben keine Kinder, also gilt pos->children.empty()).

BorisDieKlinge

die ganze denk geschichte mit den vater iterator etc. und das durchhängel zum cousin versteh ich auch nich wie ich das machen soll...

Wer nett wenn du da mir noch bischen Code geben könnest, damit ich es vll. dann verstehe...

Wie du selbst weis ist es hier im forum schwer zu erklären wo genau meine probleme liegen.. nich in worten zu fassen:)

BorisDieKlinge

ich verzweifel....

CStoll

Die Details müsstest du vermutlich nochmal in der Praxis anpassen, aber hier eine Prinziplösung:

//nach oben:
pos_type father,brother;
while(brother!=father->children.end())
{
  brother=pos=father;
  ++brother;
  father=pos->father;
}
//seitwärts zum Großonkel
pos=brother;
//abwärts bis nur Wurzel edit: natürlich zum Blatt
while(!pos->children.empty())
  pos=pos->children.begin();

BorisDieKlinge

der fahter iterator, ist quasie immer die position des Knoten vom Vater Knoten aus?

oder

einfach ein Zeiger auf den Vater?

CStoll

Fast - 'father' ist ein Iterator auf den Vaterknoten, zeigt also auf dessen Position in der Kinderliste des Großvaters. Für die Wurzel brauchst du da womöglich eine Sonderbehandlung.

CStoll schrieb:

Für die Wurzel brauchst du da womöglich eine Sonderbehandlung.

Eventuell sollte man noch eine Paradontose Prophylaxe in Erwägung ziehen.

MfG
Dr. Best Plus Plus

Dr. Best Plus Plus schrieb:

CStoll schrieb:

Für die Wurzel brauchst du da womöglich eine Sonderbehandlung.

Eventuell sollte man noch eine Paradontose Prophylaxe in Erwägung ziehen.

MfG
Dr. Best Plus Plus

Dr. Best Plus Plus schrieb:

CStoll schrieb:

Für die Wurzel brauchst du da womöglich eine Sonderbehandlung.

Eventuell sollte man noch eine Paradontose Prophylaxe in Erwägung ziehen.

MfG
Dr. Best Plus Plus

BorisDieKlinge

oh man.. ich bekomms net hin... so ein scheiss

CStoll

Dann zeig doch mal, was du hast und an welcher Stelle du nicht weiterkommst.

@Dr. Best: Danke für deine Versuche, die Situation aufzulockern Aber wenn du nichts vom Thema verstehst, halt dich besser da raus.

BorisDieKlinge

Hallo CStoll.. ich kommt mit der ganzen Logig vator ,bruder, pos der iteratornen nicht klar... das ganze ding hab ich schon überpointer gecoded.. aber ich denke mit listen ist das ganze schneller und sichere.. und übersichtlicher..

das hab ich biser großteil von dir übernommen:

class node 
{ 
public: 
	std::list<node> children; 
	std::list<node>::iterator father; 
	int i;

	node(int k) : i(k){}
}; 

class baum_iterator 
{ 
	typedef std::list<node>::iterator pos_type; 
	pos_type pos,brother; 
public: 

	baum_iterator(node *p) :pos(p->father->children.begin()){

		brother= ++p->father;

		p->father= p->children.begin();
	} 
  baum_iterator& operator++(){ 

	  //Iterator von father
 /*   post_type father = pos->father; 
    ++pos; */
   /* if(pos==father->children.end()) 
      durchhangeln zum nächsten Cousin */
	pos_type father,brother; 

	//abwärts bis nur Wurzel edit: natürlich zum Blatt 
	if(!pos->children.empty()){
		pos=pos->children.begin();
		return;
	}
	else if(pos->father != 

	//seitwärts zum Großonkel 
	pos=brother; 

	//nach oben: 

	while(brother==father->children.end()) { 
		brother=pos->father; 
		++brother; 
		father=pos->father; 
	} 

    return *this; 
  } 
}; 
class Base{

public:
	node oRoot;

	Base() : oRoot(0){}

};

Die Klasse Base enthät beim erzeugen die Wurzel.. soweit bin ich.. die ganze Sose mit der travsieren des Baumes bekomm ich einfach nicht hin..

Ich wäre dir ewig dankbar wenn du mit eine funktionierende einfache version posten könntes wo das iterieren funktioniert.. Ich komm sonst nie weiter... und die Pointer version ist mir nicht so geheuert..

Danke und Grüße @ CStoll:)

CStoll

*grübelt*
Was genau sollen die Initialisierungen im Ctor bewirken? Du setzt pos auf den ältesten Bruder des übergebenen Knoten und brother auf seinen Onkel - und dann zerstörst du die Baumstruktur, indem du den Vater des übergebenen Knoten neu setzt.

Und die Reihenfolge während der Arbeit passt auch nicht so richtig - du mußt erst nach oben und dann nach unten zum nächstfolgenden Blatt.
*sehr lange nachdenkt*
Also irgendwie habe ich inzwischen das Gefühl, daß die STL da am Ende angekommen ist. Wenn du mit deiner zeigerbasierten Baumstruktur besser zurechkommst, solltest du vielleicht die verwenden.

BorisDieKlinge

die durchhänglerei auf Zeiger Basis is mir klar.... aber das ganze mit iteratoren umzusetzen hab ich schwierigkeit.. wenn du mir ne lösung geben könnten (was für dich kein son aufwandt sein drüfte oder?), würd ich das mit den iteratoren verstehen können...

die initialisierugnen im C-tor waren nur spielrei.. hab bei dieser implementation grad voll die blockade...

CStoll

Wie gesagt, die Reihenfolge ist wichtig: du befindest dich ganz unten im Baum am Ende einer Nachfolger-Liste - da ist der Nachfolger der "(Groß)Cousin" des aktuellen Knotens. Und um da hin zu gelangen, mußt du:

dich entlang der father-Iteratoren nach oben hangeln bis zum ersten Knoten, der noch einen jüngeren Bruder hat
einen Schritt weiter gehen zu diesem jüngeren Bruder
entlang der children.begin()-Iteratoren nach unten durchhangeln bis du bei einem Blatt angekommen bist

(du hast die Schritte 1 und 3 vertauscht und den Trivialfall auskommentiert)

BorisDieKlinge

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

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

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

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?