Maximaler Knoten in einem Binary Search Tree
Ausgehend von einem leeren Binary Search Tree (BST) ohne Knoten sollen Sie drei Arten von Abfragen ausführen:
insert x– Fügt den Wertxin den BST ein.
max– Gibt den maximalen Wert im BST aus.
print– Gibt den BST in In-Order-Reihenfolge aus.
Es wird vorausgesetzt, dass
q Abfragen vorliegen. Ihre Aufgabe ist es, ein Programm zu schreiben, das diese Abfragen entsprechend ausführt.Input
Die erste Zeile der Eingabe enthält eine einzelne Zahl
q (1 ≤ q ≤ 1000).Die nächsten
q Zeilen enthalten Abfragen. Bei allen insert-Abfragen überschreitet der Wert x nicht den Betrag .Output
Für jede
max-Abfrage soll das Programm den maximalen Wert des BST in einer eigenen Zeile ausgeben.Für jede
print-Abfrage soll das Programm die Post-Order-Traversierung des BST ausgeben. Die Werte werden dabei durch ein Leerzeichen getrennt.Examples
Input | Output |
7
insert 2
insert 1
max
insert 0
max
insert 4
print | 2
2
0 1 4 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB