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:

Wayman

Mitglied
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
 

Flown

Administrator
Mitarbeiter
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;
  }
}
 

Wayman

Mitglied
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.
 

Tarrew

Top Contributor
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
D Größtes Palindrom Produkt aus zwei dreistelligen Zahlen Java Basics - Anfänger-Themen 60
sserio Größtes Palindrom-Produkt Programm funktioniert nur halb Java Basics - Anfänger-Themen 23
L Rekursion größtes Zeichen Java Basics - Anfänger-Themen 8
K Comparable - Objekte aus Array vergleichen und größtes auswählen Java Basics - Anfänger-Themen 1
F Größtes Produkt in einem String Java Basics - Anfänger-Themen 4
K Wie kann ich ein Element an den Anfang setzten ? Java Basics - Anfänger-Themen 1
pc pc pc pc pc letztes Element eines Arrays n Java Basics - Anfänger-Themen 3
heinrich172 Methoden Trotz gleichem Element stimmt Vergleich nicht? Java Basics - Anfänger-Themen 7
I Element n aus Datenbank Query (JPA / Hibernate) Java Basics - Anfänger-Themen 3
A Jedes zweite Element eines Arrays entfernen Java Basics - Anfänger-Themen 30
O Doppelt verkette Liste Element löschen Java Basics - Anfänger-Themen 15
L Längstes Element einer ArrayList ausgeben Java Basics - Anfänger-Themen 9
I Letztes, erstes Element vom Array Java Basics - Anfänger-Themen 9
districon Element in Liste einfügen Java Basics - Anfänger-Themen 1
Y Wie kann ich ein Element in einer toString finden. Java Basics - Anfänger-Themen 2
J Element aus Liste nehmen Java Basics - Anfänger-Themen 3
S Gibt es ein simples JWebbrowser Element? Java Basics - Anfänger-Themen 6
M Letztes Element einer ArrayList Java Basics - Anfänger-Themen 12
S Streams - kleinstes Element finden Java Basics - Anfänger-Themen 4
V_Fynn03 Beliebiges Element in einer Liste löschen (Java)(Lineare Datenstrukturen) Java Basics - Anfänger-Themen 9
V_Fynn03 Lineare Datenstrukturen Element löschen? Java Basics - Anfänger-Themen 2
J Selektiertes Element von jComboBox zwischenspeichern und wieder einsetzen Java Basics - Anfänger-Themen 0
Curtis_MC Collections Zufälliges Element aus Stack Java Basics - Anfänger-Themen 2
M Ist es möglich, das größte und zweitgrößte element in einem Array mit nur einer Schleife ausfindig zu machen ? Java Basics - Anfänger-Themen 19
X Array erstes und letztes Element tauschen Java Basics - Anfänger-Themen 2
A Konsolenausgabe: Hinter letztes Element ein "}" Java Basics - Anfänger-Themen 2
F nur das erste Element mit iterator ausgeben Java Basics - Anfänger-Themen 5
O Element aus Array löschen Java Basics - Anfänger-Themen 5
I Methoden List.contains() beim 2. Element = true Java Basics - Anfänger-Themen 1
M Array immer wieder um ein Element erweitern Java Basics - Anfänger-Themen 6
AnnaBauer21 org.w3c.dom.Element - Neues Element hinzufügen Java Basics - Anfänger-Themen 4
D doc.seect jsouo bestimmtes class element finden Java Basics - Anfänger-Themen 1
D Selenium Webdrive get x Element Java Basics - Anfänger-Themen 14
W Element aus HashSet in String umformen Java Basics - Anfänger-Themen 7
S Einfach verkettete Liste Element an bestimmter Position einfügen Java Basics - Anfänger-Themen 24
B Element in Array nach unten verschieben Java Basics - Anfänger-Themen 11
TechGirl JAVA GUI Oberfläche Umkreisung - wie heißt dieses Element? Java Basics - Anfänger-Themen 2
B Methoden Element aus einem Array löschen, Rest nach vorne verschieben? Java Basics - Anfänger-Themen 4
Z Html Element aus der Webseite auslesen Java Basics - Anfänger-Themen 1
A Hash Tabelle Element suchen Java Basics - Anfänger-Themen 1
K Collections Zugriff auf ein bestimmtes Element in der Collection Java Basics - Anfänger-Themen 1
K Element in ArrayList löschen ohne Index zu verschieben Java Basics - Anfänger-Themen 2
J Variablen Strings mit Zeilenumbrüchen in neues Array Element Java Basics - Anfänger-Themen 1
S Günstigstes Element aus einer ArrayList ausgeben Java Basics - Anfänger-Themen 10
N ArrayList: Das zweite Element wird zur Liste nicht eingefügt nach dem zweiten request. Java Basics - Anfänger-Themen 3
Ruvok Prüfen ob bestimmtest Element existiert im Array Java Basics - Anfänger-Themen 11
A ResultSet: vorheriges Element auslesen Java Basics - Anfänger-Themen 10
F Element aus LinkedList löschen Java Basics - Anfänger-Themen 3
J Element zu jList hinzufügen NullPointerExcepetion Java Basics - Anfänger-Themen 2
H Kein Zugriff auf das Element einer JList möglich: Fehlermeldung Java Basics - Anfänger-Themen 2
V wie kann man am einfachsten für ein Element der JavaFX die Umrandung aktiwieren ? auch ohne css ? Java Basics - Anfänger-Themen 4
D Fehlermeldung "com.element.JavaUpload.Manager" Java Basics - Anfänger-Themen 1
S Element von List<E> in String umwandeln Java Basics - Anfänger-Themen 3
I Element löschen aus der Liste Java Basics - Anfänger-Themen 2
G element in ArrayList Hinzufügen Java Basics - Anfänger-Themen 16
M ArrayList-Element hinzufügen u. löschen Java Basics - Anfänger-Themen 2
H Möglichkeit, mehrere Element zu speichern Java Basics - Anfänger-Themen 8
P Element aus einer einelementigen Menge bekommen. Java Basics - Anfänger-Themen 8
M Letztes Element im Array finden Java Basics - Anfänger-Themen 3
R Mit iterator auf Element zugreifen Java Basics - Anfänger-Themen 2
G Element einem Array hinzufügen Java Basics - Anfänger-Themen 7
Madlip Erste Schritte Das 4. Element?!? Java Basics - Anfänger-Themen 2
B Erstes Element eines Vectors erhalten Java Basics - Anfänger-Themen 5
Q queue.remove Element trotzdem noch vorhanden. Java Basics - Anfänger-Themen 10
H Zugriff auf Vector Element Java Basics - Anfänger-Themen 2
N Array, Element in Array? Java Basics - Anfänger-Themen 8
I Liste Remove erstes Element Java Basics - Anfänger-Themen 5
M Map mit Vektor: Element hinzufügen Java Basics - Anfänger-Themen 21
M element aus DB lesen Java Basics - Anfänger-Themen 4
C Variablen array element hinzufügen/entfernen Java Basics - Anfänger-Themen 10
K Letzter element aus einem Array Java Basics - Anfänger-Themen 5
S JDBC MySQL Connector - Element mit ' eintragen? Java Basics - Anfänger-Themen 4
R Element an ArrayList<int[]> "anonym" adden? Java Basics - Anfänger-Themen 3
Glühwürmchen Prüfen ob Element in ArrayList Java Basics - Anfänger-Themen 23
C Ausgewähltes Element einer JCombobox in JTextField Java Basics - Anfänger-Themen 3
L Element in Mitten eines Arrays einfügen Java Basics - Anfänger-Themen 3
S ArrayList nur ergänzen wenn Element noch nicht vorhanden Java Basics - Anfänger-Themen 4
3 3. Element mit regulären Ausdruck suchen Java Basics - Anfänger-Themen 12
S Auf Element in Arry zugreifen Java Basics - Anfänger-Themen 7
M String-Array-Element wieder null zuweisen Java Basics - Anfänger-Themen 16
B Element aus Array entfernen Java Basics - Anfänger-Themen 13
B Element in Folge suchen Java Basics - Anfänger-Themen 7
H Zeiger auf das letzte Element in einer linearen Liste Java Basics - Anfänger-Themen 4
A Array ein element hinzufügen. Java Basics - Anfänger-Themen 6
S element in Array kopieren Java Basics - Anfänger-Themen 12
S Auf Element aus Array zugreifen Java Basics - Anfänger-Themen 6
H LinkedList Element an Stelle x ausgeben? Java Basics - Anfänger-Themen 5
S Datentypen In ArrayList nach Element suchen und Position ausgeben Java Basics - Anfänger-Themen 9
M Wert soll element aus den natürlichen Zahen inkl. 0 sein Java Basics - Anfänger-Themen 6
T Letztes beschriebenes Array-Element ausgeben Java Basics - Anfänger-Themen 6
E TreeSet Element löschen Java Basics - Anfänger-Themen 9
J Stapel oberstes Element entfernen Java Basics - Anfänger-Themen 5
C Erstes Arraylist Element in for Schleife überspringen Java Basics - Anfänger-Themen 6
F jTable - neues Element vorher auf existenz Prüfen Java Basics - Anfänger-Themen 7
P Klasse nach Element casten Java Basics - Anfänger-Themen 4
G Mit Java Quelltext auf Element untersuchen. Java Basics - Anfänger-Themen 5
T Array auf einfaches Element umwandeln Java Basics - Anfänger-Themen 8
DasDogma Verkettete Liste - Element löschen Java Basics - Anfänger-Themen 2
O i-tes element eingeben? Java Basics - Anfänger-Themen 2
B Delete Methode löscht falsches Element Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Neue Themen


Oben