Multiway Tree

[ray3002]

Guten Morgen zusammmen, ich sitze nu schon seit ein paar Tagen an einem Problem, auf dessen Lösung ich nicht komme. Es geht darum die passende Datenstruktur für ein T9 (die Worterkennung) ähnliches Programm zu Programmieren. Dazu erstelle ich also einen Baum dessen Wurzel 8 verschiedene Knoten hat und sortiere die Daten dort ein. Soweit so gut, nun sortiere ich also z.B. das Wort "hallo" dort ein und erhalte einen Baum, der irgendwie so aussieht (die Knoten sind nach den entsprechenden Ziffern auf der Handytastatur benannt, also in den Knoten zwei kommt a,b,c oder ä, in drei d,e,f usw.) vier.zwei.fuenf.fuenf.sechs mit jeweils als Wert den einsortierten Character. Das ganze sieht dann so aus:


Node:

import java.io.Serializable;



public class Node implements Serializable {
	
	/**
	 * 
	 */
	private static final long serialVersionUID = 7491001156641767375L;
	Node root;
	Node zwei;
	Node drei;
	Node vier;
	Node fuenf;
	Node sechs;
	Node sieben;
	Node acht;
	Node neun;
	
	Character value;


	public Node(Character newValue) {
		value = newValue;
	}

Tree:

public class NodeTree {

	/**
	 * 
	 */

	public void ausfuehren(String s, Node root) {

		for (Integer i = 0; i < s.length(); i++) {

			Character c = s.charAt(i);
	
			{
				root = (insert(root, c));
			}

		}
	}

	public Node insert(Node node, Character value) {
		if (value.equals("a") | value.equals("b") | value.equals("c")
				| value.equals("ä")) {
			if (node.zwei != null) {
				insert(node.zwei, value);
			} else {

				node.zwei = new Node(value);
			}
			return node.zwei;
		} else if (value.equals("d") | value.equals("e") | value.equals("f")) {
			if (node.drei != null) {
				insert(node.drei, value);
			} else {

				node.drei = new Node(value);
			}
			return node.drei;
		} else if (value.equals("g") | value.equals("h") | value.equals("i")) {
			if (node.vier != null) {
				insert(node.vier, value);
			} else {

				node.vier = new Node(value);
			}
			return node.vier;
		} else if (value.equals("j") | value.equals("k") | value.equals("l")) {
			if (node.fuenf != null) {
				insert(node.fuenf, value);
			} else {

				node.fuenf = new Node(value);
			}
			return node.fuenf;
		} else if (value.equals("m") | value.equals("n") | value.equals("o")
				| value.equals("ö")) {
			if (node.sechs != null) {
				insert(node.sechs, value);
			} else {

				node.sechs = new Node(value);
			}
			return node.sechs;
		} else if (value.equals("p") | value.equals("q") | value.equals("r")
				| value.equals("s") | value.equals("ß")) {
			if (node.sieben != null) {
				insert(node.sieben, value);
			} else {

				node.sieben = new Node(value);
			}
			return node.sieben;
		} else if (value.equals("t") | value.equals("u") | value.equals("v")
				| value.equals("ü")) {
			if (node.acht != null) {
				insert(node.acht, value);
			} else {

				node.acht = new Node(value);
			}
			return node.acht;
		} else if (value.equals("w") | value.equals("x") | value.equals("y")
				| value.equals("z")) {
			if (node.neun != null) {
				insert(node.neun, value);
			} else {

				node.neun = new Node(value);
			}
			return node.neun;
		}
		return node; 

	}
}

Nun mein Problem, wie bekomme ich jetzt als Blatt des gerade erzeugten Baums den Wert des eingegebenen Strings? Hört sich entweder simpler an als es ist, oder ich steh auf der Leitung ;-)
Bin offen für Anregungen jeder Art...

Vielen Dank schonmal im voraus

Ray

 

[SlaterB]

na z.B. den String im Blatt ablegen (das Blatt könnte ein besonderer Knoten einer SubKlasse von Node sein),

welchen Sinn hat dieser Baum eigentlich?

wenn du 'axy' und dann 'bxy' ablegst,
dann fügst du erst Node 2 'a' ein und später läuft das zweite Wort auch über diesen Node 'a', obwohl das zweite Wort mit 'b' anfängt,
mit einer anderen Einfügereihenfolge hättest du einen anderen Node,

ich denke, da solltest du gar keinen Buchstaben in die einzelnen Nodes schreiben,
nur ihre Position relativ zum Parent ist wichtig,
Node 2 ist immer a-c, tausendfach in einem großen Baum,
da musst du nicht überall redundant einen zufälligen Buchstaben speichern

noch schlimmer: deinem jetztigen Code nach
wird gar das 'b' als neuer Knoten unter dem 'a' eingefügt?


und spätestens ganz unten musst du doch mehrere Blätter einem Node hinzufügen können?
mal ganz von vorne: wie soll ein Baum aussehen, in welchem zweimal 'aa' eingefügt wird?,
oder, falls Doppelte nicht erlaubt sind, 'aa' und 'ab'?

------------

und erstelle dir ein Array von neun Nodes statt Einzelvariablen,
dazu noch ein statisches Array, das jeden Char auf eine int-Nummer (0-8) abbildet,
dann besteht die Operation insert() aus 10 Zeilen statt redundanten 70!
(im Positions-Array Index für Node-Array bestimmen, prüfen ob null, sonst erstellen und weiter)

 

[ray30002]

Nene, der Baum macht das glaube ich schon richtig, wen ich den später abfrage, soll folgendes passieren. Ich will z.B. das Wort "und" schreiben, gehe also beim ersten Anlauf in den Knoten mit der Bezeichnung acht, schaue ob es dort schon ein fertiges Wort gibt, wenn nicht gehe ich weiter in den Tochterknoten von acht mit der Bezeichnung sechs und mach die selbe Ueberprüfung. Da ich dort noch immer nichts finde, also weiter in den Tochterknoten drei von sechs, dort finde ich am Ende mein "und", aber auch das nette Wort "vor", die Auswahl zwischen diesen beiden wird nun durch die größere Häufigkeit eines der beiden entschieden.

Gruß

Ray

 

[ray30002]

Achso noch die Antwort auf

und spätestens ganz unten musst du doch mehrere Blätter einem Node hinzufügen können?
mal ganz von vorne: wie soll ein Baum aussehen, in welchem zweimal 'aa' eingefügt wird?,
oder, falls Doppelte nicht erlaubt sind, 'aa' und 'ab'?

Der Baum mit doppelt a sieht genauso aus wie ab, also zwei.zwei;

Gruß

Ray