《可視化計(jì)算》第6章信息論哈夫曼編碼與二叉樹(B)

第6章信息論、哈夫曼編碼與二叉樹PART

B1《可視化計(jì)算》二叉樹

二叉樹(Binary

Tree)是指樹的度為2的有序樹。它是一種最簡(jiǎn)單、而且最重要的樹，在計(jì)算機(jī)科學(xué)領(lǐng)域有著廣泛地應(yīng)用

定義

二叉樹或者是一棵空樹，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的分別稱作根的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是一棵二叉樹2二叉樹的例子3二叉樹重要性質(zhì)

二叉樹上終端節(jié)點(diǎn)數(shù)等于雙分支節(jié)點(diǎn)數(shù)加1

二叉樹上第i層上至多有2i-1個(gè)節(jié)點(diǎn)(i≥1)

性質(zhì)3深度為h的二叉樹至多有2h-1個(gè)節(jié)點(diǎn)4滿二叉樹(a)和完全二叉樹

(b)5理想平衡樹(a)和普通二叉樹(b)理想平衡樹包含滿二叉樹和完全二叉樹，但不一定是完全二叉樹（a）6二叉樹的存儲(chǔ)結(jié)構(gòu)7

順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)一棵二叉樹時(shí)，首先對(duì)該樹中每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，然后以各節(jié)點(diǎn)的編號(hào)為下標(biāo)，把各節(jié)點(diǎn)的值對(duì)應(yīng)存儲(chǔ)到一維數(shù)組中。樹中各節(jié)點(diǎn)的編號(hào)與等深度的完全二叉樹中對(duì)應(yīng)位置上節(jié)點(diǎn)的編號(hào)相同順序存儲(chǔ)的二叉樹8二叉樹的存儲(chǔ)結(jié)構(gòu)

鏈接存儲(chǔ)結(jié)構(gòu)

在二叉樹的鏈接存儲(chǔ)：在每個(gè)節(jié)點(diǎn)中設(shè)置三個(gè)域：值域、左指針域和右指針域，其節(jié)點(diǎn)結(jié)構(gòu)如下圖：LeftdataRightdata表示值域，用于存儲(chǔ)放入節(jié)點(diǎn)的數(shù)據(jù)元素，

left和right分別表示左指針域和右指針域，用以分別存儲(chǔ)左子和右子節(jié)點(diǎn)的存貯位置9二叉樹的存儲(chǔ)結(jié)構(gòu)

在節(jié)點(diǎn)結(jié)構(gòu)中再增加一個(gè)parent指針域，用來(lái)指向其父節(jié)點(diǎn)

這種存儲(chǔ)結(jié)構(gòu)既便于查找子節(jié)點(diǎn)，也便于查找父節(jié)點(diǎn)10二叉鏈表的字符串?dāng)?shù)組表達(dá)11帶父節(jié)點(diǎn)的二叉鏈表字符串表達(dá)12在RAPTOR中建立二叉樹13二叉樹的遍歷

二叉樹的遍歷是二叉樹中所有其它運(yùn)算的基礎(chǔ)

二叉樹的遍歷是指按照一定次序訪問(wèn)樹中所有節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)的值僅被訪問(wèn)一次的過(guò)程

根據(jù)二叉樹的遞歸定義，遍歷一棵非空二叉樹的問(wèn)題可分解為三個(gè)子問(wèn)題：

訪問(wèn)根節(jié)點(diǎn)

遍歷左子樹

遍歷右子樹。14前序遍歷算法15堆排序

堆排序(Heap

Sort)是一樹形選擇排序。

父節(jié)點(diǎn)值大于或等于其子節(jié)點(diǎn)值的，叫“大根堆”（a）;父節(jié)點(diǎn)值小于或等于子節(jié)點(diǎn)值的，叫“小根堆”(b)16堆排序原理

堆排序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆底（堆的最后一個(gè)元素）交換位置

所以堆排序有兩個(gè)過(guò)程組成

建堆的過(guò)程；

調(diào)用建堆調(diào)整函數(shù)實(shí)現(xiàn)排序的過(guò)程17堆的基本操作18

1.建堆：數(shù)組具有對(duì)應(yīng)的樹表示形式

一般情況下，樹并不滿足堆的條件；通過(guò)重新排列元素，可以建立一棵“堆化”的樹

2.插入一個(gè)元素：新元素被加入到表中

