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

B1《可視化計算》二叉樹

二叉樹(Binary

Tree)是指樹的度為2的有序樹。它是一種最簡單、而且最重要的樹，在計算機科學領域有著廣泛地應用

定義

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

二叉樹上終端節點數等于雙分支節點數加1

二叉樹上第i層上至多有2i-1個節點(i≥1)

性質3深度為h的二叉樹至多有2h-1個節點4滿二叉樹(a)和完全二叉樹

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

順序存儲結構

順序存儲一棵二叉樹時，首先對該樹中每個節點進行編號，然后以各節點的編號為下標，把各節點的值對應存儲到一維數組中。樹中各節點的編號與等深度的完全二叉樹中對應位置上節點的編號相同順序存儲的二叉樹8二叉樹的存儲結構

鏈接存儲結構

在二叉樹的鏈接存儲：在每個節點中設置三個域：值域、左指針域和右指針域，其節點結構如下圖：LeftdataRightdata表示值域，用于存儲放入節點的數據元素，

left和right分別表示左指針域和右指針域，用以分別存儲左子和右子節點的存貯位置9二叉樹的存儲結構

在節點結構中再增加一個parent指針域，用來指向其父節點

這種存儲結構既便于查找子節點，也便于查找父節點10二叉鏈表的字符串數組表達11帶父節點的二叉鏈表字符串表達12在RAPTOR中建立二叉樹13二叉樹的遍歷

二叉樹的遍歷是二叉樹中所有其它運算的基礎

二叉樹的遍歷是指按照一定次序訪問樹中所有節點，并且每個節點的值僅被訪問一次的過程

根據二叉樹的遞歸定義，遍歷一棵非空二叉樹的問題可分解為三個子問題：

訪問根節點

遍歷左子樹

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

堆排序(Heap

Sort)是一樹形選擇排序。

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

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

所以堆排序有兩個過程組成

建堆的過程；

調用建堆調整函數實現排序的過程17堆的基本操作18

1.建堆：數組具有對應的樹表示形式

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

2.插入一個元素：新元素被加入到表中

隨后樹被更新以恢復堆次序

3.刪除一個元素：刪除總是發生在根（root）節點處

用表中的最后一個元素來填補空缺位置，結果樹被更新以恢復堆的性質堆排序過程19

請對對關鍵字序列14，15，32，68，54，100，876，45，32，10建堆并排序輸出堆排序實現說明20為調試方便，將排序數據放在文件

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

在第一輪循環中，用于建堆；②

在heap_sort_output中，用于調整堆排序流程

Main子圖21堆排序流程

creatheap子程序22堆排序流程

heap_sort_output

子圖23堆排序的應用場合

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

堆排序則是每次輸出一個堆頂元素，然后對堆進行再調整，保證堆頂元素總是當前剩下元素的最大或最小

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

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

1.若它的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；

2.若它的右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；

3.它的左、右子樹也分別為二叉搜索樹。25二叉搜索樹的例子26二叉搜索樹的優點

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

但它支持動態查詢（當搜索關鍵詞沒有在二叉搜索樹中時，可以進行插入，這是該算法有別于大部分查找算法的特點）

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

是一種好的動態排序方法27構造二叉搜索樹

使用隨機數產生一個無序序列，用該序列構造二叉搜索樹，并使用金字塔（下圖）的形式輸出該樹，以及排序結果28二叉搜索樹的構建說明29

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

為了簡化算法，本例沒有將動態插入的功能列入，有興趣者可自行設計二叉搜索樹的主要模塊（I）30

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

init_first子圖首次初始化使用隨機數產

生待排序數組a[]；數組元素個數可以設定；對兩個BST的指針數組l[]、r[]分別進行初

始化

binary_sort子圖進行BST的構建；二叉搜索樹31

Main子圖二叉搜索樹32

init_first子圖二叉搜索樹33

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

init_second子圖進行第二次初始化，創建

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

binary_take_out子圖實現輸出金字塔式數組b[]的填充

binary_output子圖進行數組形式的BST輸出；

sort子程序進行BST排序結果的輸出二叉搜索樹35

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

binary_output子圖38二叉搜索樹39