Hallo. Habe eigentlich zwei unterschiedlichen Fragen, doch beide haben was mit Bäumen zutun, deswegen dachte ich könnte das hier zusammenfassen.
Zuerst eine Frage zum BBaum. Habe folgende Aufgabe gestellt bekommen:
Es sollen 200000 Werte in einem BBaum der eine Höhe von 3 hat eingetragen werden. Welche Ordnung muss der BBaum dafür habe?
Mit den Werten ist doch der Schlüssel gemeint oder? Ich habe mal in einem Buch folgende Formel gefunden wie man die Max anzahl der Schlüssel in einem BBaum berechnen kann:
(2*Ordnung+1)^Höhe+1 -1
Naja ich dachte das ist im Grunde die Lösung. Ich will hier die Ordnung vom BBaum herausfinden. Dann setze ich einfach solange ein bis ich auf einen Wert von > 200000 komme.
(2*10+1)^3+1 -1 = 194480 => Also Ordnung von 10 kann nicht sein, weil kleiner als 200000
(2*11+1)^3+1 -1 = 279840 => Ordnung 11 müsste die Antwort sein
Kann das was ich geschrieben habe stimmen?
Die nächste Frage hat was mit level/pre/inorder zutun. Eigentlich habe ich das ganze verstanden. Nur ist die Umsetzung schwer, das aber auch nur bei Aufgabe wo ich für verschiedene Order EIN Baum zeichnen soll. Zum Beispiel:
Es soll ein Binärbaum gezeichnet werden bei dessen Durchlauf in Preorder- und Inorder folgende Zahlenfolgen entstehen:
Preorder-Reihenfolge: 7, 6, 8, 10, 11, 17, 12
Inoder-Reihenfolge: 6, 7, 10, 8, 17, 11, 12
Die Aufgabe ist angeblich noch nichtmal schwer.Gibt es für sowas einen Trick? Also jetzt ausser „einfach“ drauf zu gucken und das „irgendwie“ zu erkennen? Ich komme damit nicht klar. Könnte für beide das richtige Baum zeichnen, aber EIN Baum für beide überfordert mich gnadenlos. Jemand eine Idee? Wäre sehr nett.
Danke und Gruß,
Trollgo