通信原理大綜合課件軟件

在此幻燈片插入公司的徽標(biāo)從“插入”菜單選擇圖片找到徽標(biāo)文件單擊“確定”重新設(shè)置徽標(biāo)大小單擊徽標(biāo)內(nèi)任意位置?；諛?biāo)外部出現(xiàn)的方框是“調(diào)整控點(diǎn)”使用這些重新設(shè)置對(duì)象大小如果在使用尺寸調(diào)整控點(diǎn)前按下shift鍵，則對(duì)象改變大小但維持原比例。DATA1065865姓名學(xué)號(hào)成績(jī)班級(jí)李紅976105995機(jī)97.6ABCDEFG數(shù)據(jù)結(jié)構(gòu)2024/10/1622.5樹2.5.1樹的定義：由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合。僅有一個(gè)根結(jié)點(diǎn)，結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系?？捎萌缦玛P(guān)系表示：

<祖父，伯父>，<祖父，父親>，<祖父，叔父>，<伯父，堂兄>，

<伯父，堂姐>，<父親，你>，<叔父，堂弟>，<堂兄，侄兒>

其余數(shù)據(jù)元素可分為m(m>=0)個(gè)互不相交的(非空)有限集T1,T2,…,Tm,其中每一個(gè)子集本身又是一棵符合本定義的樹。

A

B

CDE

G

HIL

KT1T2T3FJ

M2024/10/163結(jié)點(diǎn)（Node）：樹中的元素。結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)擁有的子樹數(shù)。葉子（Leaf）：度為零的結(jié)點(diǎn)，也稱端結(jié)點(diǎn)。孩子（Child）：結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。兄弟（Sibling）：同一雙親的孩子。雙親（Parent）：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)，稱為這些結(jié)點(diǎn)的雙親深度（Depth)：樹中結(jié)點(diǎn)的最大層次數(shù)。森林（Forest）：M棵互不相交的樹的集合。介紹幾個(gè)概念：ABCDEGHILK

FJ

M2024/10/1642.5.2二叉樹（BinaryTree）1、二叉樹的定義及其性質(zhì)

(1)二叉樹的定義(a)空二叉樹(b)僅有跟結(jié)點(diǎn)(c)(d)(e)二叉樹的五種基本形態(tài)一種特殊的樹型結(jié)構(gòu)，特點(diǎn)是樹中每個(gè)結(jié)點(diǎn)只有兩棵子樹，且子樹有左右之分，次序不能顛倒。2024/10/165證明用歸納法：

i=1,則結(jié)點(diǎn)數(shù)=20=1為根結(jié)點(diǎn)若已知i-1層上結(jié)點(diǎn)數(shù)至多有2i-1-1=2i-2為個(gè)，由于二叉樹每個(gè)結(jié)點(diǎn)度數(shù)最大為2，因此第i層上結(jié)點(diǎn)數(shù)最多為第i-1層上結(jié)點(diǎn)數(shù)的2倍，即2×2i-2=2i-1.(2)二叉樹的性質(zhì)二叉樹的基本性質(zhì)：ABCDEFB、

深度為h的二叉樹中至多含有2h-1個(gè)結(jié)點(diǎn)。

hh∑(第i層上的最大結(jié)點(diǎn)數(shù))=∑2i-1=2h-1i=1i=1A、

二叉樹的第i層上至多有2i-1（i

1）個(gè)結(jié)點(diǎn)。C、

若在任意一棵二叉樹中，有n0個(gè)葉子結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，則：n0=n2+12024/10/166（3）滿二叉樹423156789101112131415（4）完全二叉樹842315679101112完全二叉樹423156789101112非完全二叉樹特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。完全二叉樹:指深度為k的，有n個(gè)結(jié)點(diǎn)的，且每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。2024/10/167（5）樹與二叉樹的區(qū)別A樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，二叉樹結(jié)點(diǎn)最大度數(shù)為2。B樹的結(jié)點(diǎn)子樹無(wú)左右之分，二叉樹的結(jié)點(diǎn)子樹有明確的左右之分。

二叉樹樹2024/10/1682、二叉樹的存儲(chǔ)結(jié)構(gòu)

(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)T[16]若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。ABcFED

●●●●●●●●●124

8

