Binärer Suchbaum

[Marcel_Buchner]

Hi erstmal ! Ich lerne grade ObjektOrientierte Programmierung und habe eine Übung bei der ich nicht weiterkomme. Unzwar soll ich einen binären SuchBaum als Datenstruktur zur Speicherung von Int-Werten implementieren. Die Haupteigenschaft ist, dass alle Elemente des linken Unterbaumes kleiner, alle Elemente des rechten Unterbaumes größer (oder – falls per Definition erlaubt – gleich) als das Objekt im aktuellen Knoten sein müssen. Ich selber verstehe nicht wie ich die Methoden für getparent, ToArray, PostOrder und PreOrder. Könnte mir jemand helfen wie ich diese Methoden schreiben muss ? Im Anhang habe ich Bilder meines bisher vorhandenen Codes. Schon mal vielen Dank im Vorraus

Hier das Beispiel:
public class BinarySearchTree {
/** Inner class for the binary tree node. **/
protected class BinaryTreeNode
{
public BinaryTreeNode left;
public BinaryTreeNode right;
public int data;
public BinaryTreeNode (int elem)
{
data = elem;
left = null;
right = null;
} }
/** Root node of the tree. **/
protected BinaryTreeNode root;
/** Number of elements stored in the tree. */
protected int size;
/** Inserts the given element. Duplicate elements are not allowed. Returns true if insertion was successful, false otherwise. */
public boolean insert (int elem) { ... }
/** Searches for the (first) element with the given key. Returns true if it could be found, false otherwise. */
public boolean find (int key) { ... }
/** Removes the element with the given key. Returns true if the key could be found (and removed), false otherwise. */
public boolean remove (int key) { ... }
/** Returns the number of elements stored in the tree. */
public int size () { ... }
/** Returns the parent element of the given key. Integer.MIN_VALUE if no parent can be found. */
public int getParent(int key) { ... }
/** Returns the elements of the tree in ascending (inorder traversal) or descending (reverse inorder traversal) order. */
public int[] toArray (boolean ascending) { ... }
/** Returns the elements of the tree (postorder traversal). */
public int[] toArrayPostOrder() { ... }
/** Returns the elements of the tree (preorder traversal). */
public int[] toArrayPreOrder() { ... }
/** Returns largest number stored in the tree. Integer.MIN_VALUE if no largest element can be found*/
public int max () { ... }
/** Returns smallest number stored in the tree. Integer.MIN_VALUE if no smallest element can be found */
public int min () { ... }
/** Represents the tree in a human readable form. */
public String toString() { ... }
}

Mit freundlichen Grüßen Marcel

 

[Marcel_Buchner]

[CODE lang="java" title="BinarySearchTree"]public class BinarySearchTree {
/** Inner class for the binary tree node. **/
protected class BinaryTreeNode
{
public BinaryTreeNode left;

public BinaryTreeNode right;
public int data;
public BinaryTreeNode (int elem)
{
data = elem;
left = null;
right = null;
}
}
/** Root node of the tree. **/
protected BinaryTreeNode root;
/** Number of elements stored in the tree. */
protected int size;
/** Inserts the given element. Duplicate elements are not allowed. Returns true if insertion was successful, false otherwise. */
public boolean insert(int elem)
{
if(root == null)
{
return false;
}
else
{
this.root = insert(root, elem);
return true;
}
}
public BinaryTreeNode insert(BinaryTreeNode root,int elem)
{
if (root.data >= elem) //Checkt ob root data größer oder gleich elem ist
{
root.left = insert(root.left, elem); // Wenn ja geht elem zum linken sub-tree
}
else
{
root.right = insert(root.right, elem); // Wenn kleiner geht elem zum rechten sub-tree
}
return root;
}



/** Searches for the (first) element with the given key. Returns true if it could be found, false otherwise. */
public boolean find(int key)
{
if(key == 0)
{
return false;
}
return search(root,key);
}
private boolean search(BinaryTreeNode root, int key) {

if (root.data == key) {
return true;
} else if (root.data > key) {
return search(root.left, key);
}
return search(root.right, key);
}
/** Removes the element with the given key. Returns true if the key could be found (and removed), false otherwise. */
public boolean remove(int key)
{
if(key == 0)
{
return false;
}
return true;
}

/** Returns the number of elements stored in the tree. */
public int size()
{
return size;
}
/** Returns the parent element of the given key. Integer.MIN_VALUE if no parent can be found. */
public int getParent(int key)
{
if(key == 0)
{
return Integer.MIN_VALUE;
}
return key;
}
/** Returns the elements of the tree in ascending (inorder traversal) or descending (reverse inorder traversal) order. */
public int[] toArray (boolean ascending)
{
return null;
}
/** Returns the elements of the tree (postorder traversal). */
public int[] toArrayPostOrder()
{
if(root == null)
{

}
return 0;
}
/** Returns the elements of the tree (preorder traversal). */
public int[] toArrayPreOrder()
{

}
/** Returns largest number stored in the tree. Integer.MIN_VALUE if no largest element can be found*/
public int max ()
{
if (root == null)
{
return Integer.MIN_VALUE;
}
BinaryTreeNode current = this.root;
while (current.right != null) {
current = current.right;
}
return (current.data);
}
/** Returns smallest number stored in the tree. Integer.MIN_VALUE if no smallest element can be found */
public int min()
{
if(root == null)
{
return Integer.MIN_VALUE;
}
BinaryTreeNode current = this.root;
while (current.left != null) {
current = current.left;
}
return (current.data);
}

/** Represents the tree in a human readable form. */
public String toString()
{

}

}


[/CODE]

 

[KonradN]

Wenn diese Forderung gegeben ist:

Die Haupteigenschaft ist, dass alle Elemente des linken Unterbaumes kleiner,

Ist der Code schon einmal falsch:

    if (root.data >= elem)  //Checkt ob root data größer oder gleich elem ist
    {
        root.left = insert(root.left, elem); // Wenn ja geht elem zum linken sub-tree
    }

Und dieser Code sieht auch dubios aus:

public boolean find(int key)
{
    if(key == 0)
    {
    return false;
    }

Ich denke nicht, dass dies so richtig ist. Evtl. mal bei anderen Methoden schauen, was da so geprüft wird.


Zu der eigentlichen Frage:

Ich selber verstehe nicht wie ich die Methoden für getparent, ToArray, PostOrder und PreOrder.

Erst einmal aufteilen. Das sind 4 Methoden, die Du schreiben sollst. Die würde ich immer der Reihe nach angehen also immer nur auf ein Thema begrenzt arbeiten.

Dann ist das Vorgehen immer gleich:
Überlege Dir immer erst das Vorgehen. Dabei vergisst Du java! Mal Dir einen Suchbaum auf und überlege Dir, die Du da die Aufgaben der einzelnen Methoden manuell machen kannst und was für Fälle es dabei gibt, die zu beachten sind. Beschreibe Das Vorgehen dann so, dass jeder, der die eigentliche Aufgabe nicht kennt mit einem Suchbaum und Deiner Beschreibung zu dem gewünschten Ergebniss kommen würde.

Also nehmen wir die erste Methode: Wie könntest Du zum Parent Element kommen? Wie gehst Du da vor?

 

[Marcel_Buchner]

Wenn diese Forderung gegeben ist:

Ist der Code schon einmal falsch:

    if (root.data >= elem)  //Checkt ob root data größer oder gleich elem ist
    {
        root.left = insert(root.left, elem); // Wenn ja geht elem zum linken sub-tree
    }

Und dieser Code sieht auch dubios aus:

public boolean find(int key)
{
    if(key == 0)
    {
    return false;
    }

Ich denke nicht, dass dies so richtig ist. Evtl. mal bei anderen Methoden schauen, was da so geprüft wird.


Zu der eigentlichen Frage:

Erst einmal aufteilen. Das sind 4 Methoden, die Du schreiben sollst. Die würde ich immer der Reihe nach angehen also immer nur auf ein Thema begrenzt arbeiten.

Dann ist das Vorgehen immer gleich:
Überlege Dir immer erst das Vorgehen. Dabei vergisst Du java! Mal Dir einen Suchbaum auf und überlege Dir, die Du da die Aufgaben der einzelnen Methoden manuell machen kannst und was für Fälle es dabei gibt, die zu beachten sind. Beschreibe Das Vorgehen dann so, dass jeder, der die eigentliche Aufgabe nicht kennt mit einem Suchbaum und Deiner Beschreibung zu dem gewünschten Ergebniss kommen würde.

Also nehmen wir die erste Methode: Wie könntest Du zum Parent Element kommen? Wie gehst Du da vor?

Mein Parent ist ja ein Knoten der links und rechts wieder auf zwei Knoten zeigt zeigt. Ich müsste also abfragen ob der linke oder der rechte Knoten so groß wie der "Key" wäre. Wenn einer der Knoten so groß wie der Key ist dann ist der Hauptknoten mein Parent oder?

 

[KonradN]

Mein Parent ist ja ein Knoten der links und rechts wieder auf zwei Knoten zeigt zeigt. Ich müsste also abfragen ob der linke oder der rechte Knoten größer wären. Wenn keiner davon größer wäre würde ich ja meinen Parent Punkt haben oder ?

Das ist so irgendwie nicht wirklich zu verstehen. Was bitte zeichnet den Parent Knoten eines Knotens genau aus?

 

[Marcel_Buchner]

Das ist so irgendwie nicht wirklich zu verstehen. Was bitte zeichnet den Parent Knoten eines Knotens genau aus?

Der Hauptknoten des linken und rechte Knoten. Wenn dann einer dieser beiden Knoten gleich dem Node ist. Habe ich meinen Parent. Also sagen wir haben einen Knoten mit 3 der spaltet sich links und rechts auf mit 2 und 5. Mein Node ist 5. Da dieser einer der beiden Knoten von 3 ist, ist mein Parent 3. Oder habe ich da was missverstanden

 

[KonradN]

Prinzipiell richtig, aber Du Fokusierst Dich zu sehr auf Werte.
a) Der Wert 5 kann aber doch mehrfach vorkommen.
b) Es geht hier doch um Knoten.

Aber prinzipiell ist es richtig, wenn Du statt auf die Werte auf die Knoten gehst:
Ein Knoten ist der Parent Knoten, wenn der linke oder rechte Unterknoten = dem gegebenen Knoten ist.

Da wäre also eine Abschluss-Bedingung. Die Frage wäre jetzt: Wie finde ich in dem Baum den Parent Knoten? Wie gehst Du da vor?

 

[Marcel_Buchner]

Prinzipiell richtig, aber Du Fokusierst Dich zu sehr auf Werte.
a) Der Wert 5 kann aber doch mehrfach vorkommen.
b) Es geht hier doch um Knoten.

Aber prinzipiell ist es richtig, wenn Du statt auf die Werte auf die Knoten gehst:
Ein Knoten ist der Parent Knoten, wenn der linke oder rechte Unterknoten = dem gegebenen Knoten ist.

Da wäre also eine Abschluss-Bedingung. Die Frage wäre jetzt: Wie finde ich in dem Baum den Parent Knoten? Wie gehst Du da vor?

Hmm ich würde wohl mal schauen wo ich überall den ParentKnoten habe, Wenn bei auf der linken Seite sind würde ich wohl den ersten nehmen den ich finden würde. Bei beiden Seiten weiss ich es um ehrlich zu sein nicht

 

[Staarfightaar]

getparent ist schon mal eins anzumekren

ein node braucht nicht wissen was sein parent ist
witzigerweise ist das bei rekursion durch nen baum schon "gegeben" wenn man dahinter steigt
zb du hast den baum der nur nach links geht
node(10) node(8) node(7) node(5) als werte
und du willst den parent

du latscht rein Rekursiv ( ich bezieh mich nur auf links )

public Node getParent(SUCHWERT){
   
    /// hier fehlt überprüfung ob man links oder rechts weiter suchen soll
    /// auf basis von dem ergebnis kannst du entscheiden was für wenns du
    /// von unten prüfen msust
   
    // wenn der linke unter knoten den wert beinhalten muss
    // und der linke den wert hat dann return mich als parent
    WENN( linke.node.data GLEICH SUCHWERT) return this;
    // wenn der linke aber leer ist, also null
    // aber im baum NUR da der knoten sein kann
    // heißt das dass es den wert nicht gibt
    // dh es gibt auch keinen parent .. also null als parent
    WENN( linke.node.data GLEICH null) return null
}

der trick besteht drinnen nicht zu tief in den baum rein zu latschen mit rekursion

 

[KonradN]

Hast Du Dir das denn mal auf einem Zettel etwas aufgemalt? Du hast einen Baum. Von mir aus oben erst eine 5.
Da hast Du dann links und Rechts 3 und 10
An der 10 hast Du die 7 und 15

Jetzt hast Du nur den Baum selbst (also die root Referenz, die auf den knoten mit der 5 Zeigt) und Du willst den Parent von der 15 haben.
Wie kannst Du nun durch den Baum gehen? Was machst Du genau, um den Parent Knoten zu finden?

Es ist wirklich wichtig, sich das aufzuzeichnen um damit dann alles durchzugehen. Als reine Gedankenübung führt es zu nichts!

 

[Marcel_Buchner]

Ich frage zuerst ob 5 schon der Werr ist den ich suche. Falls nicht gehe ich links und rechts auch die Knoten und überprüfe diese ob sie der gewünschte Wert sind. Wenn ich dann an der 15 angekommen bin, kann ich sagen dass mein vorheriger Wert mein Parent Note ist.

 

[KonradN]

5 schon der Werr ist den ich suche

Nein, Du schaust, ob der Knoten der gesuchte Knoten ist! Ein Wert kann ja mehrfach vorkommen!

Falls nicht gehe ich links und rechts

Du gehst links und rechts? Hast Du keine Möglichkeit zu bestimmen, in welchem Teilbaum dein gesuchter Knoten sein muss? Das solltest Du genau angeben.