3. Eigener Iterator für Baumstruktur?

Eigener Iterator für Baumstruktur?

  • B

    hab eine Klasse Node welche wieder Node enthähkt und diese Wiederrum.

    Die letzten Knoten (Blätter) des willkürlichen strukturierten Baumes solle nacheinadner travestiert werden, und dies möchte ich gerne als eigener Iterator umsetzen.. geht sowas? Hat jemand gute Ansätze?

    0
  • R

    es gibt verschiedene möglichkeiten

    du kannst dich z.B. von ast zu ast hangeln oder stacks aufbauen

    0
  • B

    kannst du mir das näch erleutern?

    ich habe mir überlegt beim erzeugen des iterator Objekts der baumstrukturklasse den baum rekursiv durchkaufen und temporär die refernez der blätter des baumes zu speichern... und so travestrien?

    Ich muss ja praktitsch den baum erst durchlaufen kann mir ja kein zustand im rekusiven zustand merken

    0
  • R

    du kannst grundsätzlich von einem blatt zum nächsten auf der selben ebene wandern

    du kannst grundsätzlich bein letzten element einer ebene zum übergeordneten wandern, und du kannst bei jedem element auf eines der unterelemente wandern

    *edit*

    das bedeutet - deine position ist dein zustand

    0
  • B

    hmm aber wenn ich nun meinen itereator wie den iterator des std::Vector verwendet will in ein for -schleife, dann muss ich ja jedes mal zu dem vorigen zsutanden der rekursion zurückspringen.. oder meinst du den zsutand als referenz merken?? stimmt eigenlich

    0
  • C

    Wie ronny schon sagte - der einzige "Zustand", den du brauchst, ist deine Position im Baum (und die Verzweigungen, die vom aktuellen Knoten ausgehen). Wenn der aktuelle Knoten einen rechten Bruder hat, springst du zu dem, andernfalls so weit wie nötig den Baum nach oben, zum rechten "Onkel" und wieder bis ganz nach unten.

    0
  • B

    Dazu brauchst du Rückwärtsverkettungen. Das ist nicht ganz selbstverständlich, dass man sowas hat. Für eine passive Iteratorabstraktion wie in der STL braucht man halt irgendeine Form von Overhead, man kann sich aussuchen, ob man die im Baum unterbringt oder in den Iteratoren, aber ohne gehts nicht.

    0
  • B

    da ich ja nur die untersten knoten de Baumes also die blätter iterieren möchste, ist es dann nich elegant wenn ich erst den baum auf alle blätter scane, und mir die referenzen der blätter wie sie nacheinader gescannt werden merke, und die elemten über die temporäre list iteriere?

    0
  • C

    Wer sagt denn, daß du das mußt:

    class node
{
  node* first_son,father,brother;
  ...
}

node* next_node(node* pos)
{
  if(pos->brother!=NULL)return pos->brother;

  while(pos->brother==NULL) pos=pos->father;    //Baum hochklettern
  pos=pos->brother;                             //Übergang zum (Groß)Onkel
  while(pos->first_son!=NULL) pos=pos->fist_son;//Baum wieder runterklettern
  return pos;
}

    (das kommt raus, wenn man meine Erklärungen von oben in Programmcode umsetzt 😉 Fehlerkontrollen etc überlasse ich dir als Übung)

    0
  • B

    d.h. ich bruache keine vector oder list? nur über pointer

    0

  • ja, nur über pointer. alles andere wäre auch wohl ziemlich langsam.
    du willst ja wohl nicht für jeden iterator gleich dynamisch speicher anfordern, oder?
    ich meine es ist schon schön wenn man iteratoren kopieren kann ohne sich gleich gedanken machen zu müssen dass ein bad_alloc rausfliegt könnte etc. ...
    (abgesehen davon dass es eben auch schrecklich langsam wäre)

    0
  • B

    ne ich meine, die knoten de baumes haben ja mehrer unterknoten, und die unterknoten sind ja als list/vector in den entsprechenden knoten angelegt.

    Die anzahl der unterknoten (Kinder) eine Vater knoten ist variabel, wobei ein knoten und ein nur ein Vater haben kann (kein GRapph) wie soll das mit pointer dan ngehen!

    Sorry Jungs.. aber ich steh immer noch aufm schlauch... komm grad bischen Dumm vor 🙂

    0
  • ?

    r0nny schrieb:

    es gibt verschiedene möglichkeiten

    du kannst dich z.B. von ast zu ast hangeln oder stacks aufbauen

    Tarzan kann das auch gut, von Liane zu Liane und so.

    0
  • B

    Her mein Code (noch in den Kinderschuhen) würde mich freuen wenn ihr VErbesserungsvorschläge, Optimierung hinsichtlich Performance, und Kritik geben könntet..

    #pragma once

// CAllocation command target

class CAllocation : public CObject{

	//Notwendige Pointer
	CAllocation *m_pFather, *m_pBrother, *m_pFirst_Son;
	//DEbug Name 
	CString m_strName;
public:

