資源簡介

(共93張PPT)
第4章 樹
樹的基本概念
二叉樹
二叉樹的遍歷實(shí)現(xiàn)
赫夫曼樹
特殊的樹
樹的基本概念
二叉樹
二叉樹的遍歷實(shí)現(xiàn)
4.2
4.3
4.1
點(diǎn)擊查看本小節(jié)知識架構(gòu)
點(diǎn)擊查看本小節(jié)知識架構(gòu)
點(diǎn)擊查看本小節(jié)知識架構(gòu)
赫夫曼樹
4.4
點(diǎn)擊查看本小節(jié)知識架構(gòu)
特殊的樹
4.5
點(diǎn)擊查看本小節(jié)知識架構(gòu)
學(xué)習(xí)目標(biāo)
掌握
掌握
熟練
掌握
掌握樹的基本概念
1
熟練編寫二叉樹的操作代碼
4
2
掌握二叉樹的基本概念
3
掌握二叉樹的遍歷方式
前面的章節(jié)介紹的都是線性結(jié)構(gòu)，其數(shù)據(jù)元素之間采用的都是一對一的關(guān)系。本章將主要介紹數(shù)據(jù)結(jié)構(gòu)中的一種非線性結(jié)構(gòu)——樹。樹形結(jié)構(gòu)在文件系統(tǒng)與數(shù)據(jù)庫開發(fā)中應(yīng)用十分普遍，可以用來提高數(shù)據(jù)排序和檢索的效率。二叉樹作為樹形結(jié)構(gòu)的一種特殊形式，無論是應(yīng)用于開發(fā)，還是作為基礎(chǔ)學(xué)習(xí)的對象，都具有重要的研究意義。因此，本章將圍繞二叉樹的性質(zhì)以及具體操作進(jìn)行深入講解，最后介紹一些特殊樹形結(jié)構(gòu)的概念以及設(shè)計(jì)原理。
4.1 樹的基本概念
4.1.1
樹的定義
返回目錄
4.1.2
樹的基本術(shù)語
4.1.1 樹的定義
1.2.1節(jié)介紹數(shù)據(jù)的邏輯結(jié)構(gòu)時，已經(jīng)對樹形結(jié)構(gòu)進(jìn)行了簡單的說明，樹形結(jié)構(gòu)是一種非線性結(jié)構(gòu)，其數(shù)據(jù)元素之間存在一對多的關(guān)系。
樹（Tree）是N（N≥0）個結(jié)點(diǎn)的有限集合，它滿足以下4個條件。
（1）有且只有一個特定的被稱為根（Root）的結(jié)點(diǎn)。
（2）除了根結(jié)點(diǎn)，其余每個結(jié)點(diǎn)都有且只有一個直接前驅(qū)。
（3）每個結(jié)點(diǎn)都可以有多個后繼，沒有后繼的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)（樹葉）。
（4）除了根結(jié)點(diǎn)，其他結(jié)點(diǎn)可以分為m（m≥0）個互不相交的有限集合T1、T2……Tm，其中每一個集合又可以視為一棵樹，稱為根的子樹（SubTree）。
4.1.1 樹的定義
樹形結(jié)構(gòu)如圖所示。
4.1.1 樹的定義
圖中，T1、T2、T3是根結(jié)點(diǎn)A的子樹，同時T4是結(jié)點(diǎn)B的子樹，T5是結(jié)點(diǎn)D的子樹。需要特別注意的是，樹形結(jié)構(gòu)中的子樹沒有個數(shù)限制，但是它們之間一定不相交。圖所示為兩種不符合定義的子樹。
4.1.2 樹的基本術(shù)語
1.度數(shù)
一個結(jié)點(diǎn)的子樹（或后繼結(jié)點(diǎn)）的個數(shù)稱為該結(jié)點(diǎn)的度數(shù)。度數(shù)為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)，度數(shù)不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，除根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。一棵樹的度數(shù)指的是該樹中結(jié)點(diǎn)的最大度數(shù)。如圖所示。
4.1.2 樹的基本術(shù)語
圖中，結(jié)點(diǎn)A、B、D都有自己的子樹，即度數(shù)不為0，都是分支結(jié)點(diǎn)，且結(jié)點(diǎn)B、D為內(nèi)部結(jié)點(diǎn)；結(jié)點(diǎn)C、E、F、G、H沒有子樹，即度數(shù)為0，都是終端結(jié)點(diǎn)。圖中結(jié)點(diǎn)D的度數(shù)最大（度數(shù)為3），因此該樹的度數(shù)為3。
2.結(jié)點(diǎn)關(guān)系
結(jié)點(diǎn)的子樹的根（結(jié)點(diǎn)的后繼結(jié)點(diǎn)）稱為該結(jié)點(diǎn)的孩子（Child），同時該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)（父結(jié)點(diǎn)），具有同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)互相稱為兄弟結(jié)點(diǎn)。
圖中，結(jié)點(diǎn)B的孩子結(jié)點(diǎn)為結(jié)點(diǎn)D和結(jié)點(diǎn)E，換句話說，結(jié)點(diǎn)B是結(jié)點(diǎn)D與結(jié)點(diǎn)E的雙親結(jié)點(diǎn)，結(jié)點(diǎn)B與結(jié)點(diǎn)C互為兄弟結(jié)點(diǎn)。
4.1.2 樹的基本術(shù)語
3.結(jié)點(diǎn)層次
樹也可以被視為一種層次結(jié)構(gòu)，樹中的每個結(jié)點(diǎn)都在固定的層次上。結(jié)點(diǎn)層次從根結(jié)點(diǎn)開始定義，根結(jié)點(diǎn)的層次為1，其孩子結(jié)點(diǎn)的層次為2，以次類推。樹中結(jié)點(diǎn)的最大層次稱為樹的深度（Depth）或高度。如圖所示。
由圖可知，該樹的深度為4，結(jié)點(diǎn)A處于第1層，結(jié)點(diǎn)B、C處于第2層，結(jié)點(diǎn)D、E處于第3層，結(jié)點(diǎn)F、G、H處于第4層。
4.有序樹與無序樹
兄弟結(jié)點(diǎn)有順序（不可交換）的樹稱為有序樹，兄弟結(jié)點(diǎn)無順序的樹稱為無序樹。
4.2 二叉樹
4.2.1
二叉樹的概念
返回目錄
4.2.2
滿二叉樹
4.2.3
完全二叉樹
4.2.4
二叉樹的性質(zhì)
4.2 二叉樹
4.2.5
二叉樹的存儲
返回目錄
4.2.6
二叉樹的遍歷方式
4.2.1 二叉樹的概念
二叉樹是一種特殊的樹形結(jié)構(gòu)，其中的每一個結(jié)點(diǎn)最多只能有兩個直接后繼。二叉樹的遞歸定義如下。
（1）有且只有一個根結(jié)點(diǎn)。
（2）可以是空樹，當(dāng)為非空樹時，它由一個根結(jié)點(diǎn)以及兩棵互不相交且分別稱為左子樹和右子樹的二叉樹組成。
二叉樹的任意結(jié)點(diǎn)最多只有兩棵子樹，也可以沒有子樹或者只有一棵子樹，因此二叉樹的度數(shù)一定小于或等于2。二叉樹嚴(yán)格區(qū)分左右子樹，即使只有一棵子樹也要區(qū)分左右。
綜上所述，二叉樹具有以下5種基本形態(tài)。
（1）空二叉樹。
（2）只有一個根結(jié)點(diǎn)。
（3）一個根結(jié)點(diǎn)和根結(jié)點(diǎn)的左子樹構(gòu)成。
（4）一個根結(jié)點(diǎn)和根結(jié)點(diǎn)的右子樹構(gòu)成。
（5）一個根結(jié)點(diǎn)和根結(jié)點(diǎn)的左右子樹構(gòu)成。
4.2.2 滿二叉樹
滿二叉樹每層的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)，除了最后一層為葉結(jié)點(diǎn)，其余所有結(jié)點(diǎn)都有左右子樹。深度為k的滿二叉樹有2 k -1個結(jié)點(diǎn)，如圖所示。
4.2.2 滿二叉樹
滿二叉樹是一種理想狀態(tài)，所有的葉結(jié)點(diǎn)都在同一層中。如果一顆二叉樹除了葉結(jié)點(diǎn)，其他結(jié)點(diǎn)都有左右子樹，但葉結(jié)點(diǎn)不在同一層，則這顆二叉樹并不是滿二叉樹，如圖所示。
由圖可知，同樣深度的二叉樹，滿二叉樹的結(jié)點(diǎn)數(shù)最多，葉結(jié)點(diǎn)數(shù)也最多。
4.2.3 完全二叉樹
對一棵具有n個結(jié)點(diǎn)的二叉樹的結(jié)點(diǎn)按層序進(jìn)行編號，如果編號為i（1≤i≤n）的結(jié)點(diǎn)與同樣深度的滿二叉樹的中編號為i（1≤i≤n）的結(jié)點(diǎn)位置相同，那么該樹就是完全二叉樹。如圖所示。
圖（a）與圖（c）中，相同編號的結(jié)點(diǎn)位置相同，因此圖（a）中的樹符合完全二叉樹的條件，而圖（b）與圖（c）中，樹的第5號和6號結(jié)點(diǎn)位置不相同，因此圖（b）所示的樹不符合完全二叉樹的條件。
4.2.4 二叉樹的性質(zhì)
1.性質(zhì)1
二叉樹的第i（i≥1）層中最多有 2 i-1 個結(jié)點(diǎn)。圖所示的滿二叉樹中，第3層結(jié)點(diǎn)的個數(shù)為2 3-1=4個，第4層結(jié)點(diǎn)的個數(shù)為 2 4-1=8個。
2.性質(zhì)2
深度為k的二叉樹最多有 2 k-1個結(jié)點(diǎn)。在同等深度的二叉樹中，滿二叉樹的結(jié)點(diǎn)數(shù)最多，葉結(jié)點(diǎn)數(shù)最多。
3.性質(zhì)3
在任何一棵二叉樹中，如果葉結(jié)點(diǎn)的數(shù)量為N，度數(shù)為2的結(jié)點(diǎn)數(shù)量為N 2，則N=N 2+1。假設(shè)該樹中度數(shù)為1的結(jié)點(diǎn)數(shù)量為 N 1 ，則這棵樹的總結(jié)點(diǎn)數(shù)為 N+N 1 +N 2 ，總結(jié)點(diǎn)數(shù)也可以是所有子結(jié)點(diǎn)數(shù)加1（根結(jié)點(diǎn)）的和，即 N 1 +2×N 2 +1。因此N 1 +2×N 2 +1=N+N 1 +N 2 ，得出 N=N 2 +1。
4.2.5 二叉樹的存儲
1.二叉樹的順序存儲
使用順序存儲實(shí)現(xiàn)二叉樹就是用一維數(shù)組存儲二叉樹中所有的結(jié)點(diǎn)，并通過數(shù)組的下標(biāo)體現(xiàn)結(jié)點(diǎn)在二叉樹中的位置。圖（a）中的完全二叉樹在數(shù)組中的存儲形式如圖所示。
而對于非完全二叉樹來說，如果將不存在的結(jié)點(diǎn)表示為“^”，則圖（b）中的非完全二叉樹在數(shù)組中的存儲形式如圖所示。
4.2.5 二叉樹的存儲
一棵深度為k的二叉樹，需要分配2 k -1個存儲單元的空間。如果該樹為右斜樹，那么采用順序存儲時將會浪費(fèi)大量空間，如圖所示。
由圖可知，k值越大，浪費(fèi)的存儲空間越多。因此，順序存儲一般只用于完全二叉樹。
4.2.5 二叉樹的存儲
2.二叉樹的鏈?zhǔn)酱鎯?br/>在順序存儲不適用的情況下，可以考慮使用鏈?zhǔn)酱鎯ΑＪ褂面準(zhǔn)酱鎯Ρ硎径鏄洌浣Y(jié)點(diǎn)結(jié)構(gòu)與雙向循環(huán)鏈表一致，即一個數(shù)據(jù)域和兩個指針域，如圖所示。這樣的鏈表稱為二叉鏈表。
圖中，data為數(shù)據(jù)域，用來保存結(jié)點(diǎn)的數(shù)據(jù)，lchild與rchild為指針域，保存的是指向左右孩子的指針。二叉樹鏈?zhǔn)浇Y(jié)構(gòu)如圖所示。
4.2.6 二叉樹的遍歷方式
二叉樹的遍歷方式有很多，主要有以下4種。
1.先序遍歷
先序遍歷就是先訪問根結(jié)點(diǎn)，然后訪問其左孩子，最后訪問其右孩子，其余子結(jié)點(diǎn)都遵循“根左右”的規(guī)則。也就是說，對樹中的任意一個結(jié)點(diǎn)，都是先訪問該結(jié)點(diǎn)的數(shù)據(jù)，然后訪問其左孩子，最后訪問其右孩子。先序遍歷的訪問順序如圖所示。
圖中，按照先序遍歷的規(guī)則，先訪問結(jié)點(diǎn)A，再訪問結(jié)點(diǎn)B，由于結(jié)點(diǎn)B又可以看作結(jié)點(diǎn)A左子樹的根，按照“根左右”的訪問順序，下一次訪問的結(jié)點(diǎn)應(yīng)該是D，而不是C。
4.2.6 二叉樹的遍歷方式
根據(jù)上述遍歷思想，采用先序遍歷訪問圖中結(jié)點(diǎn)的順序?yàn)锳-B-D-H-I-E-C-F-J-G。
2.中序遍歷
中序遍歷就是先訪問根結(jié)點(diǎn)的左孩子，然后訪問根結(jié)點(diǎn)，最后訪問根結(jié)點(diǎn)的右孩子，其余子結(jié)點(diǎn)都遵循“左根右”的規(guī)則。中序遍歷的訪問順序如圖所示。
圖中，結(jié)點(diǎn)A的左孩子為結(jié)點(diǎn)B，結(jié)點(diǎn)B的左孩子為結(jié)點(diǎn)D，結(jié)點(diǎn)D的左孩子為結(jié)點(diǎn)H，因此采用中序遍歷時，最先訪問的結(jié)點(diǎn)應(yīng)該是H。
采用中序遍歷訪問結(jié)點(diǎn)的順序?yàn)镠-D-I-B-E-A-J-F-C-G。
4.2.6 二叉樹的遍歷方式
3.后序遍歷
后序遍歷就是先訪問左孩子，然后訪問右孩子，最后訪問根結(jié)點(diǎn)，其余子結(jié)點(diǎn)都遵循“左右根”的規(guī)則。后序遍歷的訪問順序如圖所示。
圖中，采用后序遍歷訪問結(jié)點(diǎn)的順序?yàn)镠-I-D-E-B-J-F-G-C-A。
4.2.6 二叉樹的遍歷方式
4.層序遍歷
層序遍歷與前3種方式不同，其訪問從樹的第一層開始，從上到下逐層遍歷，同一層中按照從左到右的順序訪問結(jié)點(diǎn)。層序遍歷的訪問順序如圖所示。
上述4種遍歷方式的本質(zhì)區(qū)別是訪問結(jié)點(diǎn)的順序不同。而對于計(jì)算機(jī)而言，它們是4種不同規(guī)則的線性序列，程序按照規(guī)則處理數(shù)據(jù)，可以應(yīng)用于某些特定的場合。
4.3 二叉樹的遍歷實(shí)現(xiàn)
4.3.1
二叉樹的定義
返回目錄
4.3.2
二叉樹的創(chuàng)建
4.3.3
二叉樹的遍歷
4.3.4
整體測試
4.3.1 二叉樹的定義
二叉樹中的結(jié)點(diǎn)結(jié)構(gòu)與鏈表類似，代碼如下所示。
以上代碼中的兩個指針分別用于指向該結(jié)點(diǎn)的左右子樹，具體可參考圖4.12。
4.3.2 二叉樹的創(chuàng)建
創(chuàng)建二叉樹需要考慮該二叉樹是完全二叉樹還是非完全二叉樹。
1.完全二叉樹的創(chuàng)建
如果對一棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序進(jìn)行編號，則對任意一個結(jié)點(diǎn)i（1≤i≤n）來說，有如下規(guī)律。
（1）如果i=1，則結(jié)點(diǎn)i無雙親，為根結(jié)點(diǎn)。
（2）如果i＞1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)是結(jié)點(diǎn)i/2。
（3）如果 2i≤n，則結(jié)點(diǎn)i的左孩子是結(jié)點(diǎn)2i，否則結(jié)點(diǎn)i為葉結(jié)點(diǎn)。
（4）如果 2i+1≤n，則結(jié)點(diǎn)i的右孩子是結(jié)點(diǎn)2i+1，否則結(jié)點(diǎn)i無右孩子。
根據(jù)上述規(guī)律，通過代碼實(shí)現(xiàn)創(chuàng)建完全二叉樹，示例代碼參考教材4.3.2節(jié)。
4.3.2 二叉樹的創(chuàng)建
例中的代碼使用了遞歸調(diào)用的思想，其原理如圖所示。
例通過每一輪的函數(shù)遞歸調(diào)用，判斷是否需要創(chuàng)建結(jié)點(diǎn)的左右孩子，如果無左右孩子，直接將指針指向NULL。
4.3.2 二叉樹的創(chuàng)建
2.非完全二叉樹的創(chuàng)建
完全二叉樹的規(guī)律不適用于非完全二叉樹，通過代碼實(shí)現(xiàn)創(chuàng)建非完全二叉樹，示例代碼參考教材4.3.2節(jié)。
例同樣使用了遞歸調(diào)用，與例4-1不同的是，程序允許用戶選擇是否創(chuàng)建結(jié)點(diǎn)的左右孩子。如果輸入符號#，則當(dāng)前創(chuàng)建不成立，直接返回NULL（即結(jié)點(diǎn)指針指向?yàn)榭眨］敵鼋Y(jié)果如下所示。
運(yùn)行程序，手動輸入q##，表示該樹只有一個根結(jié)點(diǎn)，無左右子樹，根結(jié)點(diǎn)的數(shù)據(jù)為q。
4.3.3 二叉樹的遍歷
1.先序遍歷
先序遍歷遵循“根左右”的規(guī)則，其代碼實(shí)現(xiàn)使用了遞歸調(diào)用的思想，具體代碼如下所示。
4.3.3 二叉樹的遍歷
以上代碼輸出結(jié)點(diǎn)的數(shù)據(jù)后，判斷該結(jié)點(diǎn)是否有左右孩子（順序不可互換），如果有則遞歸調(diào)用函數(shù)本身繼續(xù)向下遍歷。無論遍歷到哪一個結(jié)點(diǎn)，都遵循“根左右”的訪問順序。
假設(shè)存在一棵非完全二叉樹，如圖所示。
使用上面的代碼對圖中的二叉樹進(jìn)行先序遍歷，具體過程如下。
（1）第1次調(diào)用pre_order函數(shù)時，參數(shù)為指向結(jié)點(diǎn)A的指針，因此root不為NULL，執(zhí)行printf()函數(shù)輸出結(jié)點(diǎn)A的數(shù)據(jù)，然后判斷結(jié)點(diǎn)A是否具有左孩子（判斷為是），遞歸調(diào)用pre_order()函數(shù)（第2次調(diào)用）。
（2）第2次調(diào)用pre_order()函數(shù)時，參數(shù)為指向結(jié)點(diǎn)A左孩子（即結(jié)點(diǎn)B）的指針，因此root不為NULL，執(zhí)行printf()函數(shù)輸出結(jié)點(diǎn)B的數(shù)據(jù)，然后判斷結(jié)點(diǎn)B是否具有左孩子（判斷為是），遞歸調(diào)用pre_order()函數(shù)（第3次調(diào)用）。
4.3.3 二叉樹的遍歷
（3）第3次調(diào)用pre_order()函數(shù)時，參數(shù)為指向結(jié)點(diǎn)B左孩子（即結(jié)點(diǎn)D）的指針，因此root不為NULL，執(zhí)行printf()函數(shù)輸出結(jié)點(diǎn)D的數(shù)據(jù)，然后判斷結(jié)點(diǎn)D是否具有左孩子（判斷為是），遞歸調(diào)用pre_order()函數(shù)（第4次調(diào)用）。
（4）第4次調(diào)用pre_order()函數(shù)時，參數(shù)為指向結(jié)點(diǎn)D左孩子（即結(jié)點(diǎn)G）的指針，因此root不為NULL，執(zhí)行printf()函數(shù)輸出結(jié)點(diǎn)G的數(shù)據(jù)，然后判斷結(jié)點(diǎn)G是否具有左孩子（判斷為否），繼續(xù)判斷結(jié)點(diǎn)G是否具有右孩子（判斷為否）。遞歸到此開始返回，返回到第3次調(diào)用pre_order()函數(shù)。
（5）返回到第3次調(diào)用pre_order()函數(shù)，繼續(xù)判斷結(jié)點(diǎn)D是否有右孩子（判斷為否），返回到第2次調(diào)用pre_order()函數(shù)。
（6）返回到第2次調(diào)用pre_order()函數(shù)，繼續(xù)判斷結(jié)點(diǎn)B是否有右孩子（判斷為是），調(diào)用pre_order()函數(shù)（第5次調(diào)用）輸出結(jié)點(diǎn)E的數(shù)據(jù)，并且判斷結(jié)點(diǎn)E是否有左右孩子（判斷為否）。
（7）返回到第1次調(diào)用pre_order()函數(shù)，繼續(xù)判斷結(jié)點(diǎn)A是否有右孩子（判斷為是），調(diào)用pre_order()函數(shù)（第6次調(diào)用），參數(shù)為指向結(jié)點(diǎn)A右孩子（即結(jié)點(diǎn)C）的指針，執(zhí)行printf()函數(shù)輸出結(jié)點(diǎn)C的數(shù)據(jù)，然后判斷結(jié)點(diǎn)C是否有左孩子（判斷為是），遞歸調(diào)用pre_order()函數(shù)（第7次調(diào)用）。
4.3.3 二叉樹的遍歷
（8）第7次調(diào)用pre_order()函數(shù)時，參數(shù)為指向結(jié)點(diǎn)C左孩子（即結(jié)點(diǎn)F）的指針，執(zhí)行printf()函數(shù)輸出結(jié)點(diǎn)F的數(shù)據(jù)，并且判斷結(jié)點(diǎn)F是否有左右孩子（判斷為否）。遞歸到此開始返回，返回到第6次調(diào)用pre_order()函數(shù)。
（9）返回到第6次調(diào)用pre_order()函數(shù)，繼續(xù)判斷結(jié)點(diǎn)C是否有右孩子（判斷為否），返回到第1 次調(diào)用pre_order()函數(shù)。至此，程序運(yùn)行結(jié)束。
4.3.3 二叉樹的遍歷
2.中序遍歷
中序遍歷遵循“左根右”的規(guī)則，其代碼實(shí)現(xiàn)同樣使用了遞歸調(diào)用的思想，具體代碼如下所示。
4.3.3 二叉樹的遍歷
以上代碼先判斷結(jié)點(diǎn)是否有左孩子，然后輸出結(jié)點(diǎn)數(shù)據(jù)，再判斷結(jié)點(diǎn)是否有右孩子（順序不可互換）。如果有左右孩子則遞歸調(diào)用函數(shù)本身繼續(xù)向下遍歷。無論遍歷到哪一個結(jié)點(diǎn)，都遵循“左根右”的訪問順序。（具體過程可參考先序遍歷）
3.后序遍歷
后序遍歷遵循“左右根”的規(guī)則，其代碼實(shí)現(xiàn)同樣使用了遞歸調(diào)用的思想，具體代碼如下所示。
4.3.3 二叉樹的遍歷
以上代碼先判斷結(jié)點(diǎn)是否有左孩子，然后判斷結(jié)點(diǎn)是否有右孩子，最后輸出結(jié)點(diǎn)數(shù)據(jù)（順序不可互換）。如果有左右孩子則遞歸調(diào)用函數(shù)本身繼續(xù)向下遍歷。無論遍歷到哪一個結(jié)點(diǎn)，都遵循“左右根”的訪問順序。（具體分析可參考先序遍歷）
4.層序遍歷
二叉樹的層序遍歷可以利用隊(duì)列的思想，從第一個結(jié)點(diǎn)（根結(jié)點(diǎn)）開始入隊(duì)，然后出隊(duì)，判斷此結(jié)點(diǎn)是否有左孩子或右孩子。如果存在則繼續(xù)入隊(duì)，入隊(duì)后繼續(xù)執(zhí)行之前的步驟。讀者可參考3.6節(jié)的鏈?zhǔn)疥?duì)列操作函數(shù)或例3-8來測試層序遍歷的代碼，具體代碼參考教材4.3.3節(jié)。
4.3.4 整體測試
1.完全二叉樹測試
使用創(chuàng)建完全二叉樹的功能代碼（例4-1），結(jié)合先序遍歷、中序遍歷、后序遍歷的功能代碼進(jìn)行測試，示例代碼參考教材4.3.4節(jié)。
根據(jù)第 96 行代碼可知，創(chuàng)建一棵完全二叉樹，且結(jié)點(diǎn)數(shù)為10，該二叉樹的邏輯結(jié)構(gòu)如圖所示。
4.3.4 整體測試
由圖可知，該二叉樹采用先序遍歷的順序?yàn)?-2-4-8-9-5-10-3-6-7，中序遍歷的順序?yàn)?-4-9-2-10-5-1-6-3-7，后序遍歷的順序?yàn)?-9-4-10-5-2-6-7-3-1。
程序輸出結(jié)果如下所示，參照上述推導(dǎo)結(jié)果，查看結(jié)點(diǎn)與數(shù)據(jù)是否對應(yīng)。
根據(jù)輸出結(jié)果可知，結(jié)點(diǎn)與數(shù)據(jù)一一對應(yīng)，測試代碼正確。
2.非完全二叉樹測試
使用創(chuàng)建非完全二叉樹的功能代碼（例4-2），結(jié)合先序遍歷、中序遍歷、后序遍歷的功能代碼進(jìn)行測試，示例代碼參考教材4.3.4節(jié)。
4.3.4 整體測試
例需要用戶自行輸入二叉樹的結(jié)點(diǎn)數(shù)據(jù)（按照創(chuàng)建非完全二叉樹的代碼邏輯思維輸入），輸入內(nèi)容為ABD#G###CE##F##（符號#表示不存在該結(jié)點(diǎn)，詳見第15行代碼），與其對應(yīng)的非完全二叉樹的邏輯結(jié)構(gòu)如圖所示。
由圖可知，該二叉樹先序遍歷的順序?yàn)锳-B-D-G-C-E-F，中序遍歷的順序?yàn)镈-G-B-A-E-C-F，后序遍歷的順序?yàn)镚-D-B-E-F-C-A。
運(yùn)行程序并輸入結(jié)點(diǎn)數(shù)據(jù)，其輸出結(jié)果如下所示，參照上述推導(dǎo)結(jié)果，查看結(jié)點(diǎn)與數(shù)據(jù)是否對應(yīng)。
遍歷輸出的結(jié)果與推導(dǎo)結(jié)果一致，測試代碼正確。
4.4 赫夫曼樹
4.4.1
赫夫曼樹的概念
返回目錄
4.4.2
赫夫曼樹的原理
4.4.3
構(gòu)造赫夫曼樹
4.4.1 赫夫曼樹的概念
赫夫曼樹又稱為最優(yōu)二叉樹。1952年，美國數(shù)學(xué)家赫夫曼（David Huffman）發(fā)明了一種壓縮編碼方法，為實(shí)現(xiàn)文件壓縮，提高數(shù)據(jù)傳輸效率做出了重要貢獻(xiàn)。為了紀(jì)念他的成就，將他在編碼中使用的特殊二叉樹稱為赫夫曼樹，同時將他的編碼方式稱為赫夫曼編碼。
接下來通過一個例子引出赫夫曼樹的概念。
在如今倡導(dǎo)素質(zhì)教育的背景下，很多中小學(xué)已經(jīng)取消使用百分制表示學(xué)科成績的做法，而是使用優(yōu)秀、良好、中等、及格和不及格來反應(yīng)學(xué)生一個學(xué)期的整體成績。對于老師來說，一般的做法是先通過評卷得到學(xué)生的成績，再判斷該成績屬于5個層次中的哪一個層次。以下代碼實(shí)現(xiàn)了這樣的轉(zhuǎn)換。
4.4.1 赫夫曼樹的概念
通常情況下，一個學(xué)校或年級中，大部分學(xué)生的成績都處于中等以上。以上代碼中，所有成績都要先被判斷是否及格，再逐級判斷得到最終結(jié)果。因此，當(dāng)成績的輸入量較大時，該算法存在很明顯的效率問題。
用二叉樹表示該算法，如圖所示。
4.4.1 赫夫曼樹的概念
假設(shè)通過計(jì)算得到學(xué)生成績在5個層次范圍的占比，如表所示。
由表可以看出，70分以上的成績占總數(shù)80%，這些成績在上述程序算法中都需要經(jīng)過3次或3次以上的判斷，顯然該算法是不合理的。
由于中等成績和良好成績所占的比例較高，可以考慮對圖所示的二叉樹進(jìn)行重新分配，如圖所示。
4.4.1 赫夫曼樹的概念
圖所示的算法比圖4.21效率要高，那么如何在一些特定的場合下設(shè)計(jì)出類似于圖所示的二叉樹（該方案在學(xué)生成績這一場合中為最優(yōu)算法），進(jìn)而實(shí)現(xiàn)代碼設(shè)計(jì)呢？，這就需要使用赫夫曼樹的設(shè)計(jì)原理。
4.4.2 赫夫曼樹的原理
對圖所示的二叉樹進(jìn)行簡化，如圖所示。
對圖所示的二叉樹進(jìn)行簡化，如圖所示。
4.4.2 赫夫曼樹的原理
在圖所示的二叉樹中，A代表不及格，B代表及格，C代表中等，D代表良好，E代表優(yōu)秀。這些結(jié)點(diǎn)對應(yīng)的值為學(xué)生成績占比。而赫夫曼樹的定義中，樹中每個結(jié)點(diǎn)的數(shù)據(jù)域可以存放一個特定的數(shù)值來，這個值稱為權(quán)值。因此，將學(xué)生成績占比作為結(jié)點(diǎn)的權(quán)值，得到結(jié)點(diǎn)A的權(quán)值為5，結(jié)點(diǎn)B的權(quán)值為15，結(jié)點(diǎn)C的權(quán)值為30，結(jié)點(diǎn)D的權(quán)值為40，結(jié)點(diǎn)E的權(quán)值為10。
在了解赫夫曼樹的原理之前，需要先了解關(guān)于赫夫曼樹的名詞解釋（結(jié)合圖4.23和圖4.24）。
（1）路徑：在一棵樹中，從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的通路稱為路徑。圖中，從根結(jié)點(diǎn)到結(jié)點(diǎn)C的通路就是一條路徑。
（2）路徑長度：一條路徑中的分支數(shù)目稱為路徑長度，也就是說，在一條路徑中，每經(jīng)過一個結(jié)點(diǎn)，路徑長度加1。圖中，根結(jié)點(diǎn)到結(jié)點(diǎn)C的路徑長度為3，根結(jié)點(diǎn)到結(jié)點(diǎn)D的路徑長度為4。
（3）樹的路徑長度：從根結(jié)點(diǎn)到每一個結(jié)點(diǎn)的路徑長度之和。圖4.23所示的樹的路徑長度為1+1+2+2+3+3+4+4=20，圖4.24所示的樹的路徑長度為1+2+3+3+2+1+2+2=16。
（3）結(jié)點(diǎn)的帶權(quán)路徑長度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)的權(quán)值的乘積。
4.4.2 赫夫曼樹的原理
（4）結(jié)點(diǎn)的帶權(quán)路徑長度：樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和。
假設(shè)有n個權(quán)值{w 1 ,w 2 ,…,w n }，構(gòu)造一棵有n個葉結(jié)點(diǎn)的二叉樹，每個葉結(jié)點(diǎn)的權(quán)值為 w k，每個葉結(jié)點(diǎn)的的路徑長度為 l k ，則該樹的帶權(quán)路徑長度記作WPL= w k l k。其中帶權(quán)路徑長度WPL最小的二叉樹稱為赫夫曼樹。
圖所示的二叉樹的WPL值為5×1+15×2+30×3+40×4+10×4=325。圖所示的二叉樹的WPL值為 5×3+15×3+30×2+40×2+10×2=220。如果學(xué)生成績示例中有10000人，按照圖4.23所示二叉樹的判斷方法，需要執(zhí)行32500次比較，而按照圖4.24所示二叉樹的判斷方法，需要執(zhí)行22000次比較。很明顯，采用第二種方式效率要比第一種高很多。
4.4.3 構(gòu)造赫夫曼樹
4.4.2節(jié)已經(jīng)介紹了赫夫曼樹的原理，接下來將討論如何構(gòu)建赫夫曼樹。在構(gòu)建赫夫曼樹時，想要使樹的帶權(quán)路徑長度最小，只需要遵循一個原則，權(quán)值越大的結(jié)點(diǎn)離樹根越近。
假設(shè)有6個帶權(quán)的結(jié)點(diǎn)，權(quán)值分別為9、12、6、3、5、15，將這些結(jié)點(diǎn)按照從小到大順序進(jìn)行排列，如圖所示。
選出圖中兩個權(quán)值最小的結(jié)點(diǎn)，將這兩個結(jié)點(diǎn)組成一個新的二叉樹，且新二叉樹的根結(jié)點(diǎn)的權(quán)值為左右孩子權(quán)值的和。如圖所示。
4.4.3 構(gòu)造赫夫曼樹
在未組成樹的剩余結(jié)點(diǎn)中選出權(quán)值最小的結(jié)點(diǎn)與二叉樹合并，形成新的二叉樹，如圖所示。
此時新二叉樹的根結(jié)點(diǎn)的權(quán)值為14，該值與未組成樹的剩余結(jié)點(diǎn)的權(quán)值相差不大，且不是其中的最大值。因此可以繼續(xù)從未組成樹的剩余結(jié)點(diǎn)中選出權(quán)值最小的結(jié)點(diǎn)與二叉樹合并，形成新的二叉樹，如圖所示。
4.4.3 構(gòu)造赫夫曼樹
此時新二叉樹的根結(jié)點(diǎn)的權(quán)值為23，該值比剩余結(jié)點(diǎn)的權(quán)值大，且相差較大。因此二叉樹不能繼續(xù)組合，否則將不滿足赫夫曼樹的定義。
將剩余結(jié)點(diǎn)組合成新的二叉樹，如圖所示。
4.4.3 構(gòu)造赫夫曼樹
將圖所示的兩顆二叉樹合并，生成最終的二叉樹，此二叉樹即為赫夫曼樹。如圖所示。
圖所示的最終合并生成的二叉樹就是赫夫曼樹，該二叉樹的帶權(quán)路徑長度WPL為12×2+15×
2+9×2+6×3+3×4+5×4=122。
4.5 特殊的樹
4.5.1
二叉排序樹
返回目錄
4.5.2
平衡二叉樹
4.5.3
B樹
4.5.4
B+樹與B*樹
4.5.5
紅黑樹
4.5.1 二叉排序樹
1.二叉排序樹的定義
二叉排序樹（Binary Sort Tree）又稱為二叉搜索樹（Binary Search Tree），其具體定義如下。
（1）若左子樹不為空，則左子樹上的所有結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值。
（2）若右子樹不為空，則右子樹上的所有結(jié)點(diǎn)的值大于根結(jié)點(diǎn)的值。
（3）左、右子樹本身也是一棵二叉排序樹。
由此定義可知，二叉排序樹的左子樹結(jié)點(diǎn)值<根結(jié)點(diǎn)值<右子樹結(jié)點(diǎn)值。如果對二叉排序樹進(jìn)行中序遍歷，可以得到一個遞增的有序序列。如圖所示，該二叉排序樹中序遍歷的順序?yàn)?-2-3-4-5-6。
4.5.1 二叉排序樹
2.二叉排序樹插入結(jié)點(diǎn)
二叉排序樹插入結(jié)點(diǎn)時，如果原二叉排序樹為空，則直接插入該結(jié)點(diǎn)；如果該結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，則將該結(jié)點(diǎn)插入左子樹；如果該結(jié)點(diǎn)的值大于根結(jié)點(diǎn)的值，則將該結(jié)點(diǎn)插入右子樹。
3.二叉排序樹刪除結(jié)點(diǎn)
二叉排序樹刪除結(jié)點(diǎn)時有以下3種情況。
（1）如果被刪除的結(jié)點(diǎn)是葉結(jié)點(diǎn)，則直接刪除，不會影響二叉樹原有的規(guī)則。
（2）如果被刪除的結(jié)點(diǎn)只有左子樹或右子樹，則將該結(jié)點(diǎn)的子樹作為其雙親結(jié)點(diǎn)的子樹，代替該結(jié)點(diǎn)；
（3）如果被刪除的結(jié)點(diǎn)有左右子樹，則可以根據(jù)中序遍歷的結(jié)果，使用被刪除結(jié)點(diǎn)的直接前驅(qū)或后繼替換該結(jié)點(diǎn)。
4.5.1 二叉排序樹
圖所示的二叉排序樹采用中序遍歷訪問結(jié)點(diǎn)的順序?yàn)?7-23-25-28-30-34-36-42-51。假設(shè)需要刪除的結(jié)點(diǎn)是28，結(jié)點(diǎn)28的上一個遍歷的結(jié)點(diǎn)為25，下一個遍歷的結(jié)點(diǎn)為30。因此，選取這兩個結(jié)點(diǎn)替換被刪除的結(jié)點(diǎn)，即可完成刪除操作，如圖所示。
刪除結(jié)點(diǎn)后，該二叉樹仍然符合二叉排序樹的規(guī)則。
4.5.1 二叉排序樹
4.二叉排序樹查找
在最壞的情況下，二叉排序樹查找需要的時間取決于樹的深度。假設(shè)某二叉排序樹的結(jié)點(diǎn)個數(shù)為n，具體的查找分析如下。
（1）當(dāng)二叉排序樹接近于滿二叉樹時，其深度為 log 2 n，因此在最壞的情況下查找的時間復(fù)雜度為 O(log 2 n)。
（2）當(dāng)二叉樹形成單枝樹時，其深度為n，在最壞的情況下查找的時間復(fù)雜度為O(n)。如圖所示。
由此可知，為了保證二叉排序樹有較高的查找速度，需要使該二叉排序樹接近于滿二叉樹，即二叉排序樹中的每一個結(jié)點(diǎn)的左、右子樹深度盡量相等。
4.5.2 平衡二叉樹
1.平衡二叉樹的定義
由二叉排序樹的查找分析可知，二叉排序樹的查找效率與其形態(tài)有關(guān)。二叉排序樹的形態(tài)最好是均勻的，這樣就產(chǎn)生了平衡二叉樹（Balanced Binary Search）。
平衡二叉樹可以是空樹，當(dāng)其不為空樹時，具有以下性質(zhì)。
（1）左右子樹的深度差的絕對值不超過1。
（2）左右子樹也分別是平衡二叉樹。
平衡二叉樹中的左子樹深度減去右子樹深度的值稱為平衡因子BF（Balance Factor）。因此，平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只能是-1、0、1。如果存在一個結(jié)點(diǎn)的平衡因子的絕對值大于1，那么該二叉樹就不是平衡二叉樹，如圖所示。
4.5.2 平衡二叉樹
平衡二叉樹是一種特殊的二叉排序樹，因此平衡二叉樹應(yīng)該滿足二叉排序樹的規(guī)則。圖（a）為平衡二叉樹，而圖（b）不是平衡二叉樹，原因是圖（b）中二叉樹根結(jié)點(diǎn)的值小于其左孩子。
2.構(gòu)造平衡二叉樹
俄羅斯數(shù)學(xué)家格奧爾基（Georgii M.Adelson-Velskii）和葉夫根尼（Evgenii M.landis）提出了一種動態(tài)保持平衡二叉樹的方法。其基本思想是：在構(gòu)造平衡二叉樹時，每當(dāng)插入一個結(jié)點(diǎn)時，先檢查是否因插入結(jié)點(diǎn)而破壞樹的平衡性，如果是，則找出其中最小不平衡子樹，調(diào)整最小不平衡樹中各結(jié)點(diǎn)的關(guān)系（在遵守二叉排序樹規(guī)則的前提下），以達(dá)到新的平衡。
4.5.2 平衡二叉樹
最小不平衡子樹指的是距離新插入結(jié)點(diǎn)最近，以第一個平衡因子絕對值大于1的結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹。如圖所示。
調(diào)整最小不平衡子樹有以下4種情況。
（1）單向右旋，新結(jié)點(diǎn)插入位置為左子樹的左子樹，以左子樹為軸心，進(jìn)行單次向右旋轉(zhuǎn)，如圖所示。
4.5.2 平衡二叉樹
由圖可知，開始時結(jié)點(diǎn)3的BF為2（左子樹深度減右子樹深度），經(jīng)過旋轉(zhuǎn)后，結(jié)點(diǎn)2成為根結(jié)點(diǎn)，并且滿足二叉排序樹的規(guī)則。旋轉(zhuǎn)后結(jié)點(diǎn)1、結(jié)點(diǎn)2、結(jié)點(diǎn)3的BF都為0。
（2）單向左旋，新結(jié)點(diǎn)插入位置為右子樹的右子樹，以右子樹為軸心，進(jìn)行單次向左旋轉(zhuǎn)，如圖所示。
由圖可知，開始時結(jié)點(diǎn)1的BF為-2，經(jīng)過旋轉(zhuǎn)后，結(jié)點(diǎn)2成為根結(jié)點(diǎn)，結(jié)點(diǎn)1、結(jié)點(diǎn)2、結(jié)點(diǎn)3的BF都為0。
4.5.2 平衡二叉樹
無論是單向左旋還是右旋，都可能出現(xiàn)一些復(fù)雜的情況，如圖所示，開始時結(jié)點(diǎn)2的BF為-1，插入結(jié)點(diǎn)6后，結(jié)點(diǎn)2的BF變?yōu)?2，顯然不滿足平衡二叉樹的規(guī)則。
對圖所示的二叉樹執(zhí)行左旋操作，結(jié)點(diǎn)4將成為新的根結(jié)點(diǎn)，旋轉(zhuǎn)后的二叉樹如圖所示。
4.5.2 平衡二叉樹
如圖所示，結(jié)點(diǎn)3原本是結(jié)點(diǎn)4的左孩子，為了在旋轉(zhuǎn)后依然滿足二叉排序樹的規(guī)則，結(jié)點(diǎn)3變成了結(jié)點(diǎn)2的右孩子。
（3）雙向旋轉(zhuǎn)，先右后左，新結(jié)點(diǎn)插入位置為右子樹的左子樹，如圖所示。
圖中，新插入結(jié)點(diǎn)為結(jié)點(diǎn)8，插入結(jié)點(diǎn)8后，結(jié)點(diǎn)4的BF值變?yōu)?2，不滿足平衡二叉樹的規(guī)則。按照一般的做法，將結(jié)點(diǎn)6、結(jié)點(diǎn)10、結(jié)點(diǎn)8向左旋轉(zhuǎn)，旋轉(zhuǎn)后可以發(fā)現(xiàn)，結(jié)點(diǎn)8成為結(jié)點(diǎn)10的右孩子，8小于10，不符合二叉排序樹的規(guī)則。
4.5.2 平衡二叉樹
上述情況下，應(yīng)該先將結(jié)點(diǎn)8、結(jié)點(diǎn)10向右旋轉(zhuǎn)，如圖所示。
圖所示為旋轉(zhuǎn)后得到的二叉樹，再將結(jié)點(diǎn)6、結(jié)點(diǎn)8、結(jié)點(diǎn)10向左旋轉(zhuǎn)，如圖所示。
4.5.2 平衡二叉樹
（4）雙向旋轉(zhuǎn)，先左向右，新結(jié)點(diǎn)插入位置為左子樹的右子樹，如圖所示。
圖中，當(dāng)結(jié)點(diǎn)8插入后，結(jié)點(diǎn)6的BF為-2，結(jié)點(diǎn)4的BF為-2，不滿足平衡二叉樹的規(guī)則。直接以結(jié)點(diǎn)6為軸心進(jìn)行旋轉(zhuǎn)，并不能使該二叉樹達(dá)到平衡，首先以結(jié)點(diǎn)9為軸心向右旋轉(zhuǎn)。按照單向右旋的方式，旋轉(zhuǎn)后的二叉樹如圖所示。
4.5.2 平衡二叉樹
然后，將該二叉樹以結(jié)點(diǎn)6為軸心向左旋轉(zhuǎn)，如圖所示。
如圖所示，經(jīng)過兩次旋轉(zhuǎn)后的得到二叉樹為平衡二叉樹。
4.5.3 B樹
1.B樹的定義
B樹（B-tree）與平衡二叉樹類似，不同的是，B樹是一種平衡的多路查找樹（結(jié)點(diǎn)的孩子至少有兩個，且每個結(jié)點(diǎn)可以存儲多個數(shù)據(jù)元素）。
數(shù)據(jù)庫中的索引（索引存在于索引文件中，保存在磁盤中，幫助數(shù)據(jù)庫高效獲取數(shù)據(jù)）通常會使用該樹形結(jié)構(gòu)。當(dāng)數(shù)據(jù)庫索引非常大（數(shù)據(jù)量越大，索引文件越大），達(dá)到幾個GB時，無法一次性加載到內(nèi)存，而是逐一加載每一個磁盤頁（對應(yīng)樹的結(jié)點(diǎn)）。然而磁盤讀寫的速度相對于內(nèi)存來說是很慢的，為了減少二者吞吐量相差太多造成的系統(tǒng)消耗，比較好的辦法是減少磁盤讀寫的次數(shù)。
當(dāng)使用樹形結(jié)構(gòu)作為索引時，每一個結(jié)點(diǎn)對應(yīng)一個磁盤頁，減少磁盤讀寫次數(shù)就是縮減樹的高度。因此，B樹“矮胖”的特征，使其更適合作為數(shù)據(jù)庫的索引，其結(jié)點(diǎn)最大的孩子數(shù)量稱為B樹的階，其大小取決于磁盤頁的大小。
4.5.3 B樹
一個M階的B樹具有以下5個特征。
（1）非葉結(jié)點(diǎn)最多只有M個孩子，且M>2。
（2）除根結(jié)點(diǎn)以外的非葉結(jié)點(diǎn)都有k個孩子和k-1個數(shù)據(jù)元素，k值滿足[M/2]。
（3）每一個葉結(jié)點(diǎn)都有k-1個數(shù)據(jù)元素，k值滿足[M/2]。
（4）所有葉結(jié)點(diǎn)都在同一層次。
（5）所有分支結(jié)點(diǎn)的信息數(shù)據(jù)一致(n,A 0 ,K 1 ,A 1 ,K 2 ,A 2, …K n ,A n )，其中：K i (i=1,2,…n)為關(guān)鍵字，且K i ＜K i+1 (i=1,2,…n－1)；A i 為指向孩子結(jié)點(diǎn)的指針，且指針 A i-1 指向子樹中的所有結(jié)點(diǎn)的關(guān)鍵字均小于 K i ，A n ，所指子樹中的所有結(jié)點(diǎn)的關(guān)鍵字均大于 K n ；n為關(guān)鍵字的個數(shù)[M/2]－1≤n≤M－1）。
4.5.3 B樹
圖所示為插入9個數(shù)據(jù)后形成的B樹。
4.5.3 B樹
2.B樹插入結(jié)點(diǎn)的實(shí)現(xiàn)
定義一棵5階的B樹（平衡5路查找），需要插入的結(jié)點(diǎn)數(shù)據(jù)為3、8、31、11、23、29、50、28。當(dāng)前需要組成一棵5路查找樹，則M=5，分支結(jié)點(diǎn)關(guān)鍵字的個數(shù)必須滿足≤4。具體實(shí)現(xiàn)過程如下。
（1）先存入數(shù)據(jù)3、8、31、11，變化過程如圖所示。（省略結(jié)點(diǎn)中表示關(guān)鍵字個數(shù)的表示n與指針 A i 。）
4.5.3 B樹
圖中，存入4個數(shù)據(jù)的結(jié)點(diǎn)已經(jīng)滿足5階，因此再存入數(shù)據(jù)時，需要對該結(jié)點(diǎn)進(jìn)行拆分。拆分的規(guī)則是將中間的數(shù)據(jù)元素提取到雙親結(jié)點(diǎn)上，該數(shù)據(jù)元素左邊的數(shù)據(jù)元素單獨(dú)形成一個結(jié)點(diǎn)，右邊的數(shù)據(jù)元素單獨(dú)形成一個結(jié)點(diǎn)。
（2）再存入數(shù)據(jù)23，變化過程如圖所示。
4.5.3 B樹
（3）再存入數(shù)據(jù)29，所有的結(jié)點(diǎn)都未達(dá)到5階，不用拆分結(jié)點(diǎn)，如圖所示。
（4）再存入數(shù)據(jù)50，結(jié)點(diǎn)達(dá)到5階，如圖所示。
4.5.3 B樹
（5）最后存入數(shù)據(jù)28，由于結(jié)點(diǎn)已經(jīng)達(dá)到5階，此次存入數(shù)據(jù)需要拆分結(jié)點(diǎn)，如圖所示。
3.B樹刪除結(jié)點(diǎn)的實(shí)現(xiàn)
假設(shè)當(dāng)前存在一棵5階的B樹，如圖所示。
4.5.3 B樹
假設(shè)當(dāng)前需要刪除結(jié)點(diǎn)中的數(shù)據(jù)28，由B樹的定義可知，結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)必須大于等于[5/2] ，因此刪除數(shù)據(jù)28將導(dǎo)致結(jié)點(diǎn)不符合B樹的規(guī)則。為了使刪除數(shù)據(jù)后的結(jié)點(diǎn)依然滿足B樹的規(guī)則，在刪除數(shù)據(jù)時需要將結(jié)點(diǎn)進(jìn)行合并。
圖中，如果刪除結(jié)點(diǎn)中的數(shù)據(jù)28，首先需要將其雙親結(jié)點(diǎn)中的數(shù)據(jù)提取到該結(jié)點(diǎn)。提取后的結(jié)果如圖所示。
4.5.3 B樹
圖中，數(shù)據(jù)29替換了數(shù)據(jù)28的位置，原來的雙親結(jié)點(diǎn)只剩余一個數(shù)據(jù)，不滿足B樹的規(guī)則，此時需要將數(shù)據(jù)39提取到雙親結(jié)點(diǎn)，如圖所示。
4.5.4 B+樹與B*樹
1.B+樹
B+樹是B樹的升級版，一棵完整的B+樹具有以下特點(diǎn)。
（1）有k個子樹的分支結(jié)點(diǎn)包含有k個元素，每個元素不保存數(shù)據(jù)，只用來作索引，所有數(shù)據(jù)都保存在葉結(jié)點(diǎn)。
（2）葉結(jié)點(diǎn)在B+樹的最底層（所有葉結(jié)點(diǎn)都在同一層），葉結(jié)點(diǎn)中存放索引值、指向記錄的指針、指向下一個葉結(jié)點(diǎn)的指針。葉結(jié)點(diǎn)按照關(guān)鍵字的大小，從小到大順序鏈接。
（3）所有分支結(jié)點(diǎn)的元素都同時存在于子結(jié)點(diǎn)中，并且在子結(jié)點(diǎn)中是最大或最小的元素。
創(chuàng)建一棵完整的B+樹，如圖所示。（為了更加清晰地展示B+樹的結(jié)點(diǎn)，圖中分支結(jié)點(diǎn)忽略指針部分，特此說明。）
4.5.4 B+樹與B*樹
由圖可知，B+樹中的結(jié)點(diǎn)之間存在重復(fù)的元素，同時每一個葉結(jié)點(diǎn)都有指針指向右邊的下一個葉結(jié)點(diǎn)，形成一個有序的鏈表。根結(jié)點(diǎn)的最大元素（圖中為17）也是整個B+樹的最大元素，無論插入或刪除多少元素，始終要保持最大元素在根結(jié)點(diǎn)中。
需要注意的是，B+樹中只有葉結(jié)點(diǎn)包含數(shù)據(jù)，其余分支結(jié)點(diǎn)只作為索引，沒有任何數(shù)據(jù)關(guān)聯(lián)，如圖所示。
4.5.4 B+樹與B*樹
B+樹的優(yōu)勢主要體現(xiàn)在查詢性能上，在查詢單個元素時，B+樹會從根結(jié)點(diǎn)向下逐層查找，最終匹配到葉結(jié)點(diǎn)。假設(shè)當(dāng)前需要查詢圖中的數(shù)據(jù)元素7，則一共需要3次磁盤頁的讀寫來完成，如圖所示。
4.5.4 B+樹與B*樹
由圖可知，雖然B+樹與B樹的查找流程類似，但是B+樹的分支結(jié)點(diǎn)不保存數(shù)據(jù)，同樣大小的磁盤頁，B+樹可以存放更多的元素。也就是說，數(shù)據(jù)量相同的情況下，B+樹的結(jié)構(gòu)比B樹更加“矮胖”，查詢數(shù)據(jù)時磁盤讀寫的次數(shù)更少。
在B+樹中查詢數(shù)據(jù)必須查找到葉結(jié)點(diǎn)，而在B樹中，數(shù)據(jù)元素可以存在于分支結(jié)點(diǎn)，也可以存在于葉結(jié)點(diǎn)，這導(dǎo)致B樹的查找性能并不穩(wěn)定（最壞的情況是查找到葉結(jié)點(diǎn)，最好的情況是查找根結(jié)點(diǎn)）。相反，B+樹每一次查找都是穩(wěn)定的。
如果查找為范圍查找，則B+樹的優(yōu)勢會更加明顯。假設(shè)當(dāng)前存在一棵完整的B樹，如圖所示，采用中序遍歷，查找數(shù)據(jù)元素3到11。
4.5.4 B+樹與B*樹
由圖可知，對B樹進(jìn)行范圍查找是比較煩瑣的。而B+樹在進(jìn)行范圍查找時，只需要對鏈表直接做遍歷。如圖所示。
在B+樹中，先查數(shù)據(jù)元素為3、5的結(jié)點(diǎn)，再查找數(shù)據(jù)元素為6、8的結(jié)點(diǎn)，最后查找數(shù)據(jù)元素為9、11的結(jié)點(diǎn)，遍歷結(jié)束。顯然，在鏈表中直接順序遍歷要比B樹的中序遍歷簡單。
4.5.4 B+樹與B*樹
2.B*樹
B*樹是B+樹的變體，B*樹不同于B+樹的是：其非根和非葉結(jié)點(diǎn)上增加了指向兄弟結(jié)點(diǎn)的指針。因此，對于一個M階的B*樹來說，非葉結(jié)點(diǎn)的關(guān)鍵字個數(shù)至少為(2/3)*M。
對于B+樹來說，當(dāng)一個結(jié)點(diǎn)滿時，將分配一個新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在雙親結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針。因此，B+樹的分裂只影響原結(jié)點(diǎn)和雙親結(jié)點(diǎn)，而不會影響兄弟結(jié)點(diǎn)（不需要指向兄弟的指針）。
而對于B*樹來說，當(dāng)一個結(jié)點(diǎn)滿時，如果它的下一個兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中，再在原結(jié)點(diǎn)中插入關(guān)鍵字，最后修改雙親結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍發(fā)生改變）。如果兄弟結(jié)點(diǎn)已滿，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在雙親結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針。
4.5.5 紅黑樹
紅黑樹（Red Black Tree）是一種自平衡二叉查找樹，又可以稱為平衡二叉B樹（Symmetric binary B-tree）。因此，紅黑樹和平衡二叉樹類似，都是在進(jìn)行插入和刪除操作時通過特定的操作保持二叉排序樹的平衡，從而獲得較高的查找性能。紅黑樹的每個結(jié)點(diǎn)上都有存儲位來表示結(jié)點(diǎn)的顏色，即紅或者黑。
一棵完整的紅黑樹滿足以下4條規(guī)則。
（1）每個結(jié)點(diǎn)或者是黑色，或者是紅色。
（2）每個葉結(jié)點(diǎn)都是黑色（葉結(jié)點(diǎn)都為NIL或NULL），根結(jié)點(diǎn)是黑色。
（3）如果一個結(jié)點(diǎn)是紅色的，則它的子結(jié)點(diǎn)必須是黑色的。
（4）任意一個結(jié)點(diǎn)到其葉結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。
根據(jù)上述最后一個規(guī)則可以推導(dǎo)出：如果一個結(jié)點(diǎn)存在黑子結(jié)點(diǎn)，那么該結(jié)點(diǎn)肯定有兩個子結(jié)點(diǎn)。
4.5.5 紅黑樹
上述規(guī)則使得紅黑樹可以達(dá)到自平衡的狀態(tài)，如圖所示。
4.5.5 紅黑樹
當(dāng)對紅黑樹進(jìn)行結(jié)點(diǎn)的插入或刪除時，紅黑樹的平衡就會被破壞，此時就需要對該樹進(jìn)行調(diào)整，以達(dá)到新的平衡。例如，在圖所示的紅黑樹中插入新結(jié)點(diǎn)，如圖所示。
4.5.5 紅黑樹
圖中，插入的新結(jié)點(diǎn)為21（紅），結(jié)點(diǎn)21的雙親結(jié)點(diǎn)22同樣為紅，因此不滿足紅黑樹的規(guī)則，即紅結(jié)點(diǎn)的子結(jié)點(diǎn)必須為黑結(jié)點(diǎn)。實(shí)現(xiàn)紅黑樹平衡有兩種方式，變色與旋轉(zhuǎn)。
由圖可知，新插入的結(jié)點(diǎn)21為紅，因此需要改變結(jié)點(diǎn)22，使之變?yōu)楹冢鐖D所示。（截取圖所示的紅黑樹中需要操作的部分）。
4.5.5 紅黑樹
圖中，修改結(jié)點(diǎn)22為黑后，其雙親結(jié)點(diǎn)25為黑，不滿足紅黑樹的最后一條規(guī)則，因此需要改變結(jié)點(diǎn)25為紅，如圖所示。
圖中結(jié)點(diǎn)25與結(jié)點(diǎn)27都為紅，不滿足紅黑樹的規(guī)則。再次修改結(jié)點(diǎn)27為黑，如圖所示，完成修改后該截取的部分滿足紅黑樹的規(guī)則。
4.5.5 紅黑樹
上述變色操作只解決了截取部分的規(guī)則問題。如圖所示，整個紅黑樹仍然不滿足規(guī)則。
4.5.5 紅黑樹
圖中，結(jié)點(diǎn)17與結(jié)點(diǎn)25都為紅，不滿足紅黑樹的規(guī)則。如果選擇修改結(jié)點(diǎn)17為黑，則結(jié)點(diǎn)13與結(jié)點(diǎn)17同為黑，依然不滿足規(guī)則。因此，通過變色已經(jīng)無法解決當(dāng)前問題，需要結(jié)合旋轉(zhuǎn)的方式。
紅黑樹的旋轉(zhuǎn)操作可以參考4.5.2節(jié)中平衡二叉樹的旋轉(zhuǎn)操作，將圖所示的紅黑樹以結(jié)點(diǎn)17為軸心向左旋轉(zhuǎn)，如圖所示。
4.5.5 紅黑樹
圖中，旋轉(zhuǎn)后結(jié)點(diǎn)17成為根結(jié)點(diǎn)，其左子樹成為結(jié)點(diǎn)13的右子樹。
根據(jù)紅黑樹的規(guī)則（根結(jié)點(diǎn)必須為黑），需要再次進(jìn)行變色操作，將結(jié)點(diǎn)17變?yōu)楹冢瑒t結(jié)點(diǎn)13需要變?yōu)榧t，結(jié)點(diǎn)8需要變?yōu)楹冢Y(jié)點(diǎn)1與結(jié)點(diǎn)11需要變?yōu)榧t，結(jié)點(diǎn)6需要變?yōu)楹凇Ｈ鐖D所示。
4.5.5 紅黑樹
圖中，經(jīng)過變色處理后的紅黑樹仍然不滿足規(guī)則。例如，結(jié)點(diǎn)13到其葉結(jié)點(diǎn)的路徑經(jīng)過的黑色結(jié)點(diǎn)數(shù)量不同。接下來，需要再次使用旋轉(zhuǎn)的方式實(shí)現(xiàn)紅黑樹平衡。
將圖所示的紅黑樹以結(jié)點(diǎn)8為軸心向右旋轉(zhuǎn)，如圖所示。
4.5.5 紅黑樹
對圖所示的紅黑樹再次進(jìn)行變色操作，結(jié)點(diǎn)8變?yōu)榧t，結(jié)點(diǎn)1與結(jié)點(diǎn)13變?yōu)楹冢Y(jié)點(diǎn)6與結(jié)點(diǎn)15變?yōu)榧t，如圖所示。
圖所示為滿足規(guī)則的紅黑樹，可見該紅黑樹達(dá)到平衡狀態(tài)。其他插入或刪除結(jié)點(diǎn)的情況，可參考上述操作過程實(shí)現(xiàn)平衡。
本章小結(jié)
本章主要介紹了一種非線性數(shù)據(jù)結(jié)構(gòu)——樹。其中，重點(diǎn)介紹了二叉樹的概念、性質(zhì)以及具體的代碼實(shí)現(xiàn)。讀者需要重點(diǎn)掌握二叉樹的特性并熟練編寫二叉樹的操作代碼，尤其是二叉樹的先序遍歷、中序遍歷以及后序遍歷。本章最后介紹了一些常見的特殊樹形結(jié)構(gòu)，包括赫夫曼樹、二叉排序樹、平衡二叉樹、紅黑樹以及系列B樹。望讀者理解這些特殊樹形結(jié)構(gòu)的概念以及設(shè)計(jì)原理，從而擴(kuò)展視野，為處理復(fù)雜樹形結(jié)構(gòu)的開發(fā)奠定基礎(chǔ)。

展開更多......

收起↑