前言
隨著近年來計算概念的快速發展，計算學科已經發展成為一個內涵繁雜的綜合性學科，其至少可以劃分為計算機工程(CE)、計算機科學(CS)、信息系統(IS)、信息技術(IT)和軟件工程(SE)5個領域，而且不同領域的人才所應具備的知識結構與能力側重也不盡相同。盡管如此，從目前已經完成的部分來看，數據結構在各領域的知識體系中仍然占據著重要的位置。“數據結構”是普通高等院校計算機和信息管理等專業的一門必修課程，主要討論數據的邏輯結構、在計算機中的存儲結構以及對其進行的各種處理運算的方法和算法。
N.Wirth早在20世紀70年代就指出“程序=數據結構+算法”。數據結構主要研究數據在計算機中存儲、組織、傳遞和轉換的過程及方法，這些也是構成與支撐算法的基礎。近年來，隨著面向對象技術的廣泛應用，從數據結構的定義、分類、組成到設計、實現與分析的模式和方法都有了長足的發展，現代數據結構更加注重和強調數據結構的整體性、通用性、復用性、簡潔性和安全性。
為遵循上述原則，本書選擇Java作為描述語言，因為相對于其他語言，Java程序設計語言是應用最廣泛、面向對象程度化最高的語言，利用Java語言中的類和接口能夠準確地描述任何一種數據結構的邏輯定義和運算，利用一種存儲結構定義的派生類能夠高效地實現對數據的運算。
在內容的選取與結構上，本書并未涉及各種數據結構，而是通過分類和講解典型結構使讀者形成對數據結構的宏觀認識。根據內容的側重，本書共分8章，分別為緒論、線性表、棧和隊列、串和數組、樹形結構、圖、排序和查找。
第1章介紹數據結構的基本概念，算法的描述和算法時間復雜度、空間復雜度等內容，是全書的基礎。
第2章主要介紹線性表的基本概念和抽象數據類型定義、線性表順序和鏈式兩種存儲方式的表示、基本操作的實現和相應的應用。
第3章簡要介紹棧和隊列的基本概念和抽象數據類型定義、棧和隊列在順序存儲和鏈式存儲結構下的基本操作和應用。
第4章主要介紹串的基本概念和數據類型定義、串的存儲結構、基本操作實現和應用等內容。
第5章主要介紹樹和二叉樹的基本概念，詳細介紹二叉樹的性質和存儲結構、遍歷方法的實現及應用、哈夫曼樹的概念和構造方法。
第6章主要介紹圖的基本概念、抽象數據類型定義、存儲結構和遍歷方法，還介紹最小生成樹的基本概念和算法、最短路徑的相關算法、拓撲排序的概念和實現方法。
第7章介紹排序的基本概念，插入排序、交換排序、選擇排序、歸并排序等多種排序的原理、實現方法及性能分析。
第8章主要介紹查找的基本概念，順序查找、二分查找等查找的原理、實現方法和性能分析，平衡二叉樹、哈希表的概念、結構定義和實現方法。
本書的理論知識的教學安排建議如下：
章節內容學時數
第1章緒論2
第2章線性表4~6
第3章棧和隊列6~8
第4章串和數組2~4
第5章樹形結構6~8
第6章圖4~8
第7章排序4~6
第8章查找4~6
建議先修課程：Java語言
建議理論教學時數：32~48學時
建議實驗(實踐)教學時數：16~32學時
本書中的所有算法都已經通過上機調試，盡量確保算法的正確性。在每章內容后都有小結，便于讀者復習總結，并配有豐富的習題，包括選擇題、填空題、算法設計題等，給讀者更多思考的空間。
本書在以下幾個方面具有突出特色：
（1）內容精練，強化基礎，合理安排內容結構，做到由淺入深、循序漸進。
本書各章節都從基本概念入手，逐步介紹其特點和基本操作的實現，把重點放在基礎知識的介紹上，縮減難度較大的內容，使理論敘述簡潔明了、重點突出、詳略得當。
（2）應用實例豐富、完整。
本書通過豐富的應用實例和源代碼使理論和應用緊密結合，增強學生的理解能力，鍛煉程序設計思維，并且代碼有詳細明了的注釋，易于閱讀。
（3）每章后面附有小結和習題，便于學習、總結和提高。
本書結合學生的學習實際選擇難度適中、邏輯合理，適于初學者和進階者開拓思路、深入了解數據結構使用方法和技巧的習題，并附有詳細的解答過程和注意要點，達到通俗易懂、由淺入深的效果，培養讀者遷移知識的能力。
（4）采用Java的泛型方法來體現方法的通用性。
本書采用面向對象的觀點討論數據結構技術，先將抽象數據類型定義成接口，再結合具體的存儲結構加以實現，并以各實現類為線索對類中各種操作的實現方法加以說明。
（5）圖文并茂，便于學生直觀地理解數據結構與算法。
本書通過圖表的方式對數據結構及相應操作進行簡單直接的描述，使內容更加淺顯易懂。
教師可以按照自己對數據結構的理解適當地跳過一些章節，也可以根據教學目標靈活地調整章節的順序，增減各章的學時數。
由于數據結構本身還在探索之中，加上我們的水平和能力有限，本書難免有疏漏之處，懇請各位同仁和廣大讀者給予批評指正，也希望各位能將實踐過程中的經驗和心得與我們交流(yunxianglu@hotmail.com)。
作者
2017年6月
第5章
樹形結構
5.1樹
5.1.1樹的基本概念
樹是數據元素之間具有層次關系的非線性結構，是由n個結點構成的有限集合，結點數為0的樹叫空樹。樹必須滿足以下條件。
(1)有且僅有一個被稱為根的結點。
(2)其余結點可分為m個互不相交的有限集合，每個集合又構成一棵樹，叫根結點的子樹。
與線性結構不同，樹中的數據元素具有一對多的邏輯關系，除根結點以外，每個數據元素可以有多個后繼但有且僅有一個前驅，反映了數據元素之間的層次關系。
樹是遞歸定義的。結點是樹的基本單位，若干個結點組成一棵子樹，若干棵互不相交的子樹組成一棵樹。
圖5.1樹的邏輯結構示意圖
人們在生活中所見的家譜、Windows的文件系統等，雖然表現形式各異，在本質上是樹結構。圖5.1給出了樹的邏輯結構示意圖。
樹的表示方法有多種，如樹形表示法、文氏圖表示法、凹入圖表示法和廣義表表示法。圖5.1所示為樹形表示法，圖5.2給出了用其他3種表示法對樹的表示。
圖5.2樹的3種表示方法
5.1.2樹的術語
1.結點
樹的結點就是構成樹的數據元素，就是其他數據結構中存儲的數據項，在樹形表示法中用圓圈表示。
2.結點的路徑
結點的路徑是指從根結點到該結點所經過結點的順序排列。
3.路徑的長度
路徑的長度指的是路徑中包含的分支數。
4.結點的度
結點的度指的是結點擁有的子樹的數目。
5.樹的度
樹的度指的是樹中所有結點的度的最大值。
6.葉結點
葉結點是樹中度為0的結點，也叫終端結點。
7.分支結點
分支結點是樹中度不為0的結點，也叫非終端結點。
8.子結點
子結點是指結點的子樹的根結點，也叫孩子結點。
9.父結點
具有子結點的結點叫該子結點的父結點，也叫雙親結點。
10.子孫結點
子孫結點是指結點的子樹中的任意結點。
11.祖先結點
祖先結點是指結點的路徑中除自身之外的所有結點。
12.兄弟結點
兄弟結點是指和結點具有同一父結點的結點。
13.結點的層次
樹中根結點的層次為0，其他結點的層次是父結點的層次加1。
14.樹的深度
樹的深度是指樹中所有結點的層次數的最大值加1。
15.有序樹
有序樹是指樹的各結點的所有子樹具有次序關系，不可以改變位置。
16.無序樹
無序樹是指樹的各結點的所有子樹之間無次序關系，可以改變位置。
17.森林
森林是由多個互不相交的樹構成的集合。給森林加上一個根結點就變成一棵樹，將樹的根結點刪除就變成森林。
5.2二叉樹
5.2.1二叉樹的基本概念
1.普通二叉樹
二叉樹是特殊的有序樹，它也是由n個結點構成的有限集合。當n=0時稱為空二叉樹。二叉樹的每個結點最多只有兩棵子樹，子樹也為二叉樹，互不相交且有左右之分，分別稱為左二叉樹和右二叉樹。
二叉樹也是遞歸定義的，在樹中定義的度、層次等術語同樣也適用于二叉樹。
2.滿二叉樹
滿二叉樹是特殊的二叉樹，它要求除葉結點外的其他結點都具有兩棵子樹，并且所有的葉結點都在同一層上，如圖5.3所示。
3.完全二叉樹
完全二叉樹是特殊的二叉樹，若完全二叉樹具有n個結點，它要求n個結點與滿二叉樹的前n個結點具有完全相同的邏輯結構，如圖5.4所示。
新書資訊