	class iterator{

		CAllocation *m_pIterPos;
	public:

		//Konstruktor
		iterator(CAllocation *pPos): m_pIterPos(pPos){}

		//Iteration ein Knoten nach vorne
		void operator++(){

			//Baum nach unten klettern
			if(m_pIterPos->m_pFirst_Son!=NULL)
				m_pIterPos= m_pIterPos->m_pFirst_Son;
			else if(m_pIterPos->m_pBrother!=NULL)
				m_pIterPos= m_pIterPos->m_pBrother;
			else{
				//Baum hochklettern
				CAllocation *p= m_pIterPos->m_pFather->m_pBrother;
				while(m_pIterPos->m_pFather->m_pBrother==NULL && m_pIterPos!=NULL)
					m_pIterPos=m_pIterPos->m_pFather;
				if(m_pIterPos==NULL)
					return;
				m_pIterPos=m_pIterPos->m_pFather->m_pBrother;
			}
		}

		//Aktueller Knoten an Iteration
		CAllocation* operator->() const {
			return m_pIterPos;		
		}

		CAllocation* operator*() const { 
			return m_pIterPos;	
		}

		bool operator!=(const CAllocation *pOpp) const {
			return m_pIterPos!=pOpp;
		}

	};

	//Default Konstruktor
	CAllocation(CString strName) :	m_pFather(NULL),
									m_pBrother(NULL),
									m_pFirst_Son(NULL),
									m_strName(strName){

	}

	//Konstruktor
	CAllocation(CAllocation *pFather,CString strName):	m_pFather(pFather), 
														m_pBrother(NULL), 
														m_pFirst_Son(NULL),
														m_strName(strName){

		ASSERT(m_pFather!= NULL);

		//AlleBrüder des Vaters druchlaufen und diesen Knoten als leter Bruder anhängen!
		CAllocation *pChilds= m_pFather->m_pFirst_Son;

		//Wenn Vater keine Kinder hat dann diese Knoten als Erster Sohn definieren, sonst als letzter Bruder.
		if(pChilds==NULL)
			m_pFather->m_pFirst_Son= this;
		else{	
			for(; pChilds->m_pBrother!= NULL; pChilds= pChilds->m_pBrother);
			pChilds->m_pBrother= this;
		}
	}

	//Destruktor
	virtual ~CAllocation(){

		//Zuerst Knoten aus Baum struktur ausgliedern
		CAllocation *pFather= this->m_pFather;
		if(pFather!=NULL){
			CAllocation *pChilds= pFather->m_pFirst_Son;
			//Dieser Knoten ist das erste Kind, also daszweite Kind als erstes Kind des Vater setzen
			if(pChilds==this)
				pFather->m_pFirst_Son= pChilds->m_pBrother;
			else{
				while(pChilds->m_pBrother!= this)
					pChilds= pChilds->m_pBrother;
				//Knoten in Childliste ausketten
				pChilds->m_pBrother= pChilds->m_pBrother->m_pBrother;
			}
		}
		//Ab hier steht der Knoten alleine, und kann samt unterknoten gellöscht werden
		CAllocation::iterator it= this;

		while(this != this->end()){
			CAllocation *p = (*it);
			++it;
			delete p;
		}
		// Iterator verwenden!!

	}

	void TRACE_Debug(){

		CAllocation::iterator it= this;
		UINT iCounter=0;
		while(it != this->end()){
			printf("Nr %2i \t NodeName %s \n",iCounter,(*it)->m_strName);
			++it;
			iCounter++;
		}
		printf("Nr %2i \t NodeName %s \n",iCounter,(*it)->m_strName);
		//for(CAllocation::iterator it= this,int i=0; it != this->end() ; ++it,++i)
		//	printf("Nr %2i \t NodeName %s \n",i,(*it)->m_strName);

	}

	UINT GetChildsCount(){
		UINT iCounter=0;
		for(CAllocation *pChilds= m_pFirst_Son; pChilds->m_pBrother!= NULL; pChilds= pChilds->m_pBrother, iCounter++);
		return iCounter;
	}

	CAllocation* begin(){
		//Von jedem Kind Knoten aus die Wurzez bzw. oberste Vater ermitteln
		CAllocation *pGrandfather= m_pFather;
		for(; pGrandfather!= NULL; pGrandfather= pGrandfather->m_pFather);
		return pGrandfather;
	}

	CAllocation* end(){

		CAllocation *pChilds= this;
		while(1){
				//Brüder für diesen Knoten durchlaufen
				for(; pChilds->m_pBrother!= NULL; pChilds= pChilds->m_pBrother);
				//Eine ebene des letzen Kindes (Bruders) nach unten steigen
				if(pChilds->m_pFirst_Son==NULL)
					break;
				pChilds=pChilds->m_pFirst_Son;
		}
		return pChilds;
	}
};

    Danke im Vorraus

    0
Anmelden zum Antworten