數(shù)據(jù)結(jié)構(gòu)-樹與二叉樹

2.5樹與二叉樹

什么是樹7

*非線性數(shù)據(jù)結(jié)構(gòu)

*元素結(jié)點(diǎn)之間存在分支和層次關(guān)系。（一對(duì)多）

*應(yīng)用：家譜

社會(huì)組織機(jī)構(gòu)

書的章節(jié)劃分

操作系統(tǒng)中的多級(jí)目錄結(jié)構(gòu)

高級(jí)語言中源程序的語法結(jié)構(gòu)等。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹.

25,/樹的罡義及其點(diǎn)卷

1.樹的定義（遞歸定義:

樹是由n（n三0）個(gè)結(jié)點(diǎn)組成的有限集合T：

*有且僅有一個(gè)結(jié)點(diǎn)稱為根結(jié)點(diǎn)（root）

*其余結(jié)點(diǎn)分為m（ni三0）個(gè)各互不相交的有限集合

「、T2....Tm,其中每一個(gè)集合本身又是

一棵樹，稱為根結(jié)點(diǎn)root的子樹。

早n=0時(shí)，為空樹。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

1）結(jié)點(diǎn)：表示樹中的元素。

2）度：結(jié)點(diǎn)擁有的子樹數(shù)。如A的度為3,B

的度為2。樹的度=樹中最大的結(jié)點(diǎn)度數(shù)。

3）葉子（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)。

4）孩子：結(jié)點(diǎn)的子樹的根（后繼結(jié)點(diǎn)）。每個(gè)結(jié)點(diǎn)

均是其前驅(qū)結(jié)點(diǎn)的孩子。

5）雙親：一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹.

25,/樹的定義及其花五

6）子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)。

7）祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。

8）兄弟：同一雙親的孩子。

9）結(jié)點(diǎn)的層次：根為第一層，根的直接后繼結(jié)點(diǎn)為

第二層，以此類推。

10）深度：樹中結(jié)點(diǎn)的最大層次數(shù)。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

11）森林：是m（m三0）棵互不相交的樹的集合

12）有序樹：樹中結(jié)點(diǎn)在同層中按從左到右有序排

歹U、不能互換的稱為有序樹；反之稱為無序樹。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

25,/樹的罡義及其商儲(chǔ)修構(gòu)

例：用有序樹表示算術(shù)表達(dá)式

(A+B)X5/(2X(C-D))

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

1）異構(gòu)型一根據(jù)結(jié)點(diǎn)的度數(shù)設(shè)置相應(yīng)的指針域。

特點(diǎn)：節(jié)省空間、運(yùn)算不便。

2）同構(gòu)型一每個(gè)結(jié)點(diǎn)的指針域個(gè)數(shù)均為樹的度數(shù)。

特點(diǎn)：運(yùn)算方便、浪費(fèi)空間。

例（空鏈域問題）：一棵具有n個(gè)結(jié)點(diǎn)的k叉樹，采用同構(gòu)

型存儲(chǔ)結(jié)構(gòu)，問有多少個(gè)空鏈域？

解：總鏈域二nk；非空鏈域二nT；

1.二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)

第二叉樹是n（n三0）個(gè)結(jié)點(diǎn)的有限集合，它或?yàn)榭諛洌╪=0）,

或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不

相交的二叉樹構(gòu)成。（遞歸定義。）即：度〈二2的有序樹

*特點(diǎn)：每個(gè)結(jié)點(diǎn)至多有2個(gè)孩子，結(jié)點(diǎn)度數(shù)最大為2；

結(jié)點(diǎn)子樹有左右之分。

*存儲(chǔ)結(jié)構(gòu)：采用二叉鏈表存儲(chǔ)。

結(jié)點(diǎn)結(jié)構(gòu):LchildRchild

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.5.2二玉樹及其喉質(zhì)

1.二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)

*二叉樹的五種形態(tài)

思考：二叉樹與二叉有序樹的區(qū)別?

2?5樹與二

2.5.2二玉樹及其喉質(zhì)

2.二叉樹的基本性質(zhì)

*二叉樹的第i層上至多有2z(iNl)個(gè)結(jié)點(diǎn)

可用歸納法證明。

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

由性質(zhì)1求和即可證明。

*在任意二叉樹中，若有n0個(gè)葉子結(jié)點(diǎn)，弱個(gè)度為2

的結(jié)點(diǎn),則必有:n0=n2+lo

證明：設(shè)nl為度為1的結(jié)點(diǎn)，則結(jié)點(diǎn)總數(shù)為

n=n0+nl+n2；又分支總數(shù)為：b=nl+2n2；

