Algorithmenproblem: Baum in Liste speichern -> Vater finden?

[JasonDX]

Ich habe einen Baum mit Tiefe N und jedes element kann beliebig viele Kinder haben
den baum speichere ich mir ganz einfach in einem array
nachdem es nur um den aufbau des Baumes geht, und nicht um den Inhalt der Einzelnen Baumelemente, speichere ich ihn folgendermaßen ab:

den Baum

Code:

0       0
_     /   \
1    1     2
_   / \   / \
2   3 4  5   6
_         \
3          7

speichere ich so ab:
2,2,0,0,2,1,0,0
0,1,3,4,2,5,7,6
Nun die Erklärung:
Im der oberen liste ist das, was ich speichere
in der unteren bloß die indexe der elemente des baumes

ich speichere also bloß die Anzahl der Kinder
(Element 0 hat 2 kinder, als 2 bei liste hinzufügen
dann das selbe für die einzelnen kinder, von links nach rechts)


Und nun das Problem
eine funktion, die mir sagt, ob es sich um einen gültigen baum handelt, und wieviel kinder ein element hat, hab ich
bloß den Vater eines Elementes finde ich nicht.
soweit bin ich schon mal
(das ganze ist, wie man unschwer erkennen kann, in C programmiert)

Code:

int Data[Used]; //da steht dann der baum als liste drinnen

int FindFather(int Index)
{
  int c = 0;
  for (int i = Index - 1; i; i--)
    if (!(c = c - Data[i] + 1))
      return i;
}

Funktionieren tut das ganze dann so, dass ich von links nach rechts laufe, bis ich denke, meinen vater gefunden zu haben.
Den meine ich gefunden zu haben, wenn alle Kinder (Elemente mit 0) vor mir ihren Vater gefunden haben
Wieviele Kinder ihren Vater noch finden müssen, speichere ich in c
Bloß funktioniert die Funktion nicht immer so, wie ich es möchte.
Kann mir hier jemand weiterhelfen?

[atreju2oo0]

Um den Vater rausfinden zu können musst Du die Kinder nicht durchzählen sondern nummerieren

0
1 2
3 4 5 6
7 11 14


bei 3 nach rechts folgend wäre dann 8 usw...

(Falls das jetzt mit deiner Problemstellung keinen Sinn macht tuts mir leid...
Habs halt so verstanden)

[sniper_w]

Ein Baum ist eine Rekursive DatenStruktur. In deinem Beispiel, jedes Element hat ein eigenes Wert und noch 3 , 2 Kinder und 1 Eltern (Nur nuch UrEltern :))
Ich wurde ein Element so Deklatieren :

Zitat:

struct tnode {
int Wert ; //beispeil
int Count;
struct tnode *Vater;
struct tnode *Links;
struct tnode *Rechts;
};

Ein Element hinzufühgen:

Zitat:

struct tnode *talloc(void)
{
return (struct tnode*)malloc(sizeof(struct tnode));
}

struct tnode *addtree(struct tnode *p,int w,struct tnode *Vater_)
{
if (p==NULL)
{
p = talloc();
p->Wert = w;
p->Count = 1;
p->Links = p->Rechts = NULL;
p->Vater = Vater_;
}
else
if (w=p->Wert) p->Count++;
else
if (w<p->Wert) p->Left = addtree(p->left, w, p);
else p->Rechts = addtree(p->Rechts,w, p);

return p;
}

Ein element Finden:

Zitat:

BOOL findnode(struct tnode *gefundene,struct tnode *anfangsnode, int w)
{
if (anfangsnode = NULL)
return FALSE;
if (anfangsnode->Wert == w)
/*GEFUNDEN*/
{
gefundene = anfangsnode;
return TRUE;
}
else
if (anfangsnode->Wert < w)
return findnode(gefundene, anfangsnode->Links,w);
else return findnode(gefundene, anfangsnode->Rechts,w);
}

So kannst du einfach zuerst finden was du willst und dann liest einfach wer Vater und Kinder sind.

[JasonDX]

@atreju2oo0: Nach welchen Regeln sollte ich die durchzählen? Wenn ich sie nach den Indexen wie beim Ursprungsbaum numeriere, versteh ich noch nicht, wie mir das weiterhelfen könnte

@sniper_w: Der Baum mit der ähnlichen Struktur, wie du ihn hast, war meine Ausgangssituation.
Ich bin dann zur Liste gegangen, weil 1. mir die Rekursion zu langsam war und 2. der Speicherbedarf bei größeren bäumen relativ hoch ist im vergleich zur liste


PS: Was ich vergessen hab zu sagen: Es handelt sich NICHT um einen binären baum, sondern beliebig viele Kinder sind pro Element möglich