二分查找樹(shù)的應(yīng)用及其畫(huà)法
說(shuō)在前面
在有序表中查找元素，通常使用二分查找算法，它每查找一次就可以縮小一半范圍，效率遠(yuǎn)高于順序查找。二分查找樹(shù)是模擬二分查找過(guò)程繪制的一棵二叉樹(shù)，通過(guò)圖形將二分查找的過(guò)程可視化，有利于分析和理解抽象的算法問(wèn)題，是一種非常重要的算法分析工具，在解決查找類問(wèn)題中有著廣泛的應(yīng)用。
當(dāng)數(shù)據(jù)量不大、查找范圍較小時(shí)，使用手工繪制二分查找樹(shù)是很方便的，但數(shù)據(jù)量較大時(shí)，手工繪圖就不現(xiàn)實(shí)了；特別是在PPT展示或試卷印刷等場(chǎng)合中，需要的是規(guī)范美觀的示意圖，通常使用Photoshop或Graphviz等專業(yè)制圖軟件來(lái)繪制，耗時(shí)耗力，效果還不一定好。
Python內(nèi)置turtle模塊（海龜繪圖）能以繪圖形式動(dòng)態(tài)展示程序運(yùn)行過(guò)程，我們只需根據(jù)二分查找算法，編寫(xiě)相應(yīng)遞歸函數(shù)，就能看到二分查找的動(dòng)態(tài)過(guò)程，并最終獲得一張精美的二分查找樹(shù)圖片。
猜數(shù)游戲是二分查找算法的典型應(yīng)用，通常是由計(jì)算機(jī)生成一個(gè)隨機(jī)整數(shù)讓玩家來(lái)猜；也可以由玩家隨意輸入一個(gè)整數(shù)讓計(jì)算機(jī)來(lái)猜，并根據(jù)計(jì)算機(jī)猜測(cè)的數(shù)據(jù)給出“偏大”或“偏小”的提示，直到計(jì)算機(jī)猜對(duì)為止。最后輸出計(jì)算機(jī)猜測(cè)次數(shù)。因?yàn)橐欢ǚ秶鷥?nèi)的整數(shù)是一個(gè)遞增序列，故計(jì)算機(jī)常使用二分查找算法來(lái)尋找答案。
參考代碼和程序運(yùn)行界面如圖1所示：
請(qǐng)問(wèn)：（1）當(dāng)輸入整數(shù)16和48時(shí)，計(jì)算機(jī)猜測(cè)次數(shù)分別為多少？
（2）要想計(jì)算機(jī)最難猜中（猜測(cè)次數(shù)最多），玩家應(yīng)該輸入哪些整數(shù)？
要回答上述2個(gè)問(wèn)題，可以根據(jù)題目代碼，繪制出對(duì)應(yīng)的二分查找樹(shù)如圖2所示：
可知，當(dāng)輸入16時(shí)，需要猜測(cè)5次；當(dāng)輸入48時(shí)，需要猜測(cè)6次；要想計(jì)算機(jī)最難猜中，玩家可以輸入2,5,8,11,14,17,20,22,24,27,30,33,35,37,40,43,46,48,50中的某一個(gè)整數(shù)，最多猜測(cè)次數(shù)為6次。
當(dāng)數(shù)據(jù)量不大、查找范圍較小時(shí)，使用手工繪制二分查找樹(shù)是很方便的，但如上圖所示數(shù)據(jù)量較大時(shí)，手工繪圖就不現(xiàn)實(shí)了；特別是在PPT展示或試卷印刷等場(chǎng)合中，需要的是規(guī)范美觀的示意圖，通常使用Photoshop或Graphviz等專業(yè)制圖軟件來(lái)繪制，耗時(shí)耗力，效果還不一定好。
Python內(nèi)置turtle模塊（海龜繪圖）能以繪圖形式動(dòng)態(tài)展示程序運(yùn)行過(guò)程，我們只需根據(jù)二分查找算法，編寫(xiě)相應(yīng)遞歸函數(shù)，就能看到二分查找的動(dòng)態(tài)過(guò)程，并最終獲得一張精美的二分查找樹(shù)圖片。
1. 根據(jù)有序數(shù)組生成對(duì)分查找樹(shù)節(jié)點(diǎn)信息
要畫(huà)出二分查找樹(shù)，必須記錄各個(gè)節(jié)點(diǎn)的數(shù)據(jù)值和位置坐標(biāo)，還有其父親節(jié)點(diǎn)的信息，以便繪制該節(jié)點(diǎn)與父親節(jié)點(diǎn)的連線。自定義函數(shù)create_bs(a:list)可以根據(jù)有序數(shù)組a生成存儲(chǔ)了二分查找樹(shù)各節(jié)點(diǎn)信息的二維列表res。其中列表res的元素為元組(data, x, y, f)，分別表示節(jié)點(diǎn)數(shù)據(jù)值、x、y坐標(biāo)和其父親節(jié)點(diǎn)在res中的下標(biāo)。
一開(kāi)始res是一個(gè)空列表，通過(guò)模擬對(duì)分查找過(guò)程，遞歸地訪問(wèn)數(shù)組a，將其元素值作為節(jié)點(diǎn)數(shù)據(jù)值，訪問(wèn)順序號(hào)和遞歸層數(shù)分別作為節(jié)點(diǎn)的x、y坐標(biāo)，當(dāng)前節(jié)點(diǎn)在res中的下標(biāo)即為其孩子節(jié)點(diǎn)的f值。因?yàn)楦?jié)點(diǎn)沒(méi)有父親節(jié)點(diǎn)，故設(shè)置其f值為-1。
參考代碼如下所示：
def create_bs(a:list):res = []L, R = 0, len(a)-1bs(a, res, L, R, 0, -1)#設(shè)置根節(jié)點(diǎn)的父親節(jié)點(diǎn)下標(biāo)為負(fù)數(shù)，表示沒(méi)有父親節(jié)點(diǎn)return res
函數(shù)create_bs()調(diào)用了一個(gè)遞歸函數(shù)bs(a:list,res:list, L:int, R:int, y:int, f:int)，它有6個(gè)形式參數(shù)，其中a是存儲(chǔ)了有序序列的一維列表；res是用來(lái)存儲(chǔ)二分查找樹(shù)節(jié)點(diǎn)信息的二維列表；L和R分別表示當(dāng)前二叉樹(shù)在有序數(shù)組中的左、右邊界；y表示當(dāng)前根節(jié)點(diǎn)的y坐標(biāo)（高度）；f表示當(dāng)前根節(jié)點(diǎn)的父親節(jié)點(diǎn)在res列表中的下標(biāo)。
函數(shù)bs()模擬了先序遍歷二叉樹(shù)的過(guò)程，先將根節(jié)點(diǎn)信息插入到列表res尾部，記錄其下標(biāo)tempf，再依次遞歸生成其左、右子樹(shù)。其中根節(jié)點(diǎn)的值為a[m]，其下標(biāo)m的計(jì)算體現(xiàn)了對(duì)分查找思想：當(dāng)元素?cái)?shù)量為偶數(shù)時(shí)，若左偏取中，則m = (L + R) // 2；若右偏取中，則m = (L + R + 1) // 2。
例如，當(dāng)a=[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]時(shí)，左偏取中和右偏取中對(duì)應(yīng)的二分查找樹(shù)分別如下圖的圖a和圖b所示：
參考代碼如下所示：
def bs(a:list,res:list, L:int, R:int, y:int, f:int):if L > R:returnm = (L + R) // 2 #根節(jié)點(diǎn)在a中的下標(biāo)，左偏取中res.append([a[m], m, y, f])tempf = len(res) - 1if m > L:bs(a, res, L, m-1, y+1, tempf)if m < R:bs(a, res, m+1, R, y+1, tempf)
2. 繪制二分查找樹(shù)示意圖
生成二分查找樹(shù)的各個(gè)節(jié)點(diǎn)信息以后，我們只需遍歷列表res，就可以按照先序遍歷二叉樹(shù)的順序，依次繪制各個(gè)節(jié)點(diǎn)和節(jié)點(diǎn)間連線。
我們?cè)O(shè)置自定義函數(shù)draw_bs(a:list)來(lái)繪制二分查找樹(shù)，形式參數(shù)a表示存儲(chǔ)了有序序列的一維列表。語(yǔ)句res = create_bs(a)通過(guò)調(diào)用函數(shù)create_bs(a)，將二叉樹(shù)節(jié)點(diǎn)完整信息存儲(chǔ)到二維列表res中。只需使用for循環(huán)遍歷列表res，就能夠?qū)崿F(xiàn)按先序繪制二叉樹(shù)各節(jié)點(diǎn)的功能。具體操作為調(diào)用函數(shù)draw_circle(x, y, r)在指定位置繪制半徑為r的圓；調(diào)用函數(shù)write_data(x, y, r, data, size)在指定圓內(nèi)書(shū)寫(xiě)數(shù)據(jù)data，其中size表示字體大小；若當(dāng)前節(jié)點(diǎn)為非根節(jié)點(diǎn)，則調(diào)用函數(shù)draw_line(x1,y1, x2, y2, r)繪制其與父親節(jié)點(diǎn)的連線。
為了靈活地控制圖像的位置與大小，特別設(shè)置了四個(gè)變量disx, disy, magx, magy，分別表示橫縱坐標(biāo)的偏差和放大倍數(shù)。
參考代碼如下所示：
def draw_bs(a:list):res = create_bs(a)disx, disy, magx, magy = 400, 200, 24, -50#分別表示橫縱坐標(biāo)的偏差和放大倍數(shù)r = 15write_data(-50, 300, 20, '生成對(duì)分查找樹(shù)', 20)write_data(0, 250, 20, ''.join(str(a)), 20)time.sleep(1)for v in res:draw_circle(magx*v[1]-disx,magy*v[2]+disy, r)write_data(magx*v[1]-disx,magy*v[2]+disy, r, v[0], 12)if v[3] >= 0: #非根節(jié)點(diǎn)，與父節(jié)點(diǎn)連線draw_line(magx*res[v[3]][1]-disx,magy*res[v[3]][2]+disy, magx*v[1]-disx, magy*v[2]+disy, r)tt.ht()tt.done()#x,y,r分別為圓心坐標(biāo)和半徑def draw_circle(x, y, r):tt.penup()tt.goto(x, y-r)tt.pendown()tt.circle(r)#x,y,r,data分別為圓心坐標(biāo)、半徑和數(shù)據(jù)，size表示字體大小def write_data(x, y, r, data, size):tt.penup()tt.goto(x, y-r*0.7)tt.pendown()tt.write(data,align="center", font=("Arial", size, "normal"))
自定義函數(shù)draw_line(x1,y1, x2, y2, r)用來(lái)繪制節(jié)點(diǎn)間連線。其中(x1, y1)，(x2, y2)分別表示兩個(gè)節(jié)點(diǎn)的圓心坐標(biāo)，r為節(jié)點(diǎn)圓半徑。我們先計(jì)算出兩個(gè)節(jié)點(diǎn)的圓心距離d = ((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) ** 0.5，然后取圓心連線與兩個(gè)圓周的交點(diǎn)分別為(x3, y3)，(x4, y4)，如圖4所示。計(jì)算出相關(guān)參數(shù)值后，將筆頭抬起，先定位到(x3, y3)，再落筆將筆頭移至(x4, y4)，實(shí)現(xiàn)畫(huà)直線功能。
參考代碼如下所示：
def draw_line(x1, y1, x2, y2, r): #繪制節(jié)點(diǎn)間連線d = ((x1-x2)*(x1-x2) +(y1-y2)*(y1-y2)) ** 0.5x3 = x1 + r * (x2-x1) / dy3 = y1 + r * (y2-y1) / dx4 = x2 - r * (x2-x1) / dy4 = y2 - r * (y2-y1) / dtt.penup()y3)tt.pendown()y4)
?
三、總結(jié)
本文闡述了二分查找樹(shù)在猜數(shù)游戲中的應(yīng)用，以及二分查找樹(shù)的繪制方法。程序僅利用二分查找基本算法和Python海龜繪圖模塊，就能繪制出與專業(yè)軟件相媲美的精美圖形，并根據(jù)實(shí)際需要?jiǎng)討B(tài)生成各種二分查找樹(shù)圖片，方便快捷。
繪圖程序本身就是對(duì)分查找和遞歸算法的典型應(yīng)用，教師可以此作為教學(xué)內(nèi)容。一方面利用程序繪制的圖形學(xué)習(xí)二分查找樹(shù)知識(shí)；另一方面要求學(xué)生根據(jù)算法原理，自行編寫(xiě)繪圖程序，實(shí)現(xiàn)理論與實(shí)際的融合，提高計(jì)算思維和編程能力。
文章給出了繪制二分查找樹(shù)的算法原理和相關(guān)代碼，但并沒(méi)有提供能實(shí)現(xiàn)演示視頻所示的完整程序。請(qǐng)你參考視頻演示效果，制作一個(gè)完整的繪制二分查找樹(shù)程序，要求可以輸入有序列表，調(diào)整放大倍數(shù)和設(shè)置中點(diǎn)左偏或右偏，并根據(jù)輸入的x坐標(biāo)偏差值，在屏幕的適當(dāng)位置繪制二分查找樹(shù)。
程序界面及運(yùn)行效果如下圖所示：
需要本文PPT、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。
我們專注Python算法，感興趣就一起來(lái)！
相關(guān)優(yōu)秀文章：