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

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?

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