1、1,樹,樹形結(jié)構(gòu)（包括樹和二叉樹）是一種非常重要的結(jié)構(gòu)。由于樹形結(jié)構(gòu)中的各子結(jié)構(gòu)與整個(gè)結(jié)構(gòu)具有相似的特性，因而其算法大多采用遞歸形式，這對(duì)許多初學(xué)者來(lái)說(shuō)是一個(gè)難點(diǎn)。,2,主要內(nèi)容,1、樹的定義及基本術(shù)語(yǔ),2、二叉樹的定義及性質(zhì),3、滿二叉樹和完全二叉樹及性質(zhì),5、遍歷二叉樹,4、二叉樹的存儲(chǔ)結(jié)構(gòu),6、赫夫曼（huffman）樹,3,1、樹的定義與運(yùn)算,定義：樹T是n個(gè)結(jié)點(diǎn)構(gòu)成的有限集合(n0)，其中有一個(gè)結(jié)點(diǎn)叫根，其余結(jié)點(diǎn)可劃分為m個(gè)互不相交的子集T1,T2Tm (m0)，并且這m個(gè)子集本身又構(gòu)成樹，稱為T的子樹。 注意：本書沒(méi)有給出空樹的概念，即節(jié)點(diǎn)數(shù)至少為1。,4,樹結(jié)構(gòu)的表現(xiàn)形式及相關(guān)概

2、念,圖形表示法：見(jiàn)下圖,結(jié)點(diǎn):包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支 結(jié)點(diǎn)的度:結(jié)點(diǎn)擁有的子樹 根結(jié)點(diǎn)：例如A 葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn) 分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn) 孩子節(jié)點(diǎn)、父節(jié)點(diǎn)、兄弟節(jié)點(diǎn)、祖先節(jié)點(diǎn)、后代節(jié)點(diǎn) 層次：從根開始定義，根為第一層。 樹的深度（高度）：樹中結(jié)點(diǎn)的最大層次 有序樹、無(wú)序樹：樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的（不能互換）為有序的.最左邊的子樹的根稱為第一個(gè)孩子，最右邊的稱為最后一個(gè)孩子。 森林:互不相交的樹的集合,5,2 、 二叉樹,7.2.1 定義：二叉樹T是n個(gè)結(jié)點(diǎn)的有限集合，其中n0,當(dāng)n=0時(shí)，為空樹，否則，其中有一個(gè)結(jié)點(diǎn)為

3、根結(jié)點(diǎn)，其余結(jié)點(diǎn)劃分為兩個(gè)互不相交的子集TL、TR，并且TL、TR分別構(gòu)成叫作左、右子樹的二叉樹。 二叉樹另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。,6,2.1 二叉樹性質(zhì),性質(zhì)1：在二叉樹的第i層上的結(jié)點(diǎn)數(shù)2i-1（i0） （在二叉樹的第i層上至多有2i-1 個(gè)結(jié)點(diǎn)）,性質(zhì)2：深度為k的二叉樹的結(jié)點(diǎn)數(shù)2k-1（k0） (深度為K的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)),性質(zhì)3：對(duì)任一棵非空的二叉樹T，如果其葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有下面的關(guān)系式成立：n0=n2+1,7,3、滿二叉樹、完全二叉樹,

4、滿二叉樹的定義：一棵深度為K且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉數(shù) 特點(diǎn)：是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù) 完全二叉樹定義：深度為K的，有N個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1到N的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹,8,3.1完全二叉樹的特點(diǎn),具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1 在編號(hào)的完全二叉樹中，各結(jié)點(diǎn)的編號(hào)之間的關(guān)系為：編號(hào)為i的結(jié)點(diǎn)如果存在左孩子，則其編號(hào)為2i，如果存在右孩子，則其編號(hào)為2i+1，如果存在父結(jié)點(diǎn)，則其編號(hào)為i/2,9,4、 二叉樹存儲(chǔ)4.1順序存儲(chǔ)二叉數(shù),按完全二叉樹的編號(hào)次序進(jìn)行，即編號(hào)為i的結(jié)點(diǎn)存儲(chǔ)在數(shù)組中下標(biāo)為i的元素

5、中；,若二叉樹不是完全二叉樹形式，則為了保持結(jié)點(diǎn)之間的關(guān)系，不得不空出許多元素來(lái)，因?yàn)?，在最壞的情況下，一個(gè)深度為K且只有K個(gè)結(jié)點(diǎn)的單支樹（樹中不存在度為2的結(jié)點(diǎn)）卻需要長(zhǎng)度為2k-1的一維數(shù)組。這就造成了空間的浪費(fèi)。為此，依據(jù)實(shí)際結(jié)點(diǎn)數(shù)來(lái)分配存儲(chǔ)空間，這就涉及到了動(dòng)態(tài)鏈表結(jié)構(gòu)。,10,4.2 二叉鏈表,二叉鏈表結(jié)構(gòu)描述： typedef char datatype； typedef struct datatype data; struct Bnode *lchild, *rchild; Bnode;,存儲(chǔ)結(jié)點(diǎn)值的數(shù)據(jù)域data,指向右孩子結(jié)點(diǎn)的指針,指向左孩子結(jié)點(diǎn)的指針,11,5、二叉樹的遍

6、歷,遍歷二叉樹是指按某種次序訪問(wèn)二叉樹中每個(gè)節(jié)點(diǎn)一次且僅一次。,12,例題：看下圖,先序遍歷：-+a*b-cd/ef 前綴表達(dá)式（波蘭式）,中序遍歷：a+b*c-d-e/f 中綴表達(dá)式,后序遍歷：abcd-*+ef/- 后綴表達(dá)式（逆波蘭式）,13,遍歷算法例題（2）,已知二叉樹的先序和中序序列如下，試構(gòu)造出相應(yīng)的二叉樹。 先序：ABCDEFGHIJ 中序：CDBFEAIHGJ 原理：先序序列的第一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn) 中序序列根結(jié)點(diǎn)處于左右子樹的中序序列之間 注意：二叉樹的先序和后序序列不能唯一確定一棵二叉樹，但由先序和中序或后序和中序序列能唯一確定一棵二叉樹。,先序：ABCDEFGHIJ 中序：

7、CDBFEAIHGJ,14,6、 哈夫曼樹（最優(yōu)二叉樹）,設(shè)計(jì)一個(gè)將百分成績(jī)轉(zhuǎn)換為等級(jí)制的算法，具體要求如下： A：90100 B：8089 C：7079 D：6069 E：059,如何判斷才能最省時(shí)間？,15,哈夫曼樹,給定一組數(shù)值w1，w2，wn作為葉子結(jié)點(diǎn)的權(quán)值，構(gòu)造一棵二叉樹。如果wiLi最小，則稱此二叉樹為最優(yōu)二叉樹，也稱哈夫曼樹。并稱wiLi為帶權(quán)路徑長(zhǎng)度。 哈夫曼算法： 根據(jù)給定的n個(gè)權(quán)值w1,w2,，wn，構(gòu)成n棵二叉樹的集合T=T1,T2,Tn，其中每個(gè)Ti只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹均空。 從T中選兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹，不妨設(shè)為T1、T2作為左右子樹構(gòu)成一棵新的二叉樹T1，并且置新二叉樹的根值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。 將新二叉樹T1并入到T中，同時(shí)從T中刪除T1、T2。 重復(fù)(2)、(3)，直到T中只有一棵樹為止。,16,例題,以集合3,4,5,6,8,10,12,18為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，并計(jì)算其帶權(quán)路