《數據結構》中基于二叉排序樹的查找與排序算法講解

吐爾地·托合提

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

0 引言

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

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

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

1 二叉排序樹的結構

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

圖1 二叉排序樹結點結構

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

設數據元素的關鍵字序列為{23，44，6，17，58，17，39，44}，則經過一系列查找和插入操作過程，便可以構造出一棵如圖2所示的二叉排序樹

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

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

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

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

二叉排序樹結點結構定義為：

2.1 二叉排序樹的查找

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

2.2 二叉排序樹的生成

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

2.3 二叉排序樹的排序

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

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

最后將以上3個算法在一個主函數中調用，就能實現對一個數據元素集合的存儲、查找和排序。

3 結語

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

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