吐爾地·托合提

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

0 引言

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

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

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

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

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

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

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

設數(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 基于二叉排序樹的查找和排序算法

二叉排序樹是常用來進行查找，其靜態(tài)查找性能接近于順序表折半查找，而動態(tài)查找效率遠遠高于折半查找[5]。但是從二叉排序樹的性質(zhì)可知，若左孩子不空，則左孩子的值小于根結(jié)點的值；若右孩子不空，則右孩子的值大于根結(jié)點的值。所以，對于二叉排序樹進行中序遍歷，就可以得到一個有序序列。我們在二叉排序樹的二叉鏈表基本結(jié)點結(jié)構(gòu)中增加一個域，以這種結(jié)點結(jié)構(gòu)構(gòu)造的二叉排序樹不僅仍然滿足靜態(tài)和動態(tài)查找，也符合進行基于二叉排序樹的排序，因此將排序和查找都在二叉排序樹上進行成為了可能。以下介紹本文基于二叉排序樹的查找和排序算法。為了簡單討論，以下假設關(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 二叉排序樹的生成

二叉排序樹不是一次生成的，而是邊查找邊插入。當二叉排序樹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ù)文本定義的結(jié)點結(jié)構(gòu)和二叉排序樹構(gòu)造過程中的操作思路，對于二叉樹中序遍歷算法進行相應的改進，就能得到基于二叉樹中序遍歷的樹表排序算法。

從算法描述可知，對于關(guān)鍵字序列{23，44，6，17，58，17，39，44}及圖2所示對應二叉排序樹，經(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)》課程教學中，我們按照教材內(nèi)容安排講述在不同存儲表示情況下的典型算法，如，順序表的查找、樹表的查找、哈希表的查找等。關(guān)于排序，除了基數(shù)排序之外，都是基于順序表的典型排序算法，沒有安排講解在同一個存儲結(jié)構(gòu)上既能查找又能排序的拓展內(nèi)容。其實，我們對一組數(shù)據(jù)進行處理時，不僅需要查找，而且也需要排序。因此，通常的做法是，選一種合理的物理結(jié)構(gòu)對數(shù)據(jù)進行存儲后，以數(shù)據(jù)為中心編寫一套算法，而不是為不同算法存儲多分數(shù)據(jù)。

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