Algorithmen und Datenstrukturen

[Midorima]

Moin moin Freunde der Sonne !

ich bin ein absoluter Anfänger in Java und nun soll ich für meine Vorlesung, einen Java-Code implementieren?!

Ich weiß gar nicht wie ich anfangen sollte und wollte im Forum mal um Hilfe fragen, denn der Übungsleiter meinte, dass die Methode nur einige Zeilen lang sein soll :idea:

Also nun zur vermeintlich schwersten Aufgabe für mich. ( für euch bestimmt ein Fingerklacks :Applaus

Kurz gesagt ist es ein kantenbeschrifteter Baum, in dem man Wörter hinzufügen, löschen, suchen und ausgeben soll.Den Code an sich verstehe ich und was die Methoden machen sollen.
Beim Hinzufügen würde ich erst prüfen ob das Wort ein Präfix vom anderen vorhandenen Wort vorhanden ist, sollte es nicht der fall sein . zb an diesem Baum
- T - e - s - t*- 1 - 2 - 3 - 4*
* \ e - s*
* \ r*
* \ n*
* \ a - g*
Der Baum hat Test,Test1234, Tester etc. würde also z.B Tee hinzugefügt werden sollen, müsste die Methode beim ersten e verzweigen sprich ein Knoten würde am e hinzugefügt werden. Jedoch wie implementiere ich dies in Java?

Ich würde mich über jede Hilfe und Tipps freuen

hier unten ist der schon vorgegebene Code :

public class TextTree
{
	private Node root = new Node(null,'@'); // Root node of the text tree

	/**
	 * Add the given word to the text tree.
	 */
	public void add(String word)
	{
		// ToDo: Aufgabe 3a)
	}

	/**
	 * Determine if the given word is contained in the text tree.
	 */
	public boolean contains(String word)
	{
		return (find(word) != null);
	}

	/**
	 * Search the text tree for the given word.
	 * @return the Node object representing the word,
	 *         or null if the word is not contained in the tree.
	 */
	private Node find(String word)
	{
		// ToDo: Aufgabe 3b)
		return null;
	}

	/**
	 * Remove the given word from the text tree, if contained.
	 * Also remove leaf nodes that do not represent a word any more.
	 */
	public void remove(String word)
	{
		// ToDo: Aufgabe 3c)
	}

	/**
	 * Print a list of all words in the text tree.
	 */
	public void printWords()
	{
		root.printWordsRecursive("");
	}

	/**
	 * Print a pseudo-graphical representation of the text tree.
	 */
	public void print()
	{
		root.print();
	}

	/**
	 * Main method with a simple test case for the text tree.
	 */
	public static void main(String[] args)
	{
		TextTree tt = new TextTree();
		tt.add("Test1234");
		tt.add("Testen");
		tt.add("Tag");
		tt.add("Test");
		tt.add("Tester");
		tt.add("Testes");
		tt.print();
		check(tt,"Tor",false);
		check(tt,"Tag",true);
		check(tt,"",false);
		check(tt,"ag",false);
		check(tt,"Testen",true);
		check(tt,"Test12345",false);
		check(tt,"Test",true);
		tt.printWords();
		tt.remove("Tester");
		tt.remove("Test1234");
		tt.print();
		check(tt,"Testen",true);
		check(tt,"Tester",false);
		check(tt,"Tag",true);
		check(tt,"Test1234",false);
		check(tt,"Test",true);
	}

	private static void check(TextTree tt,String s,boolean correctResult)
	{
		if ((tt.find(s) != null) == correctResult)
			System.out.println("CORRECT: Tree "+(correctResult?"contains ":"does not contain ")+s+".");
		else System.out.println("ERROR: "+s+" is falsely reported as "+(correctResult?"not contained.":"contained."));
	}
}

/**
 * A Node object represents one node in the text tree.
 */
class Node
{
	private Node parent;
	private char c;
	private Map<Character,Node> children;
	private boolean bWordEnds;

	Node(Node parent,char c)
	{
		this.parent = parent;
		this.c = c;
		children = new HashMap<Character,Node>();
	}

	void addChild(Character c,Node child)
	{
		children.put(c,child);
	}

	void removeChild(Character c)
	{
		children.remove(c);
	}

	Node getChild(Character c)
	{
		return children.get(c);
	}

	Node getParent()
	{
		return parent;
	}

	void setWord()
	{
		bWordEnds = true;
	}

	void removeWord()
	{
		bWordEnds = false;
	}

	boolean isWord()
	{
		return bWordEnds;
	}

	char getChar()
	{
		return c;
	}

	boolean hasChildren()
	{
		return !children.isEmpty();
	}

	void print()
	{
		printRecursive(0,true);
	}

	private void printRecursive(int level,boolean bFirst)
	{
		if (level > 0)
		{
			if (bFirst) System.out.print("- ");
			else {
				for (int i = 0; i < level-1; i++) System.out.print("    ");
				System.out.print("\\ ");
			}
			System.out.print(c+(bWordEnds?"*":" "));
		}
		bFirst = true;
		for (Map.Entry<Character,Node> entry: children.entrySet())
		{
			entry.getValue().printRecursive(level+1,bFirst);
			bFirst = false;
		}
		if (children.isEmpty()) System.out.println();
	}

	/**
	 * Recursively print out all words represented by the subtree
	 * consisting of the current node and all its descendants.
	 * @param word Prefix of the word represented by this node.
	 */
	void printWordsRecursive(String word)
	{
		// ToDo: Aufgabe 3d)
	}
}

 

[eMmiE]

Hi,

ist dein Problem rein Codetechnisch oder eher in Richtung "Wie funktionieren diese Bäume?"?

Vom Prinzip her musst du, angefangen von der Wurzel (-> Der "Node" mit char '@' ohne "Parent") zu überprüfen, ob der nächste Character bei den "Children" enthalten ist.

Das kannst du recht einfach mit der Methode getChild() machen.
Wenn der Rückgabewert null ist oder eine Exception geworfen wurde (weiß ich jetzt grad nicht genau, wie das bei Map so ist), dann ist der "Node" nicht bei den "Children" und du musst ihn mithilfe von addChild() einfügen.

Immer beachten, dass du wenn du mit dem Baum arbeitest immer den "Node" als Variable hast, den du gerade bearbeitest (So kannst du dann einfach addChild(Character, n) machen, um etwas einzufügen)

Ausserdem solltest du immer den nächsten char schon bereithalten ->

char use =  (char) string.substring(index,index+1);

Mach das Ganze einfach iterativ mit ner for-Schleife durch den ganzen String...

Gruß eMmiE

 

[Midorima]

Mein Problem ist rein Codetechnisch, da ich erst im nächsten Semester Grundlagen der Programmierung belege bzw. mich dann erst mit Java beschäftige. Leider war es eine schlechte Idee für Algorithmen und Datenstrukturen, wie ich bemerkt habe.
Den Baum bzw wie ein Baum funktioniert, habe ich verstanden, jedoch fehlt mir das Verständnis für die Programmierung bzw für die Codierung.

Das habe ich dann soweit und wie finde ich das entsprechende Wort? Sprich ich laufe von der Wurzel und checke ob es mit dem Char übereinstimmt wenn ja laufe weiter wenn nicht dann gehe zurück. Bloß wie sieht das im Code aus?
Gruß Midorima

 

[eMmiE]

Das ist jetzt mein Code, nicht die Musterlösung und vllt. nichtmal richtig

String in = ""; //Dein String
char[] array = in.toCharArray(); //Damit wir es dann leichter haben mit dem Überprüfen

Node work = this.root; //this bezogen auf TextTree
boolean vorhanden = true;

for (int i = 0;i < array.length;i++) {
if (enthält(work,array[i])) {
System.out.println("Ein weiterer Buchstabe enthalten: "+array[i]);
work = work.getChild(array[i]);
} else {
System.out.println("Wort nicht enthalten");
vorhanden = false;
break; //Bricht die Schleife ab
}
}

Das sollte funktionieren

Methode enthält(Node n,char c)

return (n.getChild(c) != null);

Das soll jetzt so funktionieren, dass die Map dir nichts (null) zurückgibt, wenn der Knoten mit char c nicht vorhanden ist

Ich persönlich habe es eigentlich lieber, wenn ich Listen iterativ durchsuchen darf.
Hoffe das klappt

Gruß eMmiE