而n=b+1；所以nO=n2+l。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

樹。結(jié)點(diǎn)編號(hào)是自上至下、自左至右。

特點(diǎn)：每一層上的結(jié)點(diǎn)都達(dá)到了最大值，即不存在度為1的

結(jié)點(diǎn)，葉子結(jié)點(diǎn)均在最底一層

錄完全二叉樹：一棵有n個(gè)結(jié)點(diǎn)的二叉樹，按與滿二

叉樹相同的編號(hào)方式對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，若樹中n個(gè)結(jié)

點(diǎn)和滿二叉樹1?n編號(hào)完全一致。

性質(zhì)：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為：Log2n+1

這個(gè)樹就不是完全二叉樹。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

弟平衡二叉樹：又稱AVL樹，（Adelson-VerskiiandLandis,

阿德爾遜-弗斯基-蘭迪斯樹），它或者是一棵空樹，或者

是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡

二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過1。

平衡因子=（結(jié)點(diǎn)的）左子樹深度一右子樹深度）

平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是-1、0、1。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

(1)將一般樹轉(zhuǎn)換為二叉樹

①在兄弟結(jié)點(diǎn)之間加一連線；

②對(duì)每個(gè)結(jié)點(diǎn)，除了與它的第一個(gè)孩子保

持聯(lián)系外，去除與其它孩子的聯(lián)系；

③以樹根為軸心，將整棵樹順時(shí)針旋

轉(zhuǎn)45。o

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?5樹與二叉樹

2.5.2二玉樹及其喉質(zhì)

（2）將森林轉(zhuǎn)換為二叉樹

-把森林中第二棵樹的根結(jié)點(diǎn)看成是第一棵

樹轉(zhuǎn)化成的二叉樹的左孩子的兄弟

2.5樹與二叉樹

2.5.2二玉樹及其喉質(zhì)

（3）將二叉樹轉(zhuǎn)換為一般樹或森林

規(guī)則：1）若二叉樹為空，則森林亦為空。

2）若二叉樹非空，則森林中第一棵樹的根為二

叉樹的根，其子樹森林是由二叉樹的左子樹轉(zhuǎn)換而成

的森林；森林中除第一棵樹之外的其余樹組成的森林

是由二叉樹的右子樹轉(zhuǎn)換而成。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.5.2二玉樹及其喉質(zhì)

（3）將二叉樹轉(zhuǎn)換為一般樹或森林

?

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?5樹與二叉樹

2.5.2二玉樹及其喉質(zhì)

（3）將二叉樹轉(zhuǎn)換為一般樹或森林

只有左子樹的二叉樹對(duì)應(yīng)于一

棵一般樹，反之一棵一般樹對(duì)

應(yīng)的二叉樹只有左子樹。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.5.2二玉樹及其喉質(zhì)

5.二叉樹的存儲(chǔ)結(jié)構(gòu)

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

-用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、

自左至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素。

123456

完全二叉樹其順序存儲(chǔ)

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.5.2二玉樹及其喉質(zhì)

5.二叉樹的存儲(chǔ)結(jié)構(gòu)

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

例:

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.5.2二玉樹及其喉質(zhì)

5.二叉樹的存儲(chǔ)結(jié)構(gòu)

(1)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2?5樹與二叉樹

2.5.3二叉樹的遍歷

—遍歷是指循某條搜索路線依次訪問某數(shù)據(jù)構(gòu)中的

全部結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)只被訪問一次。

1.遍歷二叉樹的定義

*依次遍歷根結(jié)點(diǎn)（D）、左子樹（L）、右子樹（R）

三部分。

*按先左后右，有以下3種形式：

DLR：先序遍歷（前序遍歷）

LDR：中序遍歷

LRD：后序遍歷

、說明：其中的序是針對(duì)根結(jié)點(diǎn)來說的。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.5.3二叉樹的遍歷

L遍歷二叉樹的定義

(1)先序遍歷：根-＞左-＞右

＞二叉樹為空，則空操作；

＞訪問根結(jié)點(diǎn)；*遍歷算法

＞先序遍歷左子樹;

PreOrder(t)

＞先序遍歷右子樹。

