# Binärbaum aus Eingabe durch Leerzeichen getrennt erstellen



## crazyhand77 (16. Jun 2009)

Hi,

ich habe eine Hausaufgabe und komme nicht weiter.

Ich poste einfach mal die HA so wie ich sie hier hab ohne umschreiben.



> Erzeugen Sie aus einer Eingabe, die aus durch Leerzeichen voneinander getrennten Wörtern besteht, einen möglichst gleichmäßigen Binärbaum, wie in der Vorlesung beschrieben, indem Sie immer das mittlere Wort der als Wurzelelement benutzen und aus den vorangehenden bzw. folgenden Wörtern den linken und rechten Kindbaum bilden. Lesen Sie dazu zunächst alle Wörter in ein Array- oder ArrayList-Objekt ein. Die maximale Anzahl der Wörter kann auf 100 beschränkt werden.
> Geben Sie den erzeugten Baum in Pre-Order-Traversierung aus, wobei die Kindknoten gegenüber dem Elternknoten um zwei Zeichen eingerückt sind. Warum müssen die externen Knoten mit ausgegeben werden?
> Beispiel:
> 
> ...



Ich habe die eingabe schon in einem String array. Mein Problem ist nun, wie ich aus den eingegebenen und in ein String array gepackten Daten einen Baum erstelle.

Ich wäre froh wenn mir jemand helfen könnte.

MfG Alex


----------



## SlaterB (16. Jun 2009)

kannst du denn auf irgeneine Art einen Binärbaum erstellen?
also
setze root = ..
füge linken Nachfolger ein 
füge rechten Nachfolger ein 
gib Pre-Order aus

funktioniert das soweit, sind die Baum-Klassen vorhanden?

nun musst du die Strings einem nach dem anderen einlesen, und die Anzahl der Leerzeichen prüfen, um die Stufe festzustellen,
außerdem musst du noch den zuletzt erstellten Node merken

fange mit

```
Moskau
  Lissabon
```
an, bekommst du das hin?

danach überlege,
was zwischen

```
Moskau
  Lissabon
    Hamburg
```
und

```
Moskau
  Lissabon
  Hamburg
```
anders ist, wie du daraus allgemeinen Code machen kannst, der mit beiden Beispielen klar kommt


----------



## crazyhand77 (16. Jun 2009)

Ich könnte einen Baum erstellen indem ich ein Objekt erstelle mit den attributen data, left, right.
Ist das soweit richtig?


----------



## SlaterB (16. Jun 2009)

als Grundlage recht gut


----------



## crazyhand77 (16. Jun 2009)

Gut. Nun nehme ich das mittlere Element (in dem Falle Moskau und verwende dies als root element bzw). Nun weis ich allerdings nicht wie ich auf Lisabonn als left komme.

EDIT:

ok, ich bin ein Depp. Ich weis wie es geht. Jetzt nehme ich wieder den linken Teil und davon die Hälfte(da gerade Anzahl, das linke Element.) Und das ist der Linke Teilbaum. Selbiges mit der rechten Seite.

Ist das so richtig?


----------



## SlaterB (16. Jun 2009)

was ist die Hälfte eines linken Teils?
auf gerade oder ungerade würde ich mich auch nicht verlassen, obwohl man das vielleicht so machen kann,

es geht aber ohne:
wie gesagt nur das vorherige Element anschauen und die Anzahl Leerzeichen für die Stufe,
entweder das neue Element ist ein Unterelement des vorherigen oder ein Unterelement eines der Parents des vorherigen, je nachdem, wie es mit den Leerzeichen steht


----------



## crazyhand77 (16. Jun 2009)

Sollen die Leerzeichen jetzt mit im Array stehen?
Also so in der Art:



> String[] eing = new String[5]
> 
> eing[0]: Moskau
> eing[1]: Leerzeichen
> ...



Oder soll das ganze ohne die Leerzeichen gespeichert sein?


----------



## SlaterB (16. Jun 2009)

wer sagt, dass überhaupt irgendwo ein Array benötigt wird?
die Aufgabe verlangt einen Baum, 
an Zwischenschritten solltest du genau das programmieren, was du auch brauchst


----------



## crazyhand77 (16. Jun 2009)

In der Aufgabenstellung steht:


> Lesen Sie dazu zunächst alle Wörter in ein Array- oder ArrayList-Objekt ein.



Und da dachte ich, dass ich die Werte, die als String getrennt von einem Leerzeichen eingegben werden in ein Array gelesen werden müssen.


----------



## SlaterB (16. Jun 2009)

nun gut, ich jedenfalls rate dann dazu, auch die Anzahl der Leerzeichen zu beachten, ergo sie mit abzuspeichern


----------



## crazyhand77 (16. Jun 2009)

