計概／資料結構 - 考試

※ 引述《dragoken (流星)》之銘言：
: 請問二元搜尋樹插入順序要如何求?
: 麻煩各位大大解惑。
: http://miupix.cc/pm-5CNFDU

如果答案是八十的話 可能是這樣算的

第一個選4這就不用說了
選4後選2和選6可以得到一樣多種可能(因為圖形對稱)
也就是一開始插入4,2,x,x,x,x,x 的可能如果有P種
一開始插入4,6,x,x,x,x,x 也有P種可能
所以只找一個繼續算下去

我用先選4後選2 繼續說下去
選4選2後面臨三條路徑 1 or 3 or 6
此時可以選1或選3 如果插入的順序是 4,2,1,x,x,x,x 有Q種可能
和4,2,3,x,x,x,x 也有Q種 (差不多同上P種的意義)

但4,2,6,x,x,x,x會有不同可能 W種 (等等會計算出來)

接下來就是解決Q種到底是多少種!?
以4,2,1,x,x,x.x 來說下一個x 選3 有兩種可能 4,2,1,3,6,5,7 和 4,2,1,3,6,7,5兩種
若4,2,1,x,x,x,x下一個選六 會有六種可能能 4,2,1,6,x,x,x (此時三個x誰也不會
擋到誰為3!種可能=6)
也就是前面所述Q=2+6=8
若走4,2,3,x,x,x 也是Q種我就不再計算

接下來是4,2,6,x,x,x,x 的W種
後面的X誰也不會擋到誰(4!=24種)
接下來計算P種 一開始我先選4,2,x,x,x,x,x 會有P種可能
如果他接下來走1 會有Q種可能 走3也有Q種可能 走6有W種可能 (沒別的其他路了...)
P=Q+Q+W=8+8+24=40

4之後選2或6都有P種可能ANSWER=P+P=80

因為我不會做圖所以用寫的就很複雜 有興趣的人參考一下
可能要稍微畫出樹狀結構才能知道我在說啥 如果有錯請指正 謝謝





--