Klasse ReferenceTree<T>

java.lang.Object
adt.ReferenceTree<T>
Typparameter:
T - Datentyp der Elemente
Alle implementierten Schnittstellen:
Tree<T>
Bekannte direkte Unterklassen:
SearchTree

public class ReferenceTree<T> extends Object implements Tree<T>
Referenz-basierter binärer Baum.

Hinweis: Der Konstruktor ReferenceTree(l, content, r) verlinkt die Teilbäume (keine Kopie). Dadurch können mehrere Baumobjekte dieselben Knoten teilen.

Teilbäume werden verlinkt. Das spart Kopien, bedeutet aber: mehrere Tree-Objekte können dieselben Knoten referenzieren. Mutierende Operationen müssen daher sorgfältig implementiert werden und sollten ausschließlich über die vorgesehenen Hooks erfolgen.

  • Konstruktordetails

    • ReferenceTree

      public ReferenceTree()
      Erzeugt einen leeren Baum.
    • ReferenceTree

      public ReferenceTree(T obj)
      Erzeugt einen Baum mit genau einem Element als Wurzel.
      Parameter:
      obj - Wert (nicht null)
    • ReferenceTree

      public ReferenceTree(ReferenceTree<T> l, T content, ReferenceTree<T> r)
      Erzeugt einen Baum aus linkem Teilbaum, Wurzelinhalt und rechtem Teilbaum. Teilbäume werden verlinkt (keine Kopie).
      Parameter:
      l - linker Teilbaum (oder null)
      content - Wurzelinhalt (nicht null)
      r - rechter Teilbaum (oder null)
    • ReferenceTree

      protected ReferenceTree(ReferenceTree.Node<T> node)
      Interner Konstruktor, um eine Teilbaum-View aus einem Knoten zu erzeugen.
      Parameter:
      node - Knoten
  • Methodendetails

    • empty

      public boolean empty()
      Prüfung, ob der Baum leer ist.
      Angegeben von:
      empty in Schnittstelle Tree<T>
      Gibt zurück:
      true, wenn Baum leer, sonst false
    • left

      public Tree<T> left()
      Rückgabe des linken Teilbaums.
      Angegeben von:
      left in Schnittstelle Tree<T>
      Gibt zurück:
      linker Teilbaum
    • right

      public Tree<T> right()
      Rückgabe des rechten Teilbaums.
      Angegeben von:
      right in Schnittstelle Tree<T>
      Gibt zurück:
      rechter Teilbaum
    • content

      public T content() throws NoSuchElementException
      Rückgabe des in der Wurzel gespeicherten Datenobjekts.
      Angegeben von:
      content in Schnittstelle Tree<T>
      Gibt zurück:
      Wert
      Löst aus:
      NoSuchElementException
    • root

      protected final ReferenceTree.Node<T> root()
      Zugriff auf die Wurzel (für Unterklassen).
      Gibt zurück:
      Wurzel
    • setRoot

      protected final void setRoot(ReferenceTree.Node<T> node)
      Setzt die Wurzel (für Unterklassen).
      Parameter:
      node - neuer Wurzelknoten
    • newNode

      protected final ReferenceTree.Node<T> newNode(T content)
      Erzeugt einen neuen Knoten (für Unterklassen).
      Parameter:
      content - Inhalt
      Gibt zurück:
      Referenz auf den neuen Knoten
      Löst aus:
      IllegalArgumentException - wenn Knoten gleich null
    • contentOf

      protected final T contentOf(ReferenceTree.Node<T> n)
      Liefert den Inhalt eines Knotens (für Unterklassen).
      Parameter:
      n - Knoten, dessen Inhalt ausgelesen werden soll
      Gibt zurück:
      Inhalt des Knoten
    • setContent

      protected final void setContent(ReferenceTree.Node<T> n, T content)
      Setzt den Inhalt eines Knotens (für Unterklassen).
      Parameter:
      n - Knoten dessen Inhalt gesetzt werden soll
      content - Inhalt
      Löst aus:
      IllegalArgumentException - wenn Inhalt gleich null
    • leftOf

      protected final ReferenceTree.Node<T> leftOf(ReferenceTree.Node<T> n)
      Linkes Kind lesen (für Unterklassen).
      Parameter:
      n - zu lesender Knoten
      Gibt zurück:
      linkes Kind des zu lesenden Knotens
    • rightOf

      protected final ReferenceTree.Node<T> rightOf(ReferenceTree.Node<T> n)
      Rechtes Kind lesen (für Unterklassen).
      Parameter:
      n - zu lesender Knoten
      Gibt zurück:
      rechtes Kind des zu lesenden Knotens
    • setLeft

      protected final void setLeft(ReferenceTree.Node<T> parent, ReferenceTree.Node<T> left)
      Linkes Kind setzen (für Unterklassen).
      Parameter:
      parent - Knoten dessen linkes Kind zu setzen ist
      left - neues linkes Kind
      Löst aus:
      IllegalArgumentException - wenn parent gleich null (left/right dürfen null sein; das entspricht einem leeren Teilbaum)
    • setRight

      protected final void setRight(ReferenceTree.Node<T> parent, ReferenceTree.Node<T> right)
      Rechtes Kind setzen (für Unterklassen).
      Parameter:
      parent - Knoten dessen rechtes Kind zu setzen ist
      right - neues rechtes Kind
      Löst aus:
      IllegalArgumentException - wenn parent gleich null (left/right dürfen null sein; das entspricht einem leeren Teilbaum)