(Fortsetzung der Übung zu Suchbäumen)
add
(Einfügen in Suchbaum),
contains
(Enthaltensein im Suchbaum).
class Tree<E extends Comparable<E>> { ... public void add (E x) { ... } public void addAll (Collection<E> c) { ... } // nur 3 Zeilen public boolean contains (E x) { ... } } class Entry<E> { ... static <E extends Comparable<E>> Entry<E> add (Entry<E> e, E x) { ... } }und teste:
class TreeTest { public static void addTest () { System.out.println ("addTest"); String [] words = { "foo", "bar", "baz" }; Tree<String> t = new Tree<String> (); for (String w : words) { System.out.println ("add: " + w); t.add (w); System.out.println (t); } } }
add
und contains
?
Hinweis: reicht der folgende Test aus?
class TreeTest { ... public static void containsTest () { System.out.println ("containsTest"); List<Double> l = generate (10); Tree<Double> t = new Tree<Double> (); t.addAll (l); for (Double d : l) { boolean result = t.contains (d); System.out.println (d + " : " + result); } } static List<Double> generate (int size) { List<Double> result = new LinkedList<Double> (); for (int i=0; i<size; i++) { result.add (Math.random()); } return result; } }
equals
und compareTo
definierten Relationen werden bei add
und contains
vorausgesetzt? Beantworte anhand des Quelltextes!
Tree<Integer> t = Tree.full (2); List<Integer> l = t.toList(); System.out.println (l);Deklaration (sichtbar):
class Tree<E extends Comparable<E>> { ... public List<E> toList () { List <E> l = new LinkedList<E> (); Entry.addToList (l, root); return l; } }Implementiere die passende Methode:
class Entry<E> { ... static <E> void addToList (List<E> l, Entry<E> e) { ... } }
add
zum Sortieren (Ausgabe mit toList
).
class Sort { public static <E extends Comparable<E>> List<E> tree_sort (List <E> input) { ... } // nur 3 Zeilen }
List<Double> in = generate (10); List<Double> out = Sort.tree_sort(in); System.out.println ("out: " + out);mit der Implementierung aus der Bibliothek:
Set<Double> s = new TreeSet<Double> (); s.addAll (in); System.out.println ("s: " + s);(für längere Eingaben)