7.5二分搜寻树及其应用.PDFVIP

Chapter 7 資料結構 7-19 後序表示法（postfix ）：又稱後置波蘭表示法（reverse polish notation ）。 [運算元1][運算元2][運算子] ，例如：ab+ 。 四、表示法轉換 我們如何將中序表示法轉換成前序表示法及後序表示法呢？ 方法一：考慮運算子的優先權及結合性將他們括號起來，再將運算子取 代相對應的括號，取代時運算子置左為前序表示法，置右為後序表 示法。 方法二：建立相對應之二元樹，利用前序追蹤可得前序表示法，利用後 序追蹤可得後序表示法。 前序與後序表示法較中序為佳，這是因為前序與後序沒有左、右 結合性及優先權之考量，掃瞄一次即可求算結果。而前序與後序表示 法中又以後序為最好，因為後序式使用之堆疊（stack ）數目為一個， 較前序式少。最後，要決定唯一的一顆二元樹（tree ），需要中序及後 序或中序及前序這兩種組合才行。 End 7.5 二分搜尋樹及其應用 重要性： 一、二分搜尋樹（Binary Search Tree ） 二分搜尋樹是一個二元樹。它可能是空的，若不是空的，則它具備下 列特性： 一、二分搜尋樹中每個元素都有一個惟一的鍵值（unique key value ），即任兩個元素不會有相同的鍵值。 二、非空左子樹中所有節點的鍵值必定小於樹根的鍵值。 三、非空右子樹中所有節點的鍵值必定大於樹根的鍵值。 四、左子樹與右子樹也都是二分搜尋樹。 7-20 Chapter 7 資料結構 如下圖即為一例： 16 6 36 8 20 二、霍夫曼編碼（Huffman Code ） 霍夫曼編碼也是一個二元樹的應用。其目的是為了要縮短訊息的總長 度，採用非固定長度的編碼方式，根據各別符號出現之頻率來編碼，頻率 較高者編碼長度較短，頻率較低者編碼長度較長。編碼方式如下： 先找出所有符號的頻率。 合併頻率最低的兩個，頻率相加。 重覆步驟2 ，合併到只剩下一個為止。 根據合併的關係，對每一次合併的兩項皆分別配置一個位元，一個 配置“0＂；另一個配置“1＂。 舉例說明如下： 若一系統有五個符號，其頻率如下表，請編出一套霍夫曼碼。 符號 a b c d e 頻率 0.35 0.20 0.18 0.15 0.12 若有一訊息0110110011000011 ，請以之編碼方式，將其解碼。 【解】  1.0 0 1 0.38 0.62 0 1 0 1 c b 0.27 a 0 1 e d