Abfragen auf einem Binary Search Tree ausführen
Ausgehend von einem leeren Binary Search Tree (BST) ohne Knoten sollen drei Arten von Abfragen ausgeführt werden:
insert x– fügt den Wertxin den BST einsearch x– prüft, ob der Wertxim BST vorhanden istprint– gibt den BST in Inorder-Reihenfolge (in-order traversal) aus
Sie erhalten q Anfragen und sollen ein Programm schreiben, das diese abarbeitet.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne Zahl q (1 ≤ q ≤ 1000).
Die nächsten q Zeilen enthalten die Abfragen. Für alle insert- und search-Abfragen übersteigt der Betrag von x nicht .
Ausgabe
Für jede search-Abfrage soll das Programm auf einer neuen Zeile Yes ausgeben, falls der Wert im BST vorhanden ist, oder No, falls nicht.
Für jede print-Abfrage soll das Programm die Inorder-Ausgabe des BST ausgeben, wobei die Werte durch ein Leerzeichen getrennt werden.
Beispiele
Eingabe | Ausgabe |
|---|---|
6 insert 2 insert 1 search 3 insert 0 print search 1 | No 0 1 2 Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB