witch doctor Geschrieben 31. August 2003 Geschrieben 31. August 2003 Wir haben mal folgende Aufgabe in Informatik erhalten: Programmieren Sie in der Klasse MyTreeMap die Operation public boolean containsValue(Object o), die überprüft, ob der Baum ein zu o inhaltsgleiches Objekt als Werte-Objekt enthält. Hinweis: Um festzustellen, ob ein vorgegebener Wert in einem Suchbaum enthalten ist, müssen im Extremfall alle Knoten des Baumes durchlaufen werden. Hierzu das zu bearbeitende Programme /** * Implementierung eines binären Suchbaums * * Beachte: * Der Suchbaum ist kein ausgeglichener Baum. * Er kann durch Einfüge- und Löschoperationen zu einer * linearen Liste entarten. * * Die gespeicherten Objektreferenzen für Werte dürfen * nicht gleich null sein. * */ package TreePackage; public class MyTreeMap { /** * Innere Klasse für die Knoten des binären Sucbaumes */ class Node { // Attribute Comparable key; // Verweis auf Schlüssel-Objekt Object value; // Verweis auf Wert-Objekt Node left; // Verweis auf linken Kindknoten Node right; // Verweis auf rechten Kindknoten // Konstruktor Node(Comparable key, Object value) { this.key = key; this.value = value; this.left = null; this.right = null; } } // Attribute (Klasse MyTreeMap) private Node root; // Verweis auf Wurzelknoten des Binärbaumes private int size; // Anzahl der Knoten des Binärbaumes // Konstruktor (Klasse MyTreeMap) /** * Erzeugung eines leeren Binärbaums */ public MyTreeMap() { this.root = null; this.size = 0; } // Operationen (Klasse MyTreeMap) /** * Bestimmung der Anzahl der Knoten im Binärbaum */ public int size() { return this.size; } /* * Bestimmung eines Knotens, der einen vorgegebenen Schlüssel enthält * mit Hilfe eines rekursiven Algorithmus * Die Operation setzt voraus, dass key ungleich null ist. */ private Node getNodeRec(Comparable key, Node tree) { Node result; if (tree==null) // Baum ist leer result = null; else { int cmp = key.compareTo(tree.key); if (cmp==0) // Knoten ist gefunden result = tree; else if(cmp<0) // Suchen im linken Teilbaum result = getNodeRec(key, tree.left); else // Suchen im rechten Teilbaum result = getNodeRec(key, tree.right); } return result; } /* * Bestimmung eines Knotens, der einen vorgegebenen Schlüssel enthält * mit Hilfe eines iterativen Algorithmus * Die Operation setzt voraus, dass key ungleich null ist. */ private Node getNodeIt(Comparable key, Node tree) { Node result; result = null; Node VergleichsNode = tree; int cmp = key.compareTo(VergleichsNode.key); boolean nochwaszutun = true; //Hilfsvariable für die Schleife if(this.root==null)//Baum ist leer {} else { /** * Solange nochwaszutun=true ist führt er die Schleife aus * Er vergleicht nach und nach die Knoten. * Ist der Schlüssel sofort am Anfang 0, ist die Wurzel * der gesuchte Knoten. * * Nach dem gleichen Verfahren wird im rechten und linken * Teilbaum verfahren. * * Ist nochwaszutun=false bricht die Schleife ab. */ while(nochwaszutun) { if(cmp==0) //gefunden!! { result = VergleichsNode; nochwaszutun=false; } if(cmp<0) //Suche im linken Teilbaum falls dieser existiert //ansonsten bricht er ab { if(VergleichsNode.left==null) { nochwaszutun=false; } else { VergleichsNode=VergleichsNode.left; } } if(cmp>0) //Suche im rechten Teilbaum falls dieser existiert //ansonsten bricht er ab { if(VergleichsNode.right==null) { nochwaszutun=false; } else { VergleichsNode=VergleichsNode.right; } } } } // Hier Lösung einfügen return result; } /** * Bestimmung des Wertes zu einem vorgegebenen Schlüssel */ Object get(Comparable key) { Object result = null; if (key!=null) { Node p = getNodeIt(key, this.root); if (p!=null) result = p.value; } return result; } /** * Überprüfung, ob ein zu o inhaltsgleiches Objekt als Werte-Objekt * enthalten ist */ boolean containsValue(Object o) { boolean result=false; [color=red]//Hier Lösung einfügen [/color] } /* * Rekursives Verfahren zum Einfügen eines Paares (key,value) * in den Binärbaum mit dem Wurzelknoten tree. * Ist der Schlüssel key schon vorhanden, wird der alte * Wert durch den Wert value ersetzt. * Als Ergebnis wir ein Baum zurückgeliefert, der das * Paar (key, value) enthält. */ private Node insertNode(Comparable key, Object value, Node tree) { if (tree==null) { // Neuen Knoten erzeugen tree = new Node(key, value); this.size++; } else { int cmp = key.compareTo(tree.key); if (cmp==0) { // Alter Wert wir durch neuen Wert ersetzt tree.value = value; } else if(cmp<0) // Einfügen im linken Teilbaum tree.left = insertNode(key, value, tree.left); else // Einfügen im rechten Teilbaum tree.right = insertNode(key, value, tree.right); } return tree; } /** * Einfügen eines Paares (key,value) in den Binärbaum * Ist der Schlüssel key schon vorhanden, wird der alte * Wert durch den Wert value ersetzt. */ void put(Comparable key, Object value) { if (key!=null && value!=null) this.root = insertNode(key, value, this.root); } /* * Bestimmung des Elternknotens des symmetrischen Nachfolgers * des Knotens tree * * Der symmetrische Nachfolger eines Knotens, ist der Knoten * mit dem kleinsten Schlüssel, der größer als der Schlüssel * des Knotens tree ist. * Dieser ist der am weitesten links stehende Knoten im rechten * Teilbaum des Knotens tree. */ private Node parentSymSucc(Node tree) { Node result; result = tree; if (result.right.left!=null) { result = result.right; while (result.left.left!=null) result = result.left; } return result; } /* * Rekursives Verfahren zum Entfernen eines Knotens zu einem * vorgegebenen Schlüssel im Binärbaum mit dem Wurzelknoten tree. * Als Ergebnis wir ein Baum zurückgeliefert, der den Schlüssel * key nicht mehr enthält. */ private Node removeNode(Comparable key, Node tree) { if (tree!=null) { int cmp = key.compareTo(tree.key); if (cmp<0) // Entfernen im linken Teilbaum tree.left = removeNode(key, tree.left); else if (cmp>0) // Entfernen im rechten Teilbaum tree.right = removeNode(key, tree.right); else { // zu entfernender Knoten gefunden this.size--; if (tree.left==null) tree = tree.right; // Fall 1: siehe Skript else if (tree.right==null) tree = tree.left; // Fall 2: siehe Skript else { // Knoten besitzt zwei Kindknoten Node p = parentSymSucc(tree); if (p==tree) // Fall 3: siehe Skript { tree.key = p.right.key; tree.value = p.right.value; p.right = p.right.right; } // Fall 4: siehe Skript else { tree.key = p.left.key; tree.value = p.left.value; p.left = p.left.right; } } } } return tree; } /** * Entfernen eines Eintrags im Binärbaum zu einem vorgegebenen Schlüssel */ void remove(Comparable key) { if (key!=null) this.root = removeNode(key, this.root); } /* * Rekursives Verfahren zur Ausgabe der Paare (Schlüssel,Wert) * sortiert nach aufsteigender Reihenfolge der Schlüsseln * durch einen Inorder-Durchlauf durch den Binärbaum */ private void inorderPrint(Node tree) { if (tree!=null) { inorderPrint(tree.left); System.out.println("("+tree.key+","+tree.value+")"); inorderPrint(tree.right); } } /** * Ausgabe der Paare (Schlüssel,Wert) sortiert nach aufsteigender * Reihenfolge der Schlüssel */ void print() { System.out.println("Liste der Einträge"); System.out.println("------------------"); inorderPrint(this.root); System.out.println(); } } Um an das inhaltsgleiche Objekt zu kommen habe ich folgendes programmiert, welches leider immer nur die ersten beiden, also die Wurzel und das Objekt danach finden. Ich denke der Fehler liegt im Detail. Hier meine Programmierung: private Node ersternode() { return this.root; } boolean containsValue2(Object o, Node tree) { boolean result=false; if(tree!=null) { containsValue2(o,tree.left); /** * Ist das Objekt links vorhanden?? */ if(tree.value.equals(o)) { result=true; } containsValue2(o,tree.right); /** * Ist das Objekt rechts? */ } return result; } boolean containsValue(Object o) { boolean result = false; Node tree=this.ersternode(); result=containsValue2(o,tree); return result; // Hier Lösung einfügen } Er läfut also von links nach rechts. Nur leider durchläuft er nicht jeden Knoten. Rude ich es im Hauptprogramm auf, findet er nur die ersten beiden. Zur Illustration hier das Hauptprogramm: Zitieren
witch doctor Geschrieben 31. August 2003 Autor Geschrieben 31. August 2003 package baum; import java.io.*; class TreeTest { public static void main(String[] args) { MyTreeMap dictionary = new MyTreeMap(); dictionary.put("node", "Knoten"); dictionary.put("tree", "Baum"); dictionary.put("root", "Wurzel"); dictionary.put("left", "links"); dictionary.put("right", "rechts"); System.out.println(dictionary.size()); System.out.println("Engl.: "+"root"+" Dt.: "+dictionary.get("root")); System.out.println("Engl.: "+"node"+" Dt.: "+dictionary.get("node")); System.out.println("Engl.: "+"bla"+" Dt.: "+dictionary.get("bla")); dictionary.print(); if(dictionary.containsValue("Wurzel")) { System.out.print("Der Baum enthält diesen Wert \n"); } else { System.out.print("\n Wert nicht vorhanden \n"); } dictionary.remove("tree"); System.out.println(dictionary.size()); dictionary.print(); } } Das Wort "Wurzel" findet er. Sobald ich aber zB das Wort links angebe, findet er es nicht, obwohl es vorhanden. Wo ist der Fehler? Ich habe noch eine andere Lösung. Doch ich denke,dass diese noch falscher ist: boolean containsValue(Object o) { boolean result = false; Node tree=this.root; if(tree.value.equals(o)) { result=true; } if(tree.left.value.equals(o)) { result=true; } if(tree.right.value.equals(o)) { result=true; } return result; // Hier Lösung einfügen } Ich wäre für Hilfe sehr dankbar, da ich den Fehler nciht sehe. Wie durchlaufe ich denn am Besten einen Baum? Mit einer for Schleife? Nur mit welchen Werten? Ich danke euch bereits für eure Hilfe! Zitieren
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.