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.

Code:
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:

Code:

Eingabe: Athen Berlin Lissabon Madrid Moskau Paris Prag Sofia Warschau Ergebnis: Moskau Lissabon Berlin Athen () () () Madrid () () Sofia Prag Paris () () () Warschau () ()

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

Code:

Moskau
  Lissabon

an, bekommst du das hin?

danach überlege,
was zwischen

Code:

Moskau
  Lissabon
    Hamburg

und

Code:

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
eing[2]: Lisabonn
eing[3]: Leerzeichen
eing[4]: Hamburg

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

Code:

Moskau Lissabon

an, bekommst du das hin?

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

Code:
danach überlege,
was zwischen

Code:

Moskau Lissabon Hamburg

und

Code:

Moskau Lissabon Hamburg

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

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.

Java:

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.

Java:

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);

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

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.

Java:

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.

Java:

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.

Binärbaum aus Eingabe durch Leerzeichen getrennt erstellen

Mitglied

SlaterB

Gast

Mitglied

SlaterB

Gast

Mitglied

SlaterB

Gast

Mitglied

SlaterB

Gast

Mitglied

SlaterB

Gast

Mitglied

SlaterB

Gast

Mitglied

SlaterB

Gast

Mitglied

SlaterB

Gast

Mitglied

SlaterB

Gast

Mitglied

Mitglied

SlaterB

Gast

Mitglied

SlaterB

Gast

Mitglied