Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


4. Bäume



Übungen

  1. Geben Sie die Reihenfolge an, in der die Knoten des Baumes in Abbildung 4.3 bei einer Preorder-, Inorder-, Postorder- und Level-Order-Traversierung besucht werden.
  2. Wie groß ist die Höhe eines vollständigen 4-Pfad-Baumes mit N Knoten?
  3. Zeichnen Sie den Syntaxbaum für den Ausdruck (A+B)*C+(D+E).
  4. Betrachten Sie den Baum von Abbildung 4.2 als einen Wald, der als binärer Baum dargestellt werden soll. Zeichnen Sie diese Darstellung.
  5. Geben Sie für die in Abbildung 4.9 dargestellte Preorder-Traversierung jedesmal, wenn ein Knoten besucht wird, den Inhalt des Stapels an.
  6. Geben Sie für die in Abbildung 4.12 dargestellte Level-Order-Traversierung jedesmal, wenn ein Knoten besucht wird, den Inhalt der Schlange an.
  7. Geben Sie ein Beispiel eines Baumes an, für den der Stapel bei einer Preorder-Traversierung mehr Platz benötigt, als die Schlange bei einer Level-Order-Traversierung.
  8. Geben Sie ein Beispiel eines Baumes an, für den der Stapel bei einer Preorder-Traversierung weniger Platz benötigt, als die Schlange bei einer Level-Order-Traversierung.
  9. Geben Sie eine einen Stapel benutzende Implementation der Postorder-Traversierung eines binären Baumes an.
  10. Schreiben Sie ein Programm zur Implementation der Level-Order-Traversierung eines Waldes, der als binärer Baum dargestellt ist.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]