標(biāo)題: 完整的二進(jìn)制排序樹的深度為k，節(jié)點(diǎn)數(shù)為2 ^ k-1；給定k值和任何三個節(jié)點(diǎn)，則節(jié)點(diǎn)值為1到（2 ^ k-1），輸出包含三個節(jié)點(diǎn)中最小子樹的根節(jié)點(diǎn). 樣本輸入: 4 10 15 13樣本輸出: 12

首先，讓我們了解完整二進(jìn)制排序的數(shù)量. 以下是4級完整的二進(jìn)制排序樹:

*          8
*        /   \
*       4     12
*      / \   /   \
*     2  6   10   14
*    /\  /\  / \ /  \
*   1 3 5 7 9 11 13 15

從上圖可以看到，完整的二進(jìn)制排序樹的中階遍歷是從1到2 ^ k-1的遞增序列（k是層數(shù)）. 因此，只要給出層數(shù)，我們就可以確定二進(jìn)制排序樹. 同時二叉排序樹的查找，從觀察結(jié)果可以看出，二元排序樹從上到下的根節(jié)點(diǎn)只是所有元素二元搜索的中間節(jié)點(diǎn). 根據(jù)上述規(guī)則，為解決三節(jié)點(diǎn)最小子樹的根節(jié)點(diǎn)問題，可以得到以下幾點(diǎn): 無需建立二叉樹，從1?2 ^ k-1遞增數(shù)組是輸入時完整的二叉排序樹當(dāng)三個元素在二分法節(jié)點(diǎn)的兩側(cè)時，當(dāng)前二分法節(jié)點(diǎn)是要找到的最小子樹的根節(jié)點(diǎn)（根據(jù)此規(guī)則，我們不需要判斷這三個元素，只需確定最大元素和最小元素的位置即可）當(dāng)最小節(jié)點(diǎn)的值大于二分法節(jié)點(diǎn)的值時，繼續(xù)在二分法的右半部分搜索. 當(dāng)最大節(jié)點(diǎn)的值小于二分法節(jié)點(diǎn)的值時，請繼續(xù)在二分法的左半部分搜索. 根據(jù)以上節(jié)點(diǎn)二叉排序樹的查找，編寫代碼如下:

本文來自本站，轉(zhuǎn)載請注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-249778-1.html