以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。

（1）以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。
（2）給出上述哈夫曼樹葉結(jié)點(diǎn)的哈夫曼編碼。
（3）一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，給出經(jīng)過(guò)一次劃分后結(jié)果。（由小到大排序）

（1）一組記錄的關(guān)鍵字序列為（47，80，57，39，41，46），給出利用堆排序（堆頂元素是最小元素）的方法建立的初始堆（要求以完全二叉樹描述 ）。
（2）對(duì)關(guān)鍵字序列（ 47，80，57，39，41，85）采用快速排序，給出以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后的結(jié)果。
（3）如下圖所示的二叉樹，給出其前序遍歷序列。

（1）設(shè)有數(shù)據(jù)集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。（2）一組記錄的關(guān)鍵字序列為（5，8，6，3，4，7），利用堆排序（堆頂元素是最小元素）的方法建立初始堆。（要求用完全二叉樹表示）

設(shè)查找表為（7，15，21，22，40，58，68，80，88，89，120），元素的下標(biāo)依次為1，2，3，……，11。
（1）畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹（樹中結(jié)點(diǎn)用下標(biāo)表示）
（2）說(shuō)明成功查找到元素40需要經(jīng)過(guò)多少次比較？
（3）求在等概率條件下，成功查找的平均比較次數(shù)？