if(t!=nil){

訪問根結(jié)點(diǎn)；

PreOrder(IchiId(t));

PreOrder(rchiId(t));

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.5.3二叉樹的遍歷

L遍歷二叉樹的定義

(2)中序遍歷：左-＞根-＞右

＞二叉樹為空，則空操作；

＞中序遍歷左子樹;品遍歷算法

＞訪問根結(jié)點(diǎn)；InOrder(t)

＞中序遍歷右子樹。if(t!=nil){

InOrder(IchiId(t));

訪問根結(jié)點(diǎn)；

InOrder(rchiId(t));

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.5.3二叉樹的遍歷

1.遍歷二叉樹的定義

(3)后序遍歷：左-＞右-〉根

＞二叉樹為空，則空操作；自

一占一-*遍歷算法

＞后序遍歷左子樹；

:＞后序遍歷右子樹；PostOrder(t)

＞訪問根結(jié)點(diǎn)。if(t!二nil){

PostOrder(IchiId(t));

PostOrder(rchild(t));

訪問根結(jié)點(diǎn);

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?5樹與二叉樹

2.5.3二叉樹的遍歷

1111

先序：ABABABCDABDCEFG

中序：BAABACBDDBAECFG

后序：BABACDBADBEGFCA

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.5.3二叉樹的遍歷

2?5樹與二叉樹

2.5.3二叉樹的遍歷

例：已知中序序列為：DCBGEAHFIJK,

后序序列為：DCEGBFHKJIA,

求此二叉樹及先序序列。

則后序序列為：ABCDGEIHFJK

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?5樹與二叉樹

2.5.3二叉樹的遍歷

2.遍歷的應(yīng)用

求二叉樹中的葉子數(shù)：

CountLeaf(t,count)

{

if(t!=nil){

if(Ichild(t)==nil&&rchild(t)!=nil)

count++;

CountLeaf(Ichild(t));

CountLeaf(rchild(t));

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二3

2.54二叉樹的應(yīng)用

1.二叉排序樹

(1)定義：二叉排序樹是一棵二叉樹，滿足

下列條件：

*空樹；

*左子樹上的結(jié)點(diǎn)值〈根結(jié)點(diǎn)的值；

*右子樹上的結(jié)點(diǎn)值＞二根結(jié)點(diǎn)的值；

*左、右子樹也是二叉排序樹。

在二叉排序樹中，若按中序遍歷就可以得到由小

到大的有序序列。上圖中序遍歷得到：

{2,3,4,8,9,9,10,13,15,18,21}

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.54二叉樹的應(yīng)用

1.二叉排序樹

（2）二叉排序樹的插入（生成）

*在給定的二叉排序樹中插入值為b的結(jié)點(diǎn)

若樹為空，則作為根結(jié)點(diǎn)；

[若樹不空，則將b與根結(jié)點(diǎn)值r作比較：

b<r,插入左子樹；

b>=r,插入右子樹；

（注：新插入的結(jié)點(diǎn)一定是新添的葉子結(jié)點(diǎn)）

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.54二叉樹的應(yīng)用

1.二叉排序樹

InsertBet(t,b)

*插入算法:

if(t==nil){

GETNODE(t)；

data(t)<-b;

lchild(t)<-nil;

rchild(t)<-nil;

)

elseif(b<data(t))

InsertBet(Ichild(t),b);

elseInsertBet(rchild(t),b);

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.54二叉樹的應(yīng)用

*二叉排序樹是一種動(dòng)態(tài)表結(jié)構(gòu)，即二叉排序樹的生成

過程是不斷地向二叉排序樹中插入新的結(jié)點(diǎn)。

2.5樹與二叉樹

254二叉樹的應(yīng)用

1.二叉排序樹

(3)二叉排序樹的刪除：刪除結(jié)點(diǎn)P,使刪除后的二

叉樹仍是二叉排序樹：DeiNode(t,p,f)

2.5樹與二叉樹

2.54二叉樹的應(yīng)用

刪除算法：DelNode(*t,*p,*f)

fag=O;

if(p->IchiId二二NULL)f=p->rchild;

elseif(p->rchild-NULL)f=p->lchild;

else{

q=p;s=p->lchild;

while(s->rchild!=NULL){q=s;s=s-

>rchild;}

if(q二二p)q->lchild=s->lchild;

elseq->rchild=s->lchild;

p->data=s->data;free(s);fag=l;

if(fag==O){if(f==NULL)t=s;

elseif(f->lchild==p)f->lchild=s;

elsef->rchild=s;

free(p);

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.54二叉的的應(yīng)用

1.二叉排序樹

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.54二叉樹的應(yīng)用

1.二叉排序樹

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?5樹與二叉樹

2.54二叉的的應(yīng)用

2.哈夫曼樹

——又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。

(1)基本術(shù)語

*路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間

的分支構(gòu)成兩個(gè)結(jié)點(diǎn)之間的路徑。

*路徑長度：路徑上的分支數(shù)目。

*樹的路徑長度：從樹根到每一結(jié)點(diǎn)的路徑長

、度之和(PL)o

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.54二叉的的應(yīng)用

PL=0+1X2+2X2+3=9PL=0+1+2X2+3+4=12

n

推論：對(duì)n個(gè)結(jié)點(diǎn)的二叉樹，滿足：PL>sL^g2d

1=1

最小路徑長度PL=z[log2d的樹稱為完全二叉樹

Z=1

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.54二叉樹的應(yīng)用

*結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)到樹根之間的

路徑長度與該結(jié)點(diǎn)上權(quán)值的乘積。

*樹的帶權(quán)路徑長度：樹中葉子結(jié)點(diǎn)的帶權(quán)路

徑長度之和。

wk葉子結(jié)點(diǎn)的權(quán)值,

lk--葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.54二叉樹的應(yīng)用

例:

(a)WPL=7*2+5*2+2*2+4*2=36

(b)WPL=7*3+5*3+2*1+4*2=46

(c)WPL=7*1+5*2+2*3+4*3=35（哈夫曼樹）

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?5樹與二叉樹

2.54二叉樹的應(yīng)用

*哈夫曼樹：WPL最小的二叉樹稱最優(yōu)二叉樹或哈

夫曼（huffman）樹。

注意：

＞加權(quán)路徑最小的二叉樹并非完全二叉樹。

＞哈夫曼樹中沒有度為1的結(jié)點(diǎn)，因此一棵有n

個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2nT個(gè)結(jié)點(diǎn)。

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

①由給定的n個(gè)權(quán)值｛w],w2,wn)構(gòu)成n棵二叉樹的

集合F二｛「,T2,Tn),每棵樹只有一個(gè)權(quán)值為明的根

結(jié)點(diǎn)；

②在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹

構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)

值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和；

③將新二叉樹加入F中，并去除原兩棵樹；

④重復(fù)②、③，直到F中只含一棵樹，即huffman樹

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

2.54二叉樹的應(yīng)用

*算法實(shí)現(xiàn)

結(jié)點(diǎn)采用數(shù)組型鏈表結(jié)構(gòu)，

每個(gè)結(jié)點(diǎn)由4個(gè)數(shù)據(jù)域組成:

data：存放結(jié)點(diǎn)權(quán)指

Ichild：左指針

rchild：右指針

prnt：雙親指針

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2.5樹與二叉樹

254二叉樹的應(yīng)用

HuffmanTree(n,Ichild,rchild,data,prnt,w)

{

for(i=0;i<n;i++){

data[i]<-w[i];

lchild[i]<-0;rchild[i]<-0;

}

for(i=0;i<2*n-l;i++)prnt[i]<-0;〃初始化

for(k=n;k<2*n-l;k++){

Select(k,&i,&j);〃查找最小的i,j(雙親為0)

data[k]<-data[i]+data[j];

Ichild[k]<-i;rchild[k]<-j;

prnt[i]<-k;prnt[j]<-k;

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

第一類第二類

WPL=2/20+2X3/20+(4/20+11/20)X3WPL=11/20+2X4/20+(2/20+3/20)X3

=53/20=34/20

最佳判定算法。

例：一批數(shù)據(jù)結(jié)構(gòu)，a〈=20為第一類，概率為2/20;

20<a〈=50為第二類，概率為3/20;

50<a<=100為第三類，概率為4/20;

其余為第四類，概率為11/20;

2.5樹與二叉樹

2.54二叉樹的應(yīng)用

*哈夫曼編碼（可用于信息的二進(jìn)制編碼）

1）不等長即時(shí)可譯碼（前綴碼）

ABCD電文“ABACCDA”碼長

0001101114bit（自然碼）

0001019bit（非即時(shí)可譯）

0100100010000121bit（即時(shí)可譯）

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

2?5樹與二叉樹

2.54二叉樹的應(yīng)用

2）不等長最佳即時(shí)可譯碼（平均碼長最短）

—給出現(xiàn)概率（頻率）最高的信源符號(hào)賦予最短

的碼字，給出現(xiàn)頻率低的符號(hào)賦予長碼，使平均碼長最

短。

Huffman編碼為一種不等長最佳即時(shí)可譯碼，可

通過構(gòu)造huffman樹（譯碼樹）設(shè)計(jì)碼字。

n

L=WPL=Z墳/L--總碼長，為huffman

、』樹的帶權(quán)路徑長度

第二章常用數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算

例：某一通信系統(tǒng)，信源與其出現(xiàn)碼元的概率如下：

CiABCDEF

匕0.10.40.30.10.060.04

求：1）huffman編碼，2）畫出huffman碼樹，

3）求平均碼長，3）求最大壓縮比

解：1）

編碼信源出現(xiàn)

符號(hào)概率

1