Ich habe die folgende Frage, aber keine Antwort darauf. Ich würde mich freuen, wenn meine Methode korrekt ist:
Q. Bei der Suche nach dem Schlüsselwert 60 in einem binären Suchbaum werden Knoten mit den Schlüsselwerten 10, 20, 40, 50, 70, 80, 90 durchlaufen, nicht unbedingt in der angegebenen Reihenfolge. Wie viele verschiedene Reihenfolgen sind möglich, in denen diese Schlüsselwerte auf dem Suchpfad vom Wurzelknoten mit dem Wert 60 auftreten können?
(A) 35 (B) 64 (C) 128 (D) 5040
Aus der Frage verstehe ich, dass alle angegebenen Knoten in die Durchquerung einbezogen werden müssen und letztendlich der Schlüssel 60 erreicht werden muss. Eine solche Kombination wäre beispielsweise:
10, 20, 40, 50, 90, 80, 70, 60.
Da wir alle oben angegebenen Knoten durchlaufen müssen, müssen wir entweder mit 10 oder 90 beginnen. Wenn wir mit 20 beginnen, erreichen wir nicht 10 (da 60> 20 und wir den rechten Teilbaum von 20 durchlaufen).
Ebenso können wir nicht mit 80 beginnen, da wir 90 nicht erreichen können, da 80> 60 den linken Teilbaum von 80 durchlaufen und somit 90 nicht erreichen.
Nehmen wir 10. Die verbleibenden Knoten sind 20, 40, 50, 70, 80, 90. Der nächste Knoten kann entweder 20 oder 90 sein. Wir können aus demselben zuvor genannten Grund keine anderen Knoten nehmen.
Wenn wir ähnlich betrachten, haben wir auf jeder Ebene zwei Möglichkeiten. Da es 7 Knoten gibt, zwei Auswahlmöglichkeiten für die ersten 6 und keine Auswahl für die letzte. Also gibt es total
Permutationen = 2 6 = 64
Ist das eine richtige Antwort?
Wenn nicht, was ist der bessere Ansatz?
Ich möchte verallgemeinern. Wenn Knoten angegeben sind, wären insgesamt mögliche Suchpfade 2 n - 1
Wir werden Moves in Text konvertieren. Es wird angegeben, dass wir während der Suche diese Knoten durchlaufen haben
wie man sehen kann, sind rote größer als 60 und blaue kleiner als 60.
quelle