AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Algorithmenproblem: Baum in Liste speichern -> Vater finden?
Thema durchsuchen
Ansicht
Themen-Optionen

Algorithmenproblem: Baum in Liste speichern -> Vater finden?

Ein Thema von JasonDX · begonnen am 18. Feb 2005 · letzter Beitrag vom 18. Feb 2005
 
Benutzerbild von JasonDX
JasonDX
(CodeLib-Manager)

Registriert seit: 5. Aug 2004
Ort: München
1.062 Beiträge
 
#1

Algorithmenproblem: Baum in Liste speichern -> Vater find

  Alt 18. Feb 2005, 16:51
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?
Mike
Passion is no replacement for reason
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 18:06 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz