Größtes Element im unsortierten Binärbaum

Wayman

Mitglied
Hey Leute.
Ich habe folgendes Problem:
Ich möchte in einem unsortierten Binärbaum den Knoten mit der maximalen Zahl finden und muss dabei rekursiv vorgehen.
Mein bisheriger Ansatz ist leider nicht 100% richtig.
Java:
Knoten maxi() {
	if (this.Wurzel == null) return null;
	else {
		Knoten max = new Knoten(Integer.MIN_VALUE);
		maxi(Wurzel, max);
		return max;
	}
}

void maxi(Knoten k, Knoten max) {
	if (k != null) {
		if (k.Zahl > max.Zahl) {
			max.Zahl = k.Zahl;
		}
		maxi(k.links, max);
		maxi(k.rechts, max);

	}
}
 
Zuletzt bearbeitet von einem Moderator:
Ich bin mir ehrlich gesagt nicht ganz sicher.

Ich habe jetzt mal probiert den Knoten max in der Klasse zu deklarieren, aber dann überschreibt der auch nicht den Wert der Klassenvariablen.

Vielleicht muss ich eine Hilfmethode implementieren. public void setZahl (int Zahl) oder so
 
Oder du läufst bis vom root aus bis zu die Knoten jeweils links und rechts, bis du an den Blättern bist. Danach gibst du die Blätter zurück und in jedem inneren Knoten prüfst du welcher Knoten (links oder rechts) größer ist und gibst diesen dann zurück.
Pseudocode:
Code:
def max(root : Node) : Node = {
  if(root.left == null && root.right == null) return root;
  else if(root.left == null) return max(root.right);
  else if(root.right == null) return max(root.left);
  else {
    val maxLeft : Node = max(root.left);
    val maxRight : Node = max(root.right);
    return if(maxLeft.value < maxRight.value) maxRight else maxLeft;
  }
}
 
Ich habe es mal probiert umzusetzen:


Code:
    Knoten maxi(){
        return max(Wurzel);
    }

     Knoten max(Knoten k){
        if(k.links == null && k.rechts == null) return k;
        else if (k.links == null) return max(k.rechts);
        else if (k.rechts == null) return max(k.links);
        else {
        Knoten maxLinks= max(k.links);
        Knoten maxRechts = max(k.rechts);
     if(maxLinks.Zahl < maxRechts.Zahl) return maxRechts;
     else return maxLinks;
        }
    }

Jedoch funktioniert es immer noch nicht. Ich denke mein Hauptproblem liegt darin, dass ich nicht weiß, wie man die Werte, die man zurück bekommt durch den return zwischenspeichern kann, um sie im Anschluss in der höheren Ebene wieder abzurufen und zu verwenden.
 
Du vergisst immer den aktuellen Knoten mit zu vergleichen. Dein Algorithmus sucht den größten Blattknoten.

Stell dir vor du hast diesen Baum:
4fdz48tw.png


Du delegierst die Aufrufe erst weiter nach unten.

Der Knoten 1 hat keine Kinder also wird 1 returned. Der Knoten 3 hat auch keine Kinder, also wird 3 returned.
Im 7er Knoten gibst du jetzt 3 zurück, da du nur überprüfst ob 1 oder 3 größer ist. Du vergisst den Knoten selbst mit einzubeziehen.

Am Ende vergleichst du dann 3 mit 6 und gibst die 6 zurück. Die 7 hast du aber garnicht betrachtet.
 

Neue Themen


Zurück
Oben