Sortierte Binärbäume (10 Punkte)

Dieses Übungsblatt beschäftigt sich mit sortierten Binärbäumen. In der Vorlesung sind Sie ja bereits das Konzept durchgegangen und haben einige wichtige Prozeduren (Aufbau, grafische Ausgabe, Einfügen, Löschen) besprochen. Ihre Aufgabe ist es nun, die folgenden Prozeduren in Oberon zu implementieren:

PROCEDURE SortAscending(p : TreeBasics.Tree);
  (* prints the tree elements in ascending order *)

PROCEDURE SortDescending(p : TreeBasics.Tree);
  (* prints the tree elements in descending order *)

PROCEDURE Product(p : TreeBasics.Tree) : INTEGER;
  (* calculates the product of all tree elements *)

PROCEDURE NumberOfEvenNodes(p : TreeBasics.Tree) : INTEGER;
  (* returns the unmber of tree elements with an even index *)

PROCEDURE IsWeightBalanced(p : TreeBasics.Tree) : BOOLEAN;
  (* checks if the tree is weight balanced *)

Alle Prozeduren sind rekursiv zu programmieren. Am besten fassen Sie sie in einem separatem Modul zusammen, z.B. TreeFunctions. Ihr Hauptprogramm soll dann einen geeigneten Binärbaum aufbauen und die Prozeduren testen.

Die wichtigsten Grundfunktionen zum Aufbau und zur grafischen Ausgabe habe ich Ihnen aus dem Skript kopiert und in ein Modul TreeBasics zusammengefaßt. Sie können es sich hier runterladen.

Nützliche Hinweise:

• Bei der Lösung der Aufgaben hilft Ihnen ein Blick in Ihr Skript (Thema Traversierung) garantiert weiter!
• Obwohl ich Ihnen das Modul TreeBasics komplett mitgebe, erwarte ich daß Sie sich die enthaltenen Prozeduren genau anschauen und auch verstehen. Dies gilt im übrigen auch für die Funktionen zum Einfügen und zum Löschen von Elementen, die im Skript ab Seite 233 erläutert werden.
• Bei der Prozedur IsWeightBalanced() ist es eventuell sinnvoll, mit einer rekursiven Unterprozedur zu arbeiten. Dies ist mit Sicherheit die trickreichste der fünf Aufgaben.

Viel Erfolg!!!