Binärbaum

julia123

Erfahrenes Mitglied
hi, bin grade dabei ein Binärbaum zu programieren. Hab jedoch kleines Prolem beim Verständnis der Frage:

Ein Binärbaum wird durch einen Knoten (node) abgebildet; der Knoten, der die Wurzel des Baums repräsentiert,
heißt Wurzelknoten (root). Jeder Knoten hat einen Schlüsselwert (key) und einen damit assoziierten
Zielwert (value). Ein Knoten kann einen rechten und einen linken Teilbaum haben. Alle Knoten im linken
Teilbaum haben ausschließlich Schlüsselwerte die kleiner sind als der Schlüsselwert des betrachteten Knotens.
Die Schlüsselwerte der Knoten im rechten Teilbaum sind ausnahmslos größer als der des betrachteten
Knotens. Zwischen den Schlüsselwerten muss eine Ordnungsbeziehung bestehen, so dass sie vergleichbar
sind (größer, kleiner, gleich). Ein Knoten ohne linken bzw. rechten Teilbaum heißt „Blatt“ (leaf ).
Der Einfachheit halber gehen wir davon aus, dass Schlüsselwerte ganzzahlig und Zielwerte Zeichenketten
sind.


Implementieren Sie die Klasse Node mit den gegebenen Attributen und drei Methoden: dem Konstruktor,
einer get- und einer insert-Methode.

Dem Konstruktor muss ein Schlüsselwert übergeben werden; die Angabe eines Zielwertes, eines rechten
und linken Knotens ist optional.

Die get-Methode betrachtet den vorliegenden Knoten als Wurzelknoten und sucht zum gegebenen
Schlüsselwert den Knoten mit diesem Schlüsselwert heraus. Sollte kein Knoten mit diesem Schlüsselwert
existieren, wird „nichts“ zurückgegeben – in den meisten Programmiersprachen ist das ein
Null, None oder Nil.

Die insert-Methode fügt, ausgehend vom vorliegenden Knoten, einen Knoten mit dem übergebenen
Schlüsselwert und dem optionalen Zielwert in dem Baum ein. Eine geeignete Einfügestelle muss
dazu gefunden werden. Existiert bereits ein Knoten mit dem Schlüsselwert, so wird der Zielwert
überschrieben.

Hier noch wie so ein Grapf aus sehen soll:


Mit diesen 3 Methoden soll dann wie in der Abbildung dargestellter Baum erstellt werde.

Was ich nicht verstanden hab , wo soll die Methoden befinden? Alle in der Node -Klasse?
Was soll der Zielwert repräsentieren? Für was soll das gut sein, und was meint man mit " einen Knoten mit dem übergebenen
Schlüsselwert und dem optionalen Zielwert in dem Baum ein" (Das Wort optional stört mich. Das würde ja heißen es gibt irrgendwelche Prefärenzen?)

Soll bei der insert-Methode ein Parameter Zielwert übergeben werden?

Hier meine zwischen Lösung:


Java:
public class BinTree {

	/**
	 * @param args
	 */

	public class Node {

		public int key;

		public Node left;
		public Node right;

		public String value;

		public Node(int key, String value) {
			this.key = key;
			this.value = value;
		}

		// public String get(int keySearch) {
		// if (keySearch == key) {
		// return key + "";
		// } else if (left.key == keySearch) {
		// return left.key + "";
		// } else if (right.key == keySearch) {
		// return right.key + "";
		// }
		//
		// return null;
		// }

	}

	private Node root;

	public String get(int keySearch) {

		if (keySearch == root.key) {
			return root.key + "";
		} else if (root.left.key == keySearch) {
			return root.left.key + "";
		} else if (root.right.key == keySearch) {
			return root.right.key + "";
		}

		return null;
	}

	public void insert_Methode(int key) {// ohne Prameter Zielwert
		if (root == null) {
			Node first = new Node(key, );// hab das jetzt offen gehalten
												// weill ich nicht weiss wie ich
												// dass mit dem Zeilwert
												// handhaben soll
			root = first;
		} else if (root.left == null) {
			Node startL = new Node(key, );
			root.left = startL;
		} else {
			Node startR = new Node(key, );
			root.left = startR;
		}

	}

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

	}

}

Vielen Dank schon mal!
 

Anhänge

  • baumgrapf.png
    baumgrapf.png
    7,3 KB · Aufrufe: 6
Zuletzt bearbeitet:

sheel

I love Asm
Hi

ja, die Methoden sollen wohl alle in Node sein.

Der Zielwert...was der repräsentieren soll oder so kann einem eigentlich komplett egal sein.
Vorerst wichtig it die Nummer key, nach der der Baum "sortiert" ist (Kleinere links, größere rechts)
und wonach suchbar ist. Zusätzlich hat eben jede Nummer einen String,
der (außer, dass er eben gespeichert werden sollte) nicht wichtig ist.
Das "optional" verstehe ich nicht als Präferenz, sondern dass als String
auch Nichts (null) verwendet werden können soll (ohne das dein Baumcode abstürzt)