91011563712131415(1)順序存儲(chǔ)結(jié)構(gòu)(1)順序存儲(chǔ)結(jié)構(gòu)用一組連續(xù)的存儲(chǔ)單元存放二叉樹的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。FEDCBA15141312111098765432102h-1=24-1=152024/10/169(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：

用具有兩個(gè)指針域的鏈表（二叉鏈表）作為二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域、左指針域和右指針域組成。lchildDatarchild^ADB^C^^E^^F^一般二叉樹的二叉鏈表結(jié)構(gòu)2024/10/1610鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述TypedefstructBiTNode{intdata;StructBiTNode*lchild,*rchild;}BiTNode,*BiTree;lchildDatarchildlchildDatarchild2024/10/16113、將樹和森林轉(zhuǎn)換為二叉樹

由于二叉樹可以用二叉鏈表表示，為了使一般樹也能用二叉鏈表表示，必須找出樹與二叉樹之間的關(guān)系。（1）樹轉(zhuǎn)換為二叉樹

A

B

CDE

G

HFI(1)②在兄弟之間加一條連線；

I

A

B

C

DEF

G

H(2)方法：①對(duì)每個(gè)孩子進(jìn)行自左至右的排序；2024/10/1612ABEFCDGHI(4)ABCDEFGHI(3)③對(duì)每個(gè)結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系；④以根結(jié)點(diǎn)為軸心，將整個(gè)樹順時(shí)針轉(zhuǎn)45度。2024/10/1613

（2）

森林轉(zhuǎn)換為二叉樹ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：·將各棵樹分別轉(zhuǎn)成二叉樹；·把每棵數(shù)的根結(jié)點(diǎn)用線連起來(lái)；·以第一棵數(shù)的根結(jié)點(diǎn)作為二叉樹的根結(jié)點(diǎn)，按順時(shí)針方向旋轉(zhuǎn)。2024/10/16144、二叉樹的遍歷查找某個(gè)結(jié)點(diǎn)，或?qū)Χ鏄渲腥拷Y(jié)點(diǎn)進(jìn)行某種處理，就需要遍歷。（1）遍歷定義及遍歷算法遍歷是指按某條搜索路線尋訪樹中每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。（D:訪問(wèn)根結(jié)點(diǎn)

L:遍歷左子樹

R:遍歷右子樹）2024/10/1615

按先左后右的原則，一般使用三種遍歷形式：先序遍歷、中序遍歷、后序遍歷。先序遍歷(DLR):

訪問(wèn)根結(jié)點(diǎn)，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷(LDR):按中序遍歷左子樹，訪問(wèn)根結(jié)點(diǎn)，按中序遍歷右子樹。后序遍歷(LRD):按后序遍歷左子樹，按后序遍歷右子樹，

訪問(wèn)根結(jié)點(diǎn)。二叉樹為空時(shí)，執(zhí)行空操作，即空二叉樹已遍歷完。2024/10/1616

（2）遍歷算法先序遍歷：DLR中序遍歷：LDR后序遍歷：LRDADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過(guò)程ABDCBDACDBCA2024/10/1617voidPreOderTraverse(BiTreeT){if(T!=NULL){printf(T->data);PreOrderTraverse(T->lchild);PreOrderTraverser(T->rchild);}}//先序遍歷主程序Pre(T)返回返回返回返回ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);pre(TR);pre(TR);2024/10/1618voidInOderTraverse(BiTreeT){if(T!=NULL){InOrderTraverse(T->lchild);printf(T->data);InOrderTraverser(T->rchild);

}}//中序遍歷voidPostOderTraverse(BiTreeT){if(T!=NULL){PostOrderTraverse(T->lchild);PostOrderTraverser(T->rchild);}printf(T->data);}//后序遍歷2024/10/16192.5.3哈夫曼樹及其應(yīng)用

1、哈夫曼樹（最優(yōu)樹）帶權(quán)路徑長(zhǎng)度最短的樹，在信息檢索中很有用。路徑長(zhǎng)度：從一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)之間的分支數(shù)目稱為這對(duì)結(jié)點(diǎn)間的路徑長(zhǎng)度。樹的路徑長(zhǎng)度：從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。用PL表示。2024/10/1620PL=0+1+1+2+2+2+2+3=13PL=0+1+1+2+2+2+3+3=142024/10/1621結(jié)點(diǎn)帶權(quán)的路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長(zhǎng)度為樹中葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度之和。記作：其中：Wk為樹中每個(gè)葉子結(jié)點(diǎn)的權(quán)；

Lk為每個(gè)葉子結(jié)點(diǎn)到根的路徑長(zhǎng)度2024/10/1622abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=467abcd524WPL=7*1+5*2+2*3+4*3=35

2024/10/1623①葉子上的權(quán)值均相同時(shí)，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹不一定是最優(yōu)二叉樹。

②最優(yōu)二叉樹中，權(quán)越大的葉子離根越近。

③最優(yōu)二叉樹的形態(tài)不唯一，WPL最小2024/10/1624

加權(quán)后路徑長(zhǎng)度最小的不是完全二叉樹，而是權(quán)最大的葉子離根最近的二叉樹。在哈夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根最近。adcebWPL最小的二叉樹就稱作最優(yōu)二叉樹或哈夫曼樹。哈夫曼樹2024/10/1625哈夫曼樹的構(gòu)造過(guò)程(1)由給定的n個(gè)權(quán)值{w0,w1,w2,…,wn-1}，構(gòu)造具有n棵擴(kuò)充二叉樹的集合F={T0,T1,T2,…,Tn-1}，其中每一棵二叉樹Ti只有一個(gè)帶有權(quán)值wi的根結(jié)點(diǎn)，其左、右子樹均為空。(2)重復(fù)以下步驟,直到F中僅剩下一棵樹為止：

①在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹,做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二