Es ist ziemlich schwierig, eine echte generische Baumimplementierung in Java zu machen, die die Baumoperationen und Eigenschaften von den zugrunde liegenden Implementierungen wirklich trennt, dh einen RedBlackTreeNode eintauscht und einige Methoden außer Kraft setzt, um eine RedBlackTree-Implementierung zu erhalten, während alle generischen beibehalten werden Operationen, die eine BinaryTree-Schnittstelle enthält.
Auch wäre eine ideale Abstraktion in der Lage, die Low-Level-Baumdarstellung, z. eine implizite binäre Baumstruktur, die in einem Array für eine Heap- oder Node-Base-Schnittstelle mit linken und rechten Child-Pointern oder mehreren Child-Pointern gespeichert ist, oder eine der oben genannten Funktionen mit Parent-Zeigern oder Threading der Blattknoten usw. usw., usw.
Ich habe versucht, dies selbst zu lösen, aber endete mit einer ziemlich komplizierten Schnittstelle, die immer noch Typsicherheit erzwingt. Hier ist das Grundgerüst der Idee, die eine abstrakte BinaryTree-Klasse mit einer nicht-trivialen Operation (Euler-Tour) erstellt, die auch dann funktioniert, wenn die zugrunde liegende Knotenklasse oder Baumklasse geändert wird. Es könnte wahrscheinlich verbessert werden, indem die Idee der Cursor für die Navigation und Positionen innerhalb der Baumstruktur Einführung:
public interface Tree<E, P extends Tree.Entry<E, P>> extends Collection<E>
{
public P getRoot();
public Collection<P> children(P v);
public E getValue(P v);
public static interface Entry<T, Q extends Entry<T, Q>> { }
}
public interface BinaryTree<E, P extends BinaryTree.Entry<E, P>> extends Tree<E, P>
{
public P leftChild(P v);
public P rightChild(P v);
public static interface Entry<T, Q extends Entry<T, Q>> extends Tree.Entry<T, Q>
{
public Q getLeft();
public Q getRight();
}
}
public interface TreeTraversalVisitor<E, P extends BinaryTree.Entry<E, P>, R>
{
public R visitLeft(BinaryTree<E, P> tree, P v, R result);
public R visitCenter(BinaryTree<E, P> tree, P v, R result);
public R visitRight(BinaryTree<E, P> tree, P v, R result);
}
public abstract class AbstractBinaryTree<E, P extends BinaryTree.Entry<E, P>> extends AbstractCollection<E> implements BinaryTree<E, P>
{
public Collection<P> children(P v)
{
Collection<P> c = new ArrayList<P>(2);
if (hasLeft(v))
c.add(v.getLeft());
if (hasRight(v))
c.add(v.getRight());
return c;
}
/**
* Performs an Euler Tour of the binary tree
*/
public static <R, E, P extends BinaryTree.Entry<E, P>>
R eulerTour(BinaryTree<E, P> tree, P v, TreeTraversalVisitor<E, P, R> visitor, R result)
{
if (v == null)
return result;
result = visitor.visitLeft(tree, v, result);
if (tree.hasLeft(v))
result = eulerTour(tree, tree.leftChild(v), visitor, result);
result = visitor.visitCenter(tree, v, result);
if (tree.hasRight(v))
result = eulerTour(tree, tree.rightChild(v), visitor, result);
result = visitor.visitRight(tree, v, result);
return result;
}
}
Wie möchten Sie diesen Baum verwenden? – pjp
, d. H. Definieren Sie die Struktur selbst (wie ein Familienstammbaum) oder sind die Elemente vergleichbar und möchten Sie sie effizient in den Baum einfügen? – pjp
Jeder Knoten sollte in der Lage sein, eine Liste von Kindern in der Reihenfolge des Einfügens zu führen. Ich muss etwas wie * postorder * traversal (http://en.wikipedia.org/wiki/Tree_traversal) tun, die Kinder eines Knotens in umgekehrter Richtung durchquert. –