Der Code nach der Reihe durch:
----------------------------------
Die 4 Variablen in Node schauen ziemlich perfekt aus, außer das sie public sind.
----------------------------------
Zum Konstruktor:
Man soll ja L/R-Knoten auch angeben können...Vorerst also
Java:
public Node(int key, Node left, Node right, String value)
und drin eben alle Variablen zuweisen.
Laut Angabe soll alles außer key auch null sein dürfen:

Beim Übergeben selbst passt das schon, weil key (int) nicht null sein kann
(Zahl 0 schon, aber nicht "Nichts). Da würde sich der Compiler schon beschweren,
man kann sich also darauf verlassen, das eine Zahl drin ist.
Wenn einer oder beide der Knoten null sind stört das nicht,
die Zuweisung kann unverändert erfolgen (also einfach keine Überprüfung oder irgendwas)
Ein null-Kindknoten bedeutet eben, dass da nichts ist (für die anderen Methoden)
Und für den String gilt das Selbe. Wenn man kein value will, eben null übergeben,
drin keine Sonderbehandlung, sondern einfach zuweisen

Was dann außer den 4 Zuweisungen evt. noch gut wäre:
Falls es Nicht-null-Kindknoten gibt: Überprüfen,
ob die enthaltene Keyzahl wirklich kleiner (L) bzw. größer (R) als die des aktuellen Knoten ist.
Wenn nicht: zB. eine Exception throwen,weil man so einen ungültigen Baum erstellen würde.
Falls die Kindknoten wieder Kindknoten haben müssen die nicht überprüft werden,
weil die schon von den Kindknoten selbst beim Erstellen davon geprüft wurden)
----------------------------------
Die Variable root gehört weg.
"Root" ist das, was man dann im main als Variable wie "Node meinBaum" hat
(wobei meinBaum eben ein Node ist, ggf. mit Kindknoten, die wieder Kindknoten haben usw...)
----------------------------------
Get schaut falsch aus.
Wenn keySearch==this.key dann return this.value
(und keinen verstringten Key. Das ist ja jetzt der einzige Sinn vom String value)

Wenn this.key größer ist muss der gesuchte Key im linken Teilbaum irgendwo sein.
Falls man keinen hat return null, sonst kann man die weitere Suche
einfach dem linken Teilknoten überlassen (der dann sich selbst und seine Kindknoten prüft...)
Also sowas wie "return left.get(keySearch)"

Falls this.key kleiner als keySearch war das Selbe mit Rechts statt Links...
----------------------------------
Zu insert später noch was
----------------------------------
main in Node drin ist vllt. nicht, was der Lehrer sich erwartet.
Mach noch eine Klasse nur fürs main
 

Fasibio

Mitglied
Sagmal wieso brauch mein unausgeglicher Baum mit 10 000 000 Werte zufälligen werte Grad mal 1 millisekunde um das einen Wert zu suchen
Da kann man ja dann garnicht mehr optimieren....
 

julia123

Erfahrenes Mitglied
Danke, erst mal. Hab dass ganze mal versucht in

Dass wenn der key gleich ist und die value überschrieben wird, hab ich nicht abgedeckt.

Weiss nicht wie ich ein Node anhänge und/oder da explizierte Node nehme um es zu überschreiben. Hab das mal oben so versucht zu realisieren wie ich es verstehe.
 
Zuletzt bearbeitet:

sheel

I love Asm
Zum Konstruktor:
Das mit dem Vergleich dass Key L (left) nicht größer als R sein darf ist zwar nicht falsch,
reicht aber nicht: L<this (Key) und this<R müssen beide gelten
(und L<R ist damit automatisch schon erfüllt).
(und die Vergleiche gehen dann zumindest zur Hälfte auch,
wenn nur einer von L/R nicht null ist)

Noch dazu hab ich oben bei der Beschreibung auch zu einfach gedacht, sorry:
Auch, wenn zB. L.key < this.key ist kann ja L´s Kindknoten L.R.key wieder > this.key sein...
Der ganze Baum Teilbaum müss kleiner/größer this.key sein.

