《數(shù)據(jù)結(jié)構(gòu)》中基于二叉排序樹的查找與排序算法講解

吐爾地·托合提

（新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊830046）

0 引言

查找和排序是日常生活及計算機(jī)軟件設(shè)計中極為常用的，而且是最基本的兩種運算。因此，查找和排序所使用存儲結(jié)構(gòu)及相應(yīng)算法設(shè)計是數(shù)據(jù)結(jié)構(gòu)與算法課程中重點講解內(nèi)容[1]。在數(shù)據(jù)結(jié)構(gòu)中，查找表是一種邏輯結(jié)構(gòu)，是由同一類型的數(shù)據(jù)元素構(gòu)成的集合，其實現(xiàn)方法有順序表和樹表（二叉鏈表）兩種存儲表示。對于排序，也是在類似于查找表的集合中，按照關(guān)鍵碼大小進(jìn)行比較和移動，重新安排每一個數(shù)據(jù)元素（記錄）在序列中的相應(yīng)位置。

在教學(xué)中，我們系統(tǒng)講解如何構(gòu)造查找表，或如何在內(nèi)存中存儲待排序序列，不同存儲表示（順序的和鏈?zhǔn)降模┫鄳?yīng)的查找和排序算法思路，并分析各種算法的性能和優(yōu)缺點，從而從知識層面上基本達(dá)到掌握各種查找與排序算法，對算法性能進(jìn)行分析的基本能力的課程目標(biāo)[2]。但是，在教學(xué)中發(fā)現(xiàn)，因為用有限的課時去講授較多的排序和查找算法，出現(xiàn)“內(nèi)容多，消化不良”現(xiàn)象[3]，從而從技能層面很難達(dá)到從知識中體會和掌握算法設(shè)計的思維方式及技巧，提高分析問題和解決問題能力的課程目標(biāo)[4]。

本文以基于二叉樹的查找和排序為例，形成課堂案例教學(xué)，通過講解在二叉排序樹的構(gòu)造、查找和排序算法上的一些啟發(fā)思路的知識點，一方面加深了學(xué)生對于二叉樹的性質(zhì)、存儲結(jié)構(gòu)、遍歷，以及二叉樹應(yīng)用的理解和掌握，另一方面引導(dǎo)學(xué)生要認(rèn)識到解決問題有多種方案可選，使分析問題和解決問題的能力得到了提升。

1 二叉排序樹的結(jié)構(gòu)

二叉排序樹的一般定義為：或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹。①若左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；②若右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；③左右子樹也都是二叉排序樹。通常，二叉排序樹以二叉鏈表為存儲結(jié)構(gòu)，我們可以設(shè)計每個結(jié)點有三個域，即數(shù) 據(jù) 域（data）、左 孩 子 域（l_child）和 右 孩 子 域（r_child）。因為，查找表是不會有重復(fù)關(guān)鍵字，因此以這種基本結(jié)點結(jié)構(gòu)構(gòu)造二叉排序樹是可以滿足靜態(tài)或動態(tài)查找需求。但是，如果我們在二叉排序樹上對于序列關(guān)鍵碼進(jìn)行排序，因為待排序序列中會出現(xiàn)重復(fù)關(guān)鍵碼，這就與二叉排序樹基本性質(zhì)不符。針對這種情況，我們可以在結(jié)點結(jié)構(gòu)中增加一個域（times），來記錄關(guān)鍵碼重復(fù)出現(xiàn)次數(shù)，再對二叉排序樹生成算法進(jìn)行相應(yīng)改進(jìn)。改進(jìn)后二叉排序樹結(jié)點結(jié)構(gòu)如圖1所示。

圖1 二叉排序樹結(jié)點結(jié)構(gòu)

二叉排序樹是在查找過程中逐步插入結(jié)點而生成，插入結(jié)點過程為：從空樹開始，在二叉排序樹中查找待插入關(guān)鍵字key，若查找失敗，則在對應(yīng)位置插入一個新結(jié)點，給數(shù)據(jù)域data賦key值，times被賦值為1；否則查找成功，表明待插入關(guān)鍵字已在表中，不插入新節(jié)點，對于被查找成功結(jié)點times值增1。

設(shè)數(shù)據(jù)元素的關(guān)鍵字序列為{23，44，6，17，58，17，39，44}，則經(jīng)過一系列查找和插入操作過程，便可以構(gòu)造出一棵如圖2所示的二叉排序樹

圖2 二叉排序樹二叉鏈表示意圖

以上關(guān)鍵字序列中，17和44都是2次出現(xiàn)，在生成過程中對于第二次出現(xiàn)的關(guān)鍵字不插入新節(jié)點，就修改（增1）已被插入相同關(guān)鍵字結(jié)點的times值即可。

2 基于二叉排序樹的查找和排序算法