Ok, so habe ich das auch gemacht. Funktioniert auch so wie ich das will.
Aber ich weis trotzdem nicht, wie ich die linken und rechten Elemente ohne Beachtung des jeweils Mittleren Elements herausbekommen soll.


----------



## SlaterB (16. Jun 2009)

mach es wie gesagt andersrum: gehe von Zeile zu Zeile und ordne diese korrekt ein,
am Ende hast du dann einen ferigen Baum, ohne speziell in jeder Ebene neu über links/ rechts/ mitte nachdenken zu müssen


----------



## crazyhand77 (16. Jun 2009)

Wenn ich in 30 minuten wieder zuhause am Rechner bin probiere ich das mal, obwohl ich bis jetzt noch keine Ahnung habe wie ich beim ersten Element wissen soll auf welcher Ebene es steht etc. Ein weiteres Problem ist ja, dass ich, wenn ich die Klasse Baum mit links und rechts als Verweis auf den nächsten Knoten der Klasse Baum definiere, ich gleich wisse muss, wo ich das Element einordnen muss. Oder versteh ich das hier gerade falsch?


----------



## SlaterB (16. Jun 2009)

siehe


SlaterB hat gesagt.:


> wie gesagt nur das vorherige Element anschauen und die Anzahl Leerzeichen für die Stufe,
> entweder das neue Element ist ein Unterelement des vorherigen oder ein Unterelement eines der Parents des vorherigen, je nachdem, wie es mit den Leerzeichen steht


----------



## crazyhand77 (16. Jun 2009)

Sry, du hast zwar alles super erklärt, aber ich kann mir nicht daraus nehmen wie ich die anzahl der Leerzeichen etc. zu behandeln habe. Kannst du mir das vielleicht an nem Beispiel erklären? Raff das sonst anscheinend nich 

Danke schonmal.


----------



## SlaterB (16. Jun 2009)

SlaterB hat gesagt.:


> fange mit
> 
> ```
> Moskau
> ...


Lissabon ist zwei Leerzeichen weiter, also Kind von Moskau,
klappt soweit das Programm, oder was ist bis hierhin nicht zu verstehen?



> danach überlege,
> was zwischen
> 
> ```
> ...


Hamburg ist entweder wieder das Kind oder auf gleicher Stufe, dann Kind des Parents, 
welcher bekannt ist, dann man kennt ja den Eintrag der vorherigen Zeile,
alles an den Leerzeichen zu erkennen,
was genau ist unverständlich?

bisschen denken und arbeiten musst du schon bei so einem Programm


----------



## crazyhand77 (16. Jun 2009)

Hmm, das was du da siehst ist das, was ich ausgeben muss. Also diese Baumstruktur.

Ich habe einzig und allein zur Verfügung und zum Bearbeiten einen String.


```
String eingabe = "Athen Berlin Lissabon Madrid Moskau Paris Prag Sofia Warschau"
```

Das was in einer Art Baumstruktur angegeben ist, ist nur das Ergebnis was aus dieser Zeichenkette entstehen soll.


----------



## SlaterB (16. Jun 2009)

tja, schöne sch..e,
aber nun weiß ich ja, worum es geht 

dann werde ich dir zum Ausgleich etwas mehr helfen, 
also die Städte in ein Array oder eine Liste, Leerzeichen dann natürlich nicht mehr, haben keine Funktion

das mittlere Element bestimmen und aus dem linken + rechten Rest einen Teilbaum aufbauen,
dafür braucht man eine Rekursion, etwa

Baum baueBaum(Liste) {
x = mittleres Element
Baum l = baueBaum(linke Restliste);
Baum r = baueBaum(linke Restliste);

erstelle Baum b aus x, l, r 
return b
}

auf Endbedingungen wie Listen mit <= 3 Elementen achten,
bei gerader Anzahl kannst du dir aussuchen, welches das mittlere Element sein soll


----------



## crazyhand77 (16. Jun 2009)

Das mit dem linken und rechten Teilbaum hatte ich übrigens vorhin gemeint, aber vielen Dank  ich bin Froh dass ich Hilfe finde. Wunderbar. Ich poste dann ma den code, wenn ich fertig sein sollte.

Achja, ich poste mal noch meine Baum Klasse, die müsste ja so OK sein.


```
public class BinaerBaum {

	String data;
	BinaerBaum left;
	BinaerBaum right;
	
	public BinaerBaum(String data, BinaerBaum left, BinaerBaum right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}
	
	public BinaerBaum(String data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
	
	public String getData() {return this.data;}
	public BinaerBaum getLeft() {return this.left;}
	public BinaerBaum getRight() {return this.right;}
	public void setData(String data) {this.data = data;}
	public void setLeft(BinaerBaum left) {this.left = left;}
	public void setRight(BinaerBaum right) {this.right = right;}
}
```


----------



## crazyhand77 (16. Jun 2009)