隨后樹被更新以恢復(fù)堆次序

3.刪除一個(gè)元素：刪除總是發(fā)生在根（root）節(jié)點(diǎn)處

用表中的最后一個(gè)元素來(lái)填補(bǔ)空缺位置，結(jié)果樹被更新以恢復(fù)堆的性質(zhì)堆排序過(guò)程19

請(qǐng)對(duì)對(duì)關(guān)鍵字序列14，15，32，68，54，100，876，45，32，10建堆并排序輸出堆排序?qū)崿F(xiàn)說(shuō)明20為調(diào)試方便，將排序數(shù)據(jù)放在文件

data.txt中，其中，第一個(gè)數(shù)據(jù)表示參與排序的數(shù)據(jù)個(gè)數(shù)(n)，后面則跟隨排序數(shù)據(jù)；在main子圖中，算法進(jìn)行了建堆運(yùn)算；creatheap子程序在建堆和排序輸出兩個(gè)過(guò)程中都會(huì)用到，①

在第一輪循環(huán)中，用于建堆；②

在heap_sort_output中，用于調(diào)整堆排序流程

Main子圖21堆排序流程

creatheap子程序22堆排序流程

heap_sort_output

子圖23堆排序的應(yīng)用場(chǎng)合

一般的快速排序，歸并排序都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部序列；

堆排序則是每次輸出一個(gè)堆頂元素，然后對(duì)堆進(jìn)行再調(diào)整，保證堆頂元素總是當(dāng)前剩下元素的最大或最小

欲在一個(gè)大量數(shù)據(jù)的文件中，如含有5000個(gè)元素的記錄文件中選取前10個(gè)最大的元素，可采用堆排序24二叉搜索樹

是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

1.若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；

2.若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；

3.它的左、右子樹也分別為二叉搜索樹。25二叉搜索樹的例子26二叉搜索樹的優(yōu)點(diǎn)

在二叉搜索樹中進(jìn)行查找的最糟時(shí)間復(fù)雜度為O(n)，等于順序查找；

但它支持動(dòng)態(tài)查詢（當(dāng)搜索關(guān)鍵詞沒有在二叉搜索樹中時(shí)，可以進(jìn)行插入，這是該算法有別于大部分查找算法的特點(diǎn)）

有很多二叉搜索樹改良算法可以使樹高為logn，如AVL樹等

是一種好的動(dòng)態(tài)排序方法27構(gòu)造二叉搜索樹

使用隨機(jī)數(shù)產(chǎn)生一個(gè)無(wú)序序列，用該序列構(gòu)造二叉搜索樹，并使用金字塔（下圖）的形式輸出該樹，以及排序結(jié)果28二叉搜索樹的構(gòu)建說(shuō)明29

本例采用順序形式保存二叉搜索樹（BST）并輸出排序結(jié)果，另外，需要考慮二叉搜索樹的“金字塔”形式的輸出（展示各種隨機(jī)產(chǎn)生的二叉搜索樹的特點(diǎn)）

為了簡(jiǎn)化算法，本例沒有將動(dòng)態(tài)插入的功能列入，有興趣者可自行設(shè)計(jì)二叉搜索樹的主要模塊（I）30

main子圖控制算法的整體流程

init_first子圖首次初始化使用隨機(jī)數(shù)產(chǎn)

生待排序數(shù)組a[]；數(shù)組元素個(gè)數(shù)可以設(shè)定；對(duì)兩個(gè)BST的指針數(shù)組l[]、r[]分別進(jìn)行初

始化

binary_sort子圖進(jìn)行BST的構(gòu)建；二叉搜索樹31

Main子圖二叉搜索樹32

init_first子圖二叉搜索樹33

binary_sort子圖二叉搜索樹主要模塊（II）34

init_second子圖進(jìn)行第二次初始化，創(chuàng)建

b[]向量數(shù)組，用于數(shù)組形式的BST的存貯

binary_take_out子圖實(shí)現(xiàn)輸出金字塔式數(shù)組b[]的填充

binary_output子圖進(jìn)行數(shù)組形式的BST輸出；

sort子程序進(jìn)行BST排序結(jié)果的輸出二叉搜索樹35

init_second子圖二叉搜索樹：binary_take_out子圖（I）36二叉搜索樹：binary_take_out子圖（II）37二叉搜索樹

binary_output子圖38二叉搜索樹39