數據結構(C／C++描述)第6章 樹與二叉樹

第6章樹和二叉樹6.1樹的定義及其存儲結構6.2

二叉樹6.3

遍歷二叉樹和線索化二叉樹6.4

樹、森林和二叉樹的關系6.5哈夫曼樹及其應用

6.1樹的定義及其存儲結構數據對象D：D是具有相同特性的數據元素的集合。若D為空集，則稱為空樹；否則:(1)在D中存在唯一的稱為根的數據元素root；(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數據關系R：6.1.1樹的定義及基本術語ABCDEFGHIJMKLA()T1T3T2樹根例如:B(E,F(K,L)),

C(G),

D(H,I,J(M))(１)有確定的根；(２)樹根和子樹根之間為有向關系。有向樹：有序樹：子樹之間存在確定的次序關系。無序樹：子樹之間不存在確定的次序關系。基本術語結點:結點的度:樹的度:葉子結點:分支結點:數據元素+若干指向子樹的分支分支的個數樹中所有結點的度的最大值度為零的結點度大于零的結點DHIJM(從根到結點的)路徑：孩子結點、雙親結點、兄弟結點、堂兄弟祖先結點、子孫結點結點的層次:樹的深度：

由從根到該結點所經分支和結點構成ABCDEFGHIJMKL假設根結點的層次為1,第l層的結點的子樹根結點的層次為l+1樹中葉子結點所在的最大層次任何一棵非空樹是一個二元組Tree=（root，F(xiàn)）其中：root被稱為根結點，F(xiàn)被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBEFKLCGDHIJMF對比樹型結構和線性結構的結構特點~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結構樹型結構第一個數據元素(無前驅)

根結點(無前驅)最后一個數據元素(無后繼)多個葉子結點(無后繼)其它數據元素(一個前驅、一個后繼)其它數據元素(一個前驅、多個后繼)6.1.2樹的存儲結構一、雙親數組表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFGr=0n=70

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、雙親表示法:

typedefstructPTNode

{TElemTypedata;

int

parent;//雙親位置域}PTNode;

dataparent#defineMaxTreeSize100結點結構:C語言的類型描述:typedefstruct{

PTNode

nodes[MaxTreeSize];

int

r,n;//根結點的位置和結點個數

}

PTree;樹結構:r=0n=7dataparentfirstchildABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4645123二、孩子鏈表表示法:-1000224typedefstructCTNode

{

int

child;//數組下標

structCTNode

*nextchild;}*ChildPtr;孩子結點結構:

childnextchildC語言的類型描述:

typedefstruct{TElemTypedata;//結點的值ChildPtrfirstchild;//孩子鏈的頭指針

}

CTBox;雙親結點結構

datafirstchildtypedefstruct{

CTBox

nodes[MaxTreeSize];//雙親結點結構數組

int

n,r;

//結點數和根結點的位置}

CTree;樹結構:ABCDEFGrootABCEDFGABCEDFG

三、樹的二叉鏈表(孩子-兄弟）存儲表示法root森林的二叉鏈表表示typedefstruct

CSNode{

TElemType

data;

struct

CSNode

*firstchild,*nextsibling;}

CSNode,*CSTree;C語言的類型描述:結點結構:

firstchilddata

nextsibling6.2

二叉樹6.2.1

二叉樹的定義

二叉樹或為空樹；或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結點左子樹右子樹EF二叉樹的5種基本形態(tài)：N空樹只含根結點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹6.2.2

二叉樹的性質

性質1：

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

個結點。(i≥1)用歸納法證明：

歸納基：

歸納假設：

歸納證明：i=1

層時，只有一個根結點，

2i-1

=20

=1；假設對所有的j，1≤j

i，命題成立;二叉樹上每個結點至多有兩棵子樹，則第i層的結點數=2i-2

2=2i-1

。性質2：

深度為k的二叉樹上至多含2k-1

個結點（k≥1）證明：基于上一條性質，深度為k的二叉樹上的結點數至多為

20+21+

+2k-1=2k-1

性質3：

對任何一棵二叉樹，若它含有n0個葉子結點、n2

個度為

2的結點，則必存在關系式：n0=n2+1證明：設二叉樹上結點總數n=n0+n1+n2又二叉樹上分支總數b=n1

+2n2而b=n-1=n0+n1+n2-1由此，n0=n2

+1兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。123456789101112131415abcdefghij完全二叉樹：如果一顆二叉樹只有最下一層結點數可能未達到最大，并且最下層結點都集中在該層的最左端，則稱為完全二叉樹；

A

E

D

C

B

G

A

E

D

C

B(a)(c)(b)、(b)完全二叉樹(c)不是完全二叉樹

A

G

F

E

D

C

B

性質4：

具有n個結點的完全二叉樹的深度為log2n+1證明：設完全二叉樹的深度為k則根據第二條性質得2k-1≤n<

2k即k-1

≤log2

n<k

因為k只能是整數，因此，k=log2n

+1性質5：若對含n個結點的完全二叉樹從上到下且從左至右進行1至n的編號，則對完全二叉樹中任意一個編號為

i

的結點：

(1)若i=1，則該結點是二叉樹的根，無雙親,否則，編號為i/2的結點為其雙親結點;

(2)若2i>n，則該結點i無左孩子，

否則，編號為2i的結點為其左孩子結點；

(3)若2i+1>n，則該結點i無右孩子結點，

否則，編號為2i+1

的結點為其右孩子結點。6.2.3二叉樹的存儲結構二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示#define

MaxTreeSize100

//二叉樹的最大結點數typedefTElemTypeSqBiTree[MaxTreeSize

+1];

//0號單元存儲根結點SqBiTreebt;一、二叉樹的順序存儲表示順序存儲結構:按二叉樹的結點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問：順序存儲后能否復原成唯一對應的二叉樹形狀？答：若是完全/滿二叉樹則可以做到唯一復原。而且有規(guī)律：下標值為i的雙親，其左孩子的下標值必為2i，其右孩子的下標值必為2i＋1（即性質5）例如，對應[2]的兩個孩子必為[4]和[5],即B的左孩子必是D,右孩子必為E。T[0]一般不用討論：不是完全二叉樹怎么辦？答：一律轉為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結點”，其內容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點：①浪費空間；②插入、刪除不便

例如:

ABDCEF

1234567891011121314ABCDEF2511437相應完全二叉樹

n=15二、二叉樹的鏈式存儲表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表ADEBCFrootlchilddatarchild結點結構:1.二叉鏈表typedefstruct

BiTNode

{

//結點結構TElemTypedata;

structBiTNode*lchild,*rchild;

//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結點結構:C語言的類型描述如下:rootADEBCF2．三叉鏈表parent

lchilddatarchild結點結構:

typedefstruct

TriTNode//結點結構

{TElemTypedata;

struct

TriTNode

*lchild,*rchild;

//左右孩子指針

structTriTNode

*parent;//雙親指針

}

TriTNode,*TriTree;parentlchilddatarchild結點結構:C語言的類型描述如下:6.3遍歷二叉樹和線索化二叉樹一、遍歷的概念二、先左后右的遍歷算法三、算法的遞歸描述四、中序遍歷算法的非遞歸描述五、遍歷算法的應用舉例6.3.1二叉樹的遍歷

順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次。一、遍歷的概念“訪問”的含義可以很廣，如：輸出結點的信息等。

“遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結構，

每個結點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑進行遍歷的問題。對“二叉樹”而言，可以有三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。遍歷二叉樹（TraversingBinaryTree）遍歷定義——指按某條搜索路線遍訪每個結點且不重復（又稱周游）。遍歷用途——它是樹結構插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎和核心。

遍歷方法——牢記一種約定，對每個結點的查看都是“先左后右”。二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法根左子樹右子樹根根根根根

若二叉樹為空樹，則空操作；否則，（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法（DLR）

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。中（根）序遍歷算法（LDR）

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。后（根）序遍歷算法（LRD）ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A三、算法的遞歸描述void

PreOrderTraverse(BiTreeT){//

先序遍歷二叉樹

if(T){

VisitElement(T->data);//訪問結點

PreOrderTraverse

(T->lchild);//遍歷左子樹

PreOrderTraverse

(T->rchild);//遍歷右子樹

}}void

InOrderTraverse(BiTreeT){//

中序遍歷二叉樹

if(T){

①InOrderTraverse(T->lchild);//遍歷左子樹

②VisitElement

(T->data);//訪問結點

③InOrderTraverse

(T->rchild);//遍歷右子樹

}}void

PostOrderTraverse

(BiTreeT){//

后序遍歷二叉樹

if(T){

①PostOrderTraverse(T->lchild);//遍歷左子樹

②PostOrderTraverse(T->rchild);//遍歷右子樹

③VisitElement(T->data);//訪問根結點

}}對遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將visit語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結點的時機不同。從虛線的出發(fā)點到終點的路徑上，每個結點經過3次。AFEDCBG第1次經過時訪問＝先序遍歷第2次經過時訪問＝中序遍歷第3次經過時訪問＝后序遍歷2.二叉樹遍歷的時間效率和空間效率時間效率:O(n)

//每個結點只訪問一次空間效率:O(n)

//棧占用的最大輔助空間（精確值：樹深為k的遞歸遍歷需要k+1個輔助單元?。Ρ闅v的分析：從虛線的出發(fā)點到終點的路徑上，每個結點經過3次。AFEDCBG第1次經過時訪問＝先序遍歷第2次經過時訪問＝中序遍歷第3次經過時訪問＝后序遍歷中序序列：DBFEGACint

InOrderTraverse(BiTreeT){BiTNode*p;InitStack(S);p=T;

while(p||!StackEmpty(S)){if

(p) {

Push(S,p);p=p->lchild;} //根結點進棧，遍歷左子樹else

{Pop(S,p);//根結點退棧，訪問根結點，遍歷右子樹VisitElement(p->data);p=p->rchild;}//else}//whilereturn

OK;}

//InOrderTraverse四、中序遍歷算法的非遞歸描述五、遍歷算法的應用舉例1、統(tǒng)計二叉樹中葉子結點的個數2、建立二叉樹的存儲結構1、統(tǒng)計二叉樹中葉子結點的個數算法基本思想:

先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結點，并計數。由此，需在遍歷算法中增添一個“計數”的參數，并將算法中“訪問結點”

的操作改為:若是葉子，則計數器增1。voidCountLeaf(BiTreeT,int&count){//先序遍歷二叉樹，計算葉子結點個數if(T){if((!T->lchild)&&(!T->rchild))

count++;//對葉子結點計數

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf2、建立二叉樹的存儲結構不同的定義方法相應有不同的存儲結構的建立算法

以字符串的形式“根左子樹

右子樹”定義一棵二叉樹例如:以空白字符“”表示ABCDAB

C

D

空樹只含一個根結點的二叉樹A以字符串“A”表示以下列字符串表示intCreateBiTree(BiTree&T)

{//按先序序列構造二叉鏈表表示的二叉樹Tscanf(&ch);if(ch=='')T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根結點

CreateBiTree(T->lchild);//構造左子樹

CreateBiTree(T->rchild);//構造右子樹}

returnOK;//遞歸出口}//CreateBiTreeAB

C

D

ABCD上頁算法執(zhí)行過程舉例如下:ATBCD^^^^^①scanf(&ch);②if(ch=='')T=NULL;

else

{③

if(!(T=newBiTNode))

exit(OVERFLOW);④

T->data=ch;⑤

CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnok//遞歸出口

僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹

如果同時已知二叉樹的中序序列“cbdaegf”,則會如何？

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.3.2

線索化二叉樹一、何謂線索二叉樹？遍歷二叉樹的結果是，求得結點的一個線性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA

指向該線性序列中的“前驅”和“后繼”的指針，稱作“線索”與其相對應的二叉樹，稱作“線索二叉樹”包含“線索”的存儲結構，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^對線索鏈表中結點的約定：

在二叉鏈表的結點中增加兩個標志域，并作如下規(guī)定：若該結點的左子樹不空，則Lchild域的指針指向其左子樹，且左標志域的值為“指針Link=0”；否則Lchild域的指針指向其“前驅”，且左標志的值為“線索Thread=1”。若該結點的右子樹不空，則rchild域的指針指向其右子樹，且右標志域的值為“指針Link=0”；否則，rchild域的指針指向其“后繼”，且右標志的值為“線索Thread=1”。

如此定義的二叉樹的存儲結構稱作“線索鏈表”typedefstruct

BiThrNode{

TElemTypedata;

struct

BiThrNode

*lchild,*rchild;

//左右指針

PointerThr

LTag,RTag;

//左右標志}

BiThrNode,*BiThrTree;線索鏈表的類型描述：

typedef

enum

{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索規(guī)定：1）若結點有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(即線索)；2）若結點有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。為了避免混淆，增加兩個標志域，如下圖所示：lchildLTagdataRTagrchild約定:當Tag域為0時,表示正常情況;當Tag域為1時,表示線索情況.有關線索二叉樹的幾個術語：

線索鏈表：

用前頁結點結構所構成的二叉鏈表

線索：指向結點前驅和后繼的指針

線索二叉樹：加上線索的二叉樹（圖形式樣）

線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程注：在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，當標志為0時，則需要通過一定運算才能找到它的后繼。ABCGEIDHFroot懸空？懸空？解：該二叉樹中序遍歷結果為:

H,D,I,B,E,A,F,C,G所以添加線索應當按如下路徑進行：例2：畫出以下二叉樹對應的中序線索二叉樹。為避免懸空態(tài)，應增設一個頭結點對應的中序線索二叉樹存儲結構如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結果為:H,D,I,B,E,A,F,C,G0--root0二、線索鏈表的遍歷算法由于在線索鏈表中添加了遍歷中得到的“前驅”和“后繼”的信息，從而簡化了遍歷的算法。對中序線索化鏈表的遍歷算法

※中序遍歷的第一個結點？

※在中序線索化鏈表中結點的后繼？

左子樹上處于“最左下”（沒有左子樹）的結點若無右子樹，則為后繼線索所指結點否則為對其右子樹進行中序遍歷時訪問的第一個結點void

InOrderTraverse_Thr(BiThrTreeT){//線索二叉樹的中序遍歷算法p=T->lchild;//p指向根結點

while(p!=T)

{

//空樹或遍歷結束時，p==Twhile(p->LTag==Link)p=p->lchild;//查找第一個結點－最左下

if(!visit(p->data))returnERROR;//若起點值為空則出錯告警while(p->RTag==Thread&&p->rchild!=T)

{//若有后繼標志，則直接提取p->rchild中線索并訪問p=p->rchild;Visit(p->data);//訪問后繼結點

}p=p->rchild;//當前結點右域不空或已經找好了后繼，則一律//從結點的右子樹開始重復{}的全部過程。

}}在中序遍歷過程中修改結點的左、右指針域，以保存當前訪問結點的“前驅”和“后繼”信息。遍歷過程中，附設指針pre,并始終保持指針pre指向當前訪問的、指針p所指結點的前驅。三、如何建立線索鏈表？對應的中序線索二叉樹存儲結構如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結果為:H,D,I,B,E,A,F,C,G0--root0void

InThreading(BiThrTreep)

{

if(p){//對以p為根的非空二叉樹進行線索化

InThreading(p->lchild);

//左子樹線索化

if(!p->lchild)//建前驅線索{p->LTag=1;p->lchild=pre;}

if(!pre->rchild)//建后繼線索{pre->RTag=1;pre->rchild=p;}

pre=p;//保持pre指向p的前驅

InThreading(p->rchild);

//右子樹線索化

}//if}//InThreadingStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//構建中序線索鏈表if(!(Thrt=newBiThrNode))exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加頭結點returnOK;}//InOrderThreading……if(!T)

Thrt->lchild=Thrt;//若二叉樹空，左指針回指else{Thrt->lchild=T;

pre=Thrt;//設置前趨指針初值

InThreading(T);//調用算法6.7

pre->rchild=Thrt;

//處理最后一個結點

pre->RTag=Thread;Thrt->rchild=pre;

}

6.4樹、森林和二叉樹的關系6.4.1樹、森林和二叉樹的轉換設森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉樹

B=(LBT,Node(root),RBT);由森林轉換成二叉樹的轉換規(guī)則為:若F=Φ，則B=Φ;由ROOT(T1)對應得到Node(root);否則，由(t11,t12,…,t1m)對應得到LBT;由(T2,T3,…,Tn)對應得到RBT。T1T11,T12,…,T1mT2,…,TnLBTRBTroot轉換步驟：step1:將樹中同一結點的兄弟相連;step2:保留結點的最左孩子連線，刪除其它孩子連線；step3:將同一孩子的連線繞左孩子順時針旋轉45度角。加線抹線旋轉討論1：樹如何轉為二叉樹？方法：加線—抹線—旋轉

abeidfhgc樹轉二叉樹舉例：abeidfhgc兄弟相連長兄為父孩子靠左根結點肯定沒有右孩子！討論2：二叉樹怎樣還原為樹？abeidfhgc要點：把所有右孩子變?yōu)樾值埽∪缓竽鏁r針旋轉45度。

abeidfhgc法1：①各森林先各自轉為二叉樹；②依次連到前一個二叉樹的右子樹上。討論3：森林如何轉為二叉樹？法2：

森林直接變兄弟，再轉為二叉樹即F={T1,T2,…,Tm}B={root,LB,RB}ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林轉二叉樹舉例：（法2）兄弟相連長兄為父孩子靠左頭根為根

A討論4：二叉樹如何還原為森林？要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?/p>

ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B={root,LB,RB}F={T1,T2,…,Tm}

由此，樹和森林的各種操作均可與二叉樹的各種操作相對應。

應當注意的是，和樹對應的二叉樹，其左、右子樹的概念已改變?yōu)椋?/p>

左是孩子，右是兄弟6.4.2樹和森林的遍歷一、樹的遍歷二、森林的遍歷三、樹的遍歷的應用樹的遍歷可有3條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。若樹不空，則自上而下自左至右訪問樹中每個結點。

層次遍歷時頂點的訪問次序：ABCDEFGHIJK

先根遍歷時頂點的訪問次序：ABEF

C

DGHIJK后根遍歷時頂點的訪問次序：EFB

C

IJKHG

DAABCD

EFGHIJK

BCDEFGHIJK1。森林中第一棵樹的根結點；2。森林中第一棵樹的子樹森林；3。森林中其它樹構成的森林?？梢苑纸獬?部分：森林

若森林不空，則訪問森林中第一棵樹的根結點;先序遍歷森林中第一棵樹的子樹森林;先序遍歷森林中（除第一棵樹之外）其余樹構成的森林。先序遍歷:森林的遍歷即：依次從左至右對森林中的每一棵樹進行先根遍歷。

BCDEFGHIJK森林