Re: [考題] 計概／資料結構

: 請問二元搜尋樹插入順序要如何求? : 麻煩各位大大解惑。 : 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 因為我不會做圖所以用寫的就很複雜 有興趣的人參考一下 可能要稍微畫出樹狀結構才能知道我在說啥 如果有錯請指正 謝謝 -- ◆ From: 118.167.118.170
※ 批踢踢實業坊(ptt.cc)
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1364964301.A.2B5.html

推 dragoken:我了解了，謝謝大大解惑~ 04/03 13:52