Was ich da machen würde:
Eine kleine Methode check, die ein int übergeben bekommt und prüft,
ob der Key vom Node (wo es aufgerufen wurde) inkl beider Teilbäume
rekursiv kleiner als diese Zahl sind:
(returnt zB. -1 wenn alle kleiner ist, +1 wenn alles größer ist, und 0 für Fehler)
Java:
protected int check(int testkey) {
    if(this.key < testkey
        && (left == null || left.check(testkey) < 0)
        && (right == null || right.check(testkey) < 0))
        return (-1);
    if(this.key > testkey
        && (left == null || left.check(testkey) > 0)
        && (right == null || right.check(testkey) > 0))
        return 1;
    return 0;
}
Im Konstruktor dann als einzige Prüfung diese Methode für lft und right aufrufen
(jeweils wenn nicht null). Der Durchgang von left muss <0 sein, der von right >0.
Sonst eben Exception.

----------------------------------
get schaut gut aus :)

Und zu insert (Vermutung: Baum muss nicht balanciert sein):
Idee ok, aber du machst es dir zu kompliziert.
Der erste Teil (wenn this.key == thatkey dann ersetze value) ist in Ordnung
(außer, dass du in dem Fall dann mit der Funktion schon fertig bist,
also den Code weiter unten nciht mehr ausführen).

Zu dem "weiter unten":
Die passende Einfügestelle suchen etc. wäre zwar nicht falsch,
kann man sich aber viel einfacher machen:
Zuerst prüfen, ob der key größenmäßig links oder rechts sein sollte,
und dann dem jeweiligen Kindknoten das Ganze einfach überlassen... (insert davon aufrufen)

Zumindest hat man so die "Key schon vorhanden, Value ersetzen"-Fälle abgedeckt.
Mit einer kleinen Änderung machts auch die Neu-Einfügungen:
insert vom Kindknoten kann ja nur aufgerufen werden wenn der nciht null ist.
Biser wurde im null-Fall einfach nichts gemacht, jetzt aber
kann man einen "leeren" Knoten (so wie dein tmp) dort einfügen
und dann trotzdem insert aufrufen.
->Man hat einen Knoten mit dem key erzeugt, und das value wird rein "ersetzt"...
alles in Ordnung

@Fasibio, nur ganz kurz: Du hast nichts verstanden.
 

Fasibio

Mitglied
Ja doch hab schon verstanden...
musste es nur erstmal selber machen befor ich helfen konnte und da ist es mir halt aufgefallen.
;)
 

julia123

Erfahrenes Mitglied
ja, bin auch davon ausgeganen dass wenn man nur die Kinder betrachtet dass dadurch alles abgedeckt wird.
Hab dass dann entsprechen so angepasst :

Bin mir bei der Realisierung besonders in der letzten Spalte (13-14) unsicher.
 
Zuletzt bearbeitet:

sheel

I love Asm
Kontruktor passt, beim insert meinte ich sowas (Code nur für Links):
Java:
if (key < this.key) {
    if(left == null) {
        left = new Node(key, null, null, null);
    }
    left.insert_Methode(key, value);
}
Oder, ganz gleichbedeutend:
Java:
if (key < this.key) {
    if(left == null) {
        left = new Node(key, null, null, value);
    }
    else {
        left.insert_Methode(key, value);
    }
}
Das Selbe auch noch für Rechts.
 
Zuletzt bearbeitet:

julia123

Erfahrenes Mitglied
ok danke, hab dass ganze implementiert:

Müsste rightig sein. Jetzt müsste ich ja mit diesen Methoden sollch ein Baum wie oben in der Abbildung basteln können.

Java:
public class BinTree {
       public class Node{

                //alle Methode,Konstruktor ....

        }
public static void main(String[] args) {

		
		Node baum = new Node (4,null,null,null);
		baum.insert_Methode(3, null);
		baum.insert_Methode(2, null);
		baum.insert_Methode(1, null);
		baum.insert_Methode(0, null);
		
	}
}

In Zeile 10 tritt dieser Fehler auf :
No enclosing instance of type BinTree is accessible. Must qualify the allocation with an enclosing instance of type
BinTree (e.g. x.new A() where x is an instance of BinTree).

Die Main muss doch in der BinTree class sein ? Ich glaube ich stell mich doof an :( . Wie soll ich das sonst initialisieren.
Hab das mal so versucht auch ohne Erfolg. Was ich nicht verstehe wieso der Compiler hier nicht aufspringt und mir sagt dass
ich baum2 initialisieren muss (new).
Java:
public static void main(String[] args) {

				
		Node baum2 = null;
		baum2.insert_Methode(4, null);
		baum2.insert_Methode(3, null);
		baum2.insert_Methode(2, null);
		baum2.insert_Methode(1, null);
		baum2.insert_Methode(0, null);
	}
 
Zuletzt bearbeitet:

sheel

I love Asm
Also, zum insert noch ein letztes Mal:
Sorry, hab schon wieder einen Schlampigkeitsfehler gemacht :/
Ist oben ausgebessert.

Zum Fehler: Wenn man nicht weiß warum, dann besser keine Klassen in andere Klassen packen.
Node kann (sollte) wie BinTree komplett eigenständig sein.