Pfad zu schwerstem Blatt suchen
-
Hallo
Gegeben ist ein Baum, in dem jeder Konten beliebig viele Nachfolger haben kann, jedoch nie über 8. In den Blättern stehen Integers. Jetzt suche ich den Pfad zum 'schwersten' Blatt, sprich mit der größten Zahl. Die Pfade sind dabei durchnummier von 0 bis 7, aber es müssen wie gesagt nicht alle Zahlen vorkommen. Als Pfad reicht die erste Verzweigung, also direkt nach der Wurzel, schon völlig aus. Zurückliefern soll die Funktion dann die dem Pfad entsprechende Zahl.
Ich suche den Ansatz, von mir aus auch in Pseudocode. Kann mir jemand helfen?
-
Kannst du mit for-Schleifen alle Gewichte einlesen und dann das Maximum suchen?
-
Ich dachte eine rekursive Lösung, die den Baum durchgeht.
Irgendwie muss dort eine Funktion max dazwischenstehen, die den aktuellen mit dem atuell besten Wert vergleicht. In jedem Falle bleibt mein größtes Problem, wie ich den Pfad speichern kann.
-
Ja das geht auch. Nur kannst du dann nicht so leicht z.b. sortiert alle Werte und Pfade ausgeben.
In welcher Form liegt dieser Baum vor?
-
Ich brauche auch nicht alle Werte. Nur den Pfad, der zum Maximum führt (das Maximum selbst ist auch uninteressant)
Es ist ein klassischer Baum, aufgebaut aus Zeigern auf Strukturen.
-
Na dann 2 unsigned char-Arrays erstellen, in deren Zellen jeweils die Abzweigungen stehen, die Größe entspricht der maximalen Stufenzahl.
In eines dieser Arrays speicherst du immer den aktuellen Pfad, am Ende des Pfades vergleichst du den Wert mit dem bisherigen Maximum.
Falls größer, Array kopieren und Vorgang wiederholen.