> Baum baueBaum(Liste) {
> x = mittleres Element
> Baum l = baueBaum(linke Restliste);
> Baum r = baueBaum(linke Restliste);
> ...



Meinst du mit Liste in baueBaum(Liste) das array wo ich die Städte hineingeschrieben habe?


----------



## SlaterB (16. Jun 2009)

statt Liste geht auch Array,
die Teillisten = Teilarrays sind entweder neu erstellte kleinere Arrays oder du übergibst das Originalarray und Anfang- + Ende-Index


----------



## crazyhand77 (16. Jun 2009)

EDIT:

Hab jetzt was, aber die Methode createBaum hat noch Fehler.


```
public class Aufgabe1 {
	
	BinaerBaum root;
	BinaerBaum e;
	
	public Aufgabe1() {
		this.root = null;
	}
	
	public BinaerBaum createBaum(String[] baum, int anz) {
		int x = anz /2;
		e.setData(baum[x]);
		root = e;
		e.setLeft(createBaum(baum, x/2));
		e.setRight(createBaum(baum, (anz/2)+(x/2)));
		e.setData(baum[x]);
		return e;
	}
	
	public void go() {
		SimpleInput in = new SimpleInput();
		//zählvariable a anlegen und initialisieren;
		int a = 0;
		//Städte eingeben
		String eingabe = in.readString("Geben sie maximal 100 Wörter getrent mit Leerzeichen ein: ");
		//String uebergang anlegen und initialisieren
		String uebergang = "";
		//String array anlegen
		String[] baum = new String[100];
		//String in Char array
		char[] eingabeChar = eingabe.toCharArray();
		//Städte in String array einfügen
		for (int i = 0; i < eingabeChar.length; i++) {
			if (eingabeChar[i] != ' ') {
				uebergang += eingabeChar[i];				
			} else {
				baum[a] = uebergang;
				a++;
				uebergang = "";
			}
		}
		//letzte Stadt an String array anfügen
		baum[a] = uebergang;
		a++;
		//Ausgabe des String arrays
		for (int z = 0; z < a; z++) {
			System.out.println(baum[z]);
		}
		root = createBaum(baum, a);
		
	}
	
	public static void main(String[] args) {
		Aufgabe1 r = new Aufgabe1();
		r.go();
	}
}
```


----------



## SlaterB (16. Jun 2009)

stell dir vor du hast ein Array der Länge 10,
erstes x = 5,
linker Teilbaum, glauben wir mal das das klappt
rechter Teilbaum bekommt dann als Parameter 7

dann wird für den rechten Teilbaum x = 3 gewählt, also ein Element der linken Hälfte, das wird übel,
du musst also genaue Info 'von 5 bis 10' übergeben, z.B. Begin- + EndIndex

und immer die Abbruchbedingungen!

> //root sollte egtl nur einmal auf e zugewiesen werden
prüfen, ob root null ist oder schon gesetzt


----------



## crazyhand77 (16. Jun 2009)

EDIT:



Das müsste jetzt stimmen.


```
public class Aufgabe1 {
	
	BinaerBaum root;
	BinaerBaum e = new BinaerBaum();
	
	public Aufgabe1() {
		this.root = null;
	}
	
	public BinaerBaum createBaum(String[] baum, int anz) {
		int x = anz /2;
		e = new BinaerBaum();
		if (root == null) {
			root = e;
		}
		e.setData(baum[x]);
		if (x != 0) {
			e.setLeft(createBaum(baum, x/2));
			e.setRight(createBaum(baum, (anz/2)+(x/2)));
			e.setData(baum[x]);
		}
		return e;
	}
	
	public void go() {
		SimpleInput in = new SimpleInput();
		//zählvariable a anlegen und initialisieren;
		int a = 0;
		//Städte eingeben
		String eingabe = in.readString("Geben sie maximal 100 Wörter getrent mit Leerzeichen ein: ");
		//String uebergang anlegen und initialisieren
		String uebergang = "";
		//String array anlegen
		String[] baum = new String[100];
		//String in Char array
		char[] eingabeChar = eingabe.toCharArray();
		//Städte in String array einfügen
		for (int i = 0; i < eingabeChar.length; i++) {
			if (eingabeChar[i] != ' ') {
				uebergang += eingabeChar[i];				
			} else {
				baum[a] = uebergang;
				a++;
				uebergang = "";
			}
		}
		//letzte Stadt an String array anfügen
		baum[a] = uebergang;
		a++;
		//Ausgabe des String arrays
		/*
		for (int z = 0; z < a; z++) {
			System.out.println(baum[z]);
		}
		*/
		createBaum(baum, a);
	}
	
	public static void main(String[] args) {
		Aufgabe1 r = new Aufgabe1();
		r.go();
	}
}
```

Jetzt muss ich nur noch die Ausgabe hinbekommen, so dass sie so aussieht wie in der Aufgabenstellung.


----------

