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?