在搜索特定的密鑰時可能出現多少個不同的命令可能出現鍵值？

Question

在二叉搜索樹中搜索鍵值60時，包含鍵值10,20,40,50,70,80,90的節點是遍歷的，不一定按給定順序。在包含值60的根節點的 搜索路徑中可能出現多少個這樣的關鍵值的不同順序？

Answer 1

答案是7C4。

尋找60，我們遇到4個鍵小於60（10,20,40,50）& 3個鍵更大（70,80,90）。

四個較小的鍵必須以升序顯示，而三個較大的鍵必須以降序顯示，否則一些鍵將在遍歷中被遺漏。

請注意，在遍歷中，這些較小的鍵可能不是連續的，可以用較大的鍵分隔。

對於例如：10，90，20，30，80，40，70，50

但鍵的兩個組的順序（更小或更大）分別保持相同。

現在，在七個位置中，較小的鍵獲得四個位置，可以用7C4方式選擇。一旦我們知道這四個鍵的位置，三個較大鍵的位置只有一個排列。

對於例如：如果我們知道

10，_，20，30，_，40，_，50

那麼只有一種排列的90位，80 & 70是到位編號2，分別爲5 & 7。

因此，對於較小密鑰的每個組合，都有一個更大密鑰的獨特組合。

因此，總組合= 7C4 * 1 = 35種方式