Binärbaum Ordnungsproblem

pzypher

Aktives Mitglied
Hallo,

ich schaffe es nicht, Zahlen bis n in einen geordneten binären Suchbaum unterzubringen. (linker Ast kleiner; rechter Ast größer als Vaterknoten)

Bei meinem Beispiel möchte ich 60 Zahlen unterbringen, dh. hätte ich mir root = 30 angefangen.

Klasse Knoten
Java:
public class Knoten {
	
	Knoten links;
	Knoten rechts;
	int value;
	
	public Knoten(int value) {
		this.value = value;
	}
	
	public void insert(Knoten currentRoot, int value) {
		
//Füge neue Wurzel ein, falls Wert kleiner Vorgänger + nächste Wurzel = null
		if(value < currentRoot.value) {
			if(currentRoot.links == null) {
				System.out.println(" Wert " + value + " links vom root " + currentRoot.value);
				currentRoot.links = new Knoten(value);
			}
//sonst rekursiver Aufruf mit nächstem Wurzelelement
			else 
				insert(currentRoot.links, value);
		}
//Füge neue Wurzel ein, falls Wert größer Vorgänger + nächste Wurzel = null
		else if(value > currentRoot.value) {
			if(currentRoot.rechts == null) {
				System.out.println(" Wert " + value + " rechts vom root " + currentRoot.value);
				currentRoot.rechts = new Knoten(value);
			}
//sonst rekursiver Aufruf mit nächstem Wurzelelement
			else 
				insert(currentRoot.rechts, value);
		}
	}

}

Klasse Hauptprogramm
Java:
import java.util.Scanner;

public class Hauptprogramm {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub


//Mein aktueller Versuch, Zahlen von 60 in einen Binärbaum unterzubringen
//root soll den Wert 20 haben (damit alle Äste gleich lang sind?) 

		Knoten root = new Knoten(30); 
		
//Mit dieser Schleife erschaffe ich mir nur einen Baum, der nach links und rechts geht 

		for(int i = 1; i <= root.value; i++) {
			
			if(i%2==0) 
				root.insert(root, root.value-i);
			else
				root.insert(root, root.value+i);
		}
	}

}

Mit dem aktuellen Hauptprogramm erstelle ich einen Baum, bei dem jede Wurzel (bis auf root) nur 1 Nachfolger hat.

Ich suche bereits seit Stunden nach einer Rechenvorschrift, finde (oder verstehe?) aber keine. Ich wäre auch schon dankbar wenn mir jemand eben diese Rechenvorschrift vermittelt, die Implementierung mach ich dann gerne selber.

Danke für eure Hilfe!
 

XHelp

Top Contributor
Mach es doch auf dem Blattpapier nach, dann kommst du bestimmt auf das selbe Ergebnis.
Falls ich es mir richtig vorstelle, dass muss du, damit dein Baum "ausbalanciert" ist, jeweils die "Mitte" hinzufügen:
zuerst 30, dann 15 und 45, dann 7, 22, 38, 52 usw.
Einfach mal in einer Reihe alle Zahlen reinzuknallen wird nicht klappen.
 

Fant

Bekanntes Mitglied
Wenn man einen ausbalancierten Baum haben will, dann sollte der Baum selbst aber dafür sorgen, dass er ausbalanciert ist und nicht der Benutzer beim Einfügen der Werte.
Wenn alle einzutragenen Werte vorher bekannt sind, dann wird der Baum ja eh sinnlos sein...
 

pzypher

Aktives Mitglied
Und wieso ist das ein Problem? Mir ist nicht klar, was du nun überhaupt wissen willst?! ???:L

Jede (bis auf evtl. die letzte) Wurzel hat genau 2 Nachfolger -> Binärer Baum; Ausserdem: linker Ast kleiner; rechter Ast größer als Vaterknoten -> siehe mein Problem

Mach es doch auf dem Blattpapier nach, dann kommst du bestimmt auf das selbe Ergebnis.
Falls ich es mir richtig vorstelle, dass muss du, damit dein Baum "ausbalanciert" ist, jeweils die "Mitte" hinzufügen:
zuerst 30, dann 15 und 45, dann 7, 22, 38, 52 usw.
Einfach mal in einer Reihe alle Zahlen reinzuknallen wird nicht klappen.

Ich werds probieren, danke

Wenn man einen ausbalancierten Baum haben will, dann sollte der Baum selbst aber dafür sorgen, dass er ausbalanciert ist und nicht der Benutzer beim Einfügen der Werte.
Wenn alle einzutragenen Werte vorher bekannt sind, dann wird der Baum ja eh sinnlos sein...

Der Benutzer gibt ja nur ein, welche Zahlen von n - m er im ausbalancierten Baum haben möchte. Und genau das wie bei: "sollte der Baum selbst aber dafür sorgen, dass er ausbalanciert ist" möchte ich ja herausfinden! ;)
 
Zuletzt bearbeitet:

Sesostris

Aktives Mitglied
Wenn du in einen normalen binären Suchbaum die Zahlen 1 bis 60 aufsteigend sortiert einfügst, hast du einen zur linearen Liste entarteten Baum. Da das für gewöhnlich unerwünscht ist, gibt es auch sogenannte balancierte Bäume, die durch geschicktes Rotieren die Blätter "balanciert" auf alle Äste verteilen und damit überlange Äste vermeiden. Wie Fant bereits geschrieben hat, sollte der Baum für diese Balancierung sorgen und nicht der Benutzer, Stichwort: Self-balancing binary search tree
 

Fant

Bekanntes Mitglied
Jede (bis auf evtl. die letzte) Wurzel hat genau 2 Nachfolger -> Binärer Baum; Ausserdem: linker Ast kleiner; rechter Ast größer als Vaterknoten -> siehe mein Problem

Das geht doch so überhaupt nicht. Wenn du in einen Baum 2 Element einfügst, dann ist diese Bedingung schon verletzt. Es geht einfach darum, dass jeder Knoten höchstens zwei Nachfolger besitzt.
Wenn du einen ausbalancierten Baum haben willst, dann solltest du wie vorher schon angesprochen wirklich einen anderen Baum verwenden.
 

XHelp

Top Contributor
Binärbaum heißt nicht, dass jeder Knoten (es gibt übrigens nur eine einzige Wurzel im Baum) IMMER 2 Kinder hat, sondern NICHT MEHR ALS 2 Kinder.
 

pzypher

Aktives Mitglied
Alles klar, danke, dann war das ein Missverständnis meinerseits. Ich werd mich mit der neuen Erkenntnis dann nochmal dranhocken und nachdenken ;)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Y Wie greift man auf die Knoten in einem Binärbaum zu? Java Basics - Anfänger-Themen 5
T Binärbaum-Suche Implementation Java Basics - Anfänger-Themen 6
A Binärbaum rekursiv durchsuchen und Referenz zurückgeben Java Basics - Anfänger-Themen 4
D Werte aus einem BinärBaum in einem Array speichern Java Basics - Anfänger-Themen 1
D Binärbaum Blätter finden und Ausgeben Java Basics - Anfänger-Themen 22
O BinärBaum einfügen Java Basics - Anfänger-Themen 13
E Erste Schritte Testklasse Binärbaum Java Basics - Anfänger-Themen 10
void19 Methoden Binärbaum Inorder Traversierung in Array speichern Java Basics - Anfänger-Themen 1
A Größten Eintrag aus Binärbaum löschen Java Basics - Anfänger-Themen 4
L Ganzen BinärBaum ausgeben? Java Basics - Anfänger-Themen 3
L Binärbaum (Stammbaum) Java Basics - Anfänger-Themen 8
S Binärbaum in PreOrder in ArrayList speichern Java Basics - Anfänger-Themen 0
J Methoden Binärbaum, Traversierung in Array speichern Java Basics - Anfänger-Themen 18
K BinärBaum Java Basics - Anfänger-Themen 4
J Max. Anzahl von Knoten im Binärbaum Java Basics - Anfänger-Themen 3
M Werte der Knoten in Binärbaum addieren (iterativ) Java Basics - Anfänger-Themen 6
C Binärbaum mit grafischer Ausgabe Java Basics - Anfänger-Themen 0
J Binärbaum formatiert ausgeben. Java Basics - Anfänger-Themen 7
P Listen sortieren mit Binärbaum gibt keine Ausgabe ab 10000 Integern Java Basics - Anfänger-Themen 14
E Binärbaum - von rekursiv zu iterativ Java Basics - Anfänger-Themen 10
W Größtes Element im unsortierten Binärbaum Java Basics - Anfänger-Themen 7
N Generischer Binärbaum - löschen Java Basics - Anfänger-Themen 1
M Binärbaum mit parent-Zeigern Java Basics - Anfänger-Themen 1
B Methoden BinärBaum als String Knoten löschen Java Basics - Anfänger-Themen 5
S Binärbaum kopieren Java Basics - Anfänger-Themen 6
B Binärbaum mit java implementieren! Java Basics - Anfänger-Themen 5
D Binärbaum Suche Java Basics - Anfänger-Themen 5
D Binärbaum probleme Java Basics - Anfänger-Themen 4
P Binärbaum - Primärschlüssel Java Basics - Anfänger-Themen 3
X Fehler Binärbaum Java Basics - Anfänger-Themen 6
PaulG Fragen zu Binärbaum Java Basics - Anfänger-Themen 21
N Binärbaum/Implementierung Java Basics - Anfänger-Themen 9
P Generischer Binärbaum (compareTo Frage) Java Basics - Anfänger-Themen 4
P einen binärbaum implementieren Java Basics - Anfänger-Themen 4
M Binärbaum - Problem bei Knoten anhängen / löschen Java Basics - Anfänger-Themen 5
B Binärbaum höhe herausfinden Java Basics - Anfänger-Themen 12
L Rot Scharz Baum von Binärbaum erben Java Basics - Anfänger-Themen 9
S Klassen Aufgabe: Binärbaum überprüfen Java Basics - Anfänger-Themen 16
S Binärbaum Java Basics - Anfänger-Themen 9
S Variable Parameterliste in Binärbaum Java Basics - Anfänger-Themen 2
N BinärBaum Hilfestellung Java Basics - Anfänger-Themen 8
S Binärbaum prüfen, ob sortiert oder unsortiert Java Basics - Anfänger-Themen 6
W Binärbaum zahlen addieren Java Basics - Anfänger-Themen 7
S Binärbaum - Klasse Knoten - Methode Suchen Java Basics - Anfänger-Themen 5
S Binärbaum Java Basics - Anfänger-Themen 7
I Binärbaum Java Basics - Anfänger-Themen 5
S Bitte um Hilfe beim unsortierten Binärbaum!! Java Basics - Anfänger-Themen 6
J Binärbaum getSize Java Basics - Anfänger-Themen 4
P Fragen zum Binärbaum Java Basics - Anfänger-Themen 3
S Binärbaum implementieren Java Basics - Anfänger-Themen 6
K Tiefe im Binärbaum Java Basics - Anfänger-Themen 2
G generischer binärbaum Java Basics - Anfänger-Themen 9
G Binärbaum und Wrapperklassen Java Basics - Anfänger-Themen 6
F Binärbaum codieren. Codeproblem! Java Basics - Anfänger-Themen 4
D rekursion im binärbaum Java Basics - Anfänger-Themen 11
0 Binärbaum als verkettete Liste Java Basics - Anfänger-Themen 3
T Binärbaum - noch ein "klitzekleiner Fehler" Java Basics - Anfänger-Themen 4
B Binärbaum auf Vollständigkeit prüfen Java Basics - Anfänger-Themen 15
G Frage zur einfügen in einem Binärbaum Java Basics - Anfänger-Themen 21
G Binärbaum grafisch darstellen Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Neue Themen


Oben