二叉排序樹是常用來進(jìn)行查找，其靜態(tài)查找性能接近于順序表折半查找，而動態(tài)查找效率遠(yuǎn)遠(yuǎn)高于折半查找[5]。但是從二叉排序樹的性質(zhì)可知，若左孩子不空，則左孩子的值小于根結(jié)點的值；若右孩子不空，則右孩子的值大于根結(jié)點的值。所以，對于二叉排序樹進(jìn)行中序遍歷，就可以得到一個有序序列。我們在二叉排序樹的二叉鏈表基本結(jié)點結(jié)構(gòu)中增加一個域，以這種結(jié)點結(jié)構(gòu)構(gòu)造的二叉排序樹不僅仍然滿足靜態(tài)和動態(tài)查找，也符合進(jìn)行基于二叉排序樹的排序，因此將排序和查找都在二叉排序樹上進(jìn)行成為了可能。以下介紹本文基于二叉排序樹的查找和排序算法。為了簡單討論，以下假設(shè)關(guān)鍵碼為整形，而且只考慮關(guān)鍵碼，暫不考慮數(shù)據(jù)元素其他數(shù)據(jù)項。

二叉排序樹結(jié)點結(jié)構(gòu)定義為：

2.1 二叉排序樹的查找

算法在二叉排序樹上查找數(shù)據(jù)域data等于key的結(jié)點，Root為根結(jié)點指針，若查找成功，則返回指向該結(jié)點的地址，指針q指向其父結(jié)點，若待查找的key在根結(jié)點中或Root為空樹，則q為空；若找找失敗，則返回空指針，此時q指向查找失敗前的最后一個結(jié)點。

2.2 二叉排序樹的生成

二叉排序樹不是一次生成的，而是邊查找邊插入。當(dāng)二叉排序樹Root中不存在數(shù)據(jù)域data值等于待插入關(guān)鍵字key[i]的結(jié)點時，插入數(shù)據(jù)域data值為key的新結(jié)點；若查找成功，則修改被查找成功結(jié)點times值增1；待插入關(guān)鍵字序列存儲在一個長度為n的整形數(shù)組key[]中。

2.3 二叉排序樹的排序

從二叉排序樹的性質(zhì)可知，二叉排序樹中以任意一結(jié)點為根的子樹都為二叉排序樹。樹中結(jié)點關(guān)鍵字大小依次為左孩子、根、右孩子，所以對二叉排序樹進(jìn)行中序遍歷，便可得到一個有序序列，從而達(dá)到對于序列進(jìn)行升序排序的目的。在此，根據(jù)文本定義的結(jié)點結(jié)構(gòu)和二叉排序樹構(gòu)造過程中的操作思路，對于二叉樹中序遍歷算法進(jìn)行相應(yīng)的改進(jìn)，就能得到基于二叉樹中序遍歷的樹表排序算法。

從算法描述可知，對于關(guān)鍵字序列{23，44，6，17，58，17，39，44}及圖2所示對應(yīng)二叉排序樹，經(jīng)過中序遍歷排序得到有序序列{6，17，17，23，39，44，44，58}。

最后將以上3個算法在一個主函數(shù)中調(diào)用，就能實現(xiàn)對一個數(shù)據(jù)元素集合的存儲、查找和排序。

3 結(jié)語

在《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)中，我們按照教材內(nèi)容安排講述在不同存儲表示情況下的典型算法，如，順序表的查找、樹表的查找、哈希表的查找等。關(guān)于排序，除了基數(shù)排序之外，都是基于順序表的典型排序算法，沒有安排講解在同一個存儲結(jié)構(gòu)上既能查找又能排序的拓展內(nèi)容。其實，我們對一組數(shù)據(jù)進(jìn)行處理時，不僅需要查找，而且也需要排序。因此，通常的做法是，選一種合理的物理結(jié)構(gòu)對數(shù)據(jù)進(jìn)行存儲后，以數(shù)據(jù)為中心編寫一套算法，而不是為不同算法存儲多分?jǐn)?shù)據(jù)。

數(shù)據(jù)結(jié)構(gòu)中，二叉排序樹的查找以二叉鏈表為存儲結(jié)構(gòu)，其靜態(tài)查找性能接近于順序表折半查找，但動態(tài)查找效率遠(yuǎn)遠(yuǎn)高于折半查找。因此，本文選二叉排序樹為數(shù)據(jù)表示方法，對其基本結(jié)點結(jié)構(gòu)和生成方法進(jìn)行相應(yīng)的改進(jìn)，在它已有的高效查找特性的基礎(chǔ)上，再引入了基于二叉樹遍歷的排序方法，一方面，加深了學(xué)生對鏈?zhǔn)酱鎯Y(jié)構(gòu)、二叉樹及二叉鏈表的性質(zhì)、遍歷算法的理解和應(yīng)用掌握程度，另一方面，培養(yǎng)了學(xué)生以數(shù)據(jù)為中心的分析問題、解決問題的技能。