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

 

[Ruzmanz]

Im groben:

currentNode = root;
for(Character c: inputString) {
  // Wenn der aktuelle Knoten das relevante Zeichen enthält
  if(currentNode.getChild(c) != null) {
    // Gehe eine ebene Tiefer
    currentNode = currentNode.getChild(c);
  } else {
    // Füge restliche Zeichen an die currentNode an
  }
}

 

[Midorima]

Erstmal vielen dank für die schnelle Antwort !
Und für Löschen der Wörter mache ich es invers oder täusche ich mich da?

 

[Ruzmanz]

Ja, irgendwie so.

currentNode = lastNode;
if(currentNode.getChildren().size() == 0) {
  currentNode = currentNode.getParent();
  currentNode.getParent().removeChild(currentNode.getChar());
}

 

[Midorima]

hmm ok danke für die Hilfe.
Jetzt fehlen nur noch ausgeben und finden.

Beim finden sollen alle Teilbäume des Wortes die den gleichen Präfix haben wiedergegeben werden. Also muss die Methode rekursiv(?) das Wort von hinten nach vorne kürzen und alle Abzweigungen mitnehmen. Oh Gott das klingt ja vielleicht mal kompliziert???:L

Und finden dazu verstehe ich den zweiten Teil der Aufgabe nicht :Implementieren Sie die Methode TextTree::find(), die ein gegebenes Wort im Baum sucht und, falls vorhanden, das korrespondierende Node Objekt des Knotens, an dem das gesuchte Wort endet, zurückgibt.

Heißt das, dass ich das Wort suche und danach alles sozusagen auf altsetze, als wäre nichts geschehen?

 

[Ruzmanz]

find: Du gehst die Character von deinem Wort schrittweise durch und gibst die Node zurück, bei der es endet. Wenn das Wort nicht gefunden wurde, dann null.
printWordsRecursive(String word): Du kopierst die Funktionsweise von "printRecursive" und setzt vor der Ausgabe System.out.println(word + XYZ).

 

[Midorima]

Heißt das für find muss ich eine for-Schleife durchlassen für jeden Character wenn nichts übereinstimmt dann halt null und sonst halt zurückgegeben. Aber wie schreibe ich es in einen Java Code?