Suchalgorithmus für Baum mit n-Kinder gesucht.

Larrelt

Hi

Ich habe aus einer doppelt verketteten Liste eine multi verkette Liste gemacht. Also einen Baum wo jeder Knoten n-viele Kinder hat.

typedef struct baum			
{
	int iHoehe;//Fängt bei 1 an, bis max 9
	char szName[100];    // speichert den Namen. Also den Inhalt. 
	baum *pnaechster[200]; //Zeigt auf einen der Kinder
    baum *pvorgaenger;	    // Zeiger auf den Vorgänger.
	int iLeft; //Unwichtig.
	int iTop;//Unwichtig.
	int iRight;//Unwichtig.
	int iBottom;//Unwichtig.
}baum;

pnaechster Zeigt also auf eins der höchstens 200 Kinder. Jetzt will ich in meinen Baum neue Knoten einfügen. Bei einer verketten Liste ist dies kein Problem, jedoch muss ich beim Baum z.B. suchen, wo der Vorgänger ist, und dann das neue Kind anhängen. Nur wie finde ich einen Knoten in so einen Baum. Die ganzen suchverfahren (Breitensuche, Tiefensuche) gibt es nur für Beispiele vor ein Knoten max. 2 Kinder hat

Grüße!

CStoll

Du hast doch einen Zeiger auf den Vorgänger in deiner Struktur, jetzt mußt du nur in pVorgänger->pnaechster nach deiner Adresse suchen und den vorherigen Wert im Array nehmen.

Larrelt

Ich habe nur einen Zeiger auf den Vorgänger wenn der Knoten erstellt wurde. Der Knoten wird aber nicht am Ende des Baumes erstellt, sondern auch mittendrin. z.B.

Bei Peter Meyer soll das Kind Hans Meyer geaddet werden. Also muss ich erstmal im Baum suchen wo der Knoten Peter Meyer sich befindet. Dann mach ich ne neue Struktur, lass Peter Meyer aufs Kind Hans Meyer zeigen, und Hans Meyer soll auf den Vater Peter Meyer zeigen Nur muss als erstes der Knoten Peter Meyer in der Struktur gefunden werden

CStoll

Das kannst du rekursiv von der Wurzel (Urahn) aus machen:

baum* finde(baum pos,char* name)
{
  if(strcmp(name,pos.szName)==0) return &pos;

  for(int i=0;i<200;++i)
  {
    if(pos.pnaechster[i]==NULL) return NULL;//keine weiteren Kinder
    baum* fpos=finde(*(pos.pnaechster[i]),name);
    if(fpos!=NULL) return fpos;             //Kind gefunden
  }
  return NULL;
}

Larrelt

Moin,
erstmal vielen Dank!

Leider bekomme ich keinen Wert zurück wenn ich die Funktion aufrufe

"warning C4172: Adresse einer lokalen Variablen oder eines temporären Werts wird zurückgegeben"

Aufruf:

baum* objSearch = SucheBaum(point, *objTree.pWorker);

Funktion in der geprüft wird, ob in einen der Knoten( in der Fkt. fälschlicherweise Baum benannt) geklickt wurde:

baum* CTaxonView::SucheBaum(CPoint point,baum objBaum)
	{

	CRect Rectal;//Koordinaten aus Knoten holen.
	Rectal.top = objBaum.iTop; 
	Rectal.left = objBaum.iLeft;
	Rectal.bottom = objBaum.iBottom;
	Rectal.right = objBaum.iRight;

		if(Rectal.PtInRect(point)) return &objBaum;//Hier Warning

		for(unsigned int i=0;i<objBaum.child.size();i++)
			{
				if(objBaum.child[i]==NULL) return NULL;//Keine Kinder.

				baum* objBaum2 = SucheBaum(point ,*objBaum.child[i]);
				if(objBaum2 != NULL)
				{
					return objBaum2;//Falls Werte, Zurück!
				}

			}
		return NULL;
}

Hier nochmal die Struktur der einzelnen Knoten:

typedef struct baum			
{
	char szName[100];// speichert den Namen.
	vector<baum*>child;
    baum *pvorgaenger;	    // Zeiger auf den Vorgänger.
	////////////////////////////////
	int iLeft;
	int iTop;
	int iRight;
	int iBottom;
}baum;

Bin schon seit zwei Tagen dabei es zu fixen. Hoffe das ihr mir helfen könnt

Viele Grüße

Pellaeon

Hast du schon das Ding namens Debugger entdeckt?

objBaum ist eine lokale Kopie deiner Baumstruktur - versuch's mal mit der Deklaration "baum* CTaxonView::SucheBaum(CPoint point,const baum& objBaum)" stattdessen.