曾祖父爺爺二爺三爺父親二叔獨生子族譜樹是以分支關系定義的層次結(jié)構(gòu)。第十章樹樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。學習重點:樹的基本概念

二叉樹的基本概念、相關操作樹和森林與二叉樹之間的相互轉(zhuǎn)換二叉樹的應用第十章樹樹的定義和基本術語樹(Tree):是具有層次結(jié)構(gòu)的n(n>0)

個結(jié)點的有限集。ABCDEFGHIJKLM一般樹第十章樹只有根結(jié)點的樹A樹(Tree):是n(n>0)

個結(jié)點的有限集。n＞0

，有且僅有一個稱為根的結(jié)點。n＞1

，除根結(jié)點外，其余結(jié)點可分為m(m＞0)個互不相交的有限子集T1,T2,…Tm

，其中每個子集都稱為根結(jié)點的子樹。A...T1T2Tmn＞1第十章樹和二叉樹基本術語結(jié)點(node)——表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支結(jié)點的度(degree)——結(jié)點擁有的子樹數(shù)葉子(leaf)——度為0的結(jié)點孩子(child)——結(jié)點子樹的根稱為該結(jié)點的孩子雙親(parents)——孩子結(jié)點的上層結(jié)點叫該結(jié)點的~兄弟(sibling)——同一雙親的孩子樹的度——一棵樹中最大的結(jié)點度數(shù)深度(depth)——樹中結(jié)點的最大層次數(shù)第十章樹和二叉樹ABCDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先第十章樹和二叉樹樹的其它表示方法

a.嵌套集合大集合表示樹，小集合表示子樹，相互嵌套。ABDCEFKLGHJIM第六章樹b.

層次表示法類似書的編目ABCDEFGHIJKLM第六章樹二叉樹二叉樹的定義二叉樹是n(n≥0)

個結(jié)點的有限集，它或者是空集，或者是由一個根和稱為左、右子樹的兩個互不相交的二叉樹組成。

二叉樹是一個遞歸定義。樹的子樹次序不作規(guī)定，二叉樹的兩個子樹有左、右之分。樹中結(jié)點的度沒有限制，二叉樹中結(jié)點的度只能取0、1、2。Φ空二叉樹ABCDEF一般二叉樹根左子樹右子樹第十章樹和二叉樹根據(jù)定義，二叉樹通常具有5種基本形態(tài):Φ空二叉樹A僅有根結(jié)點的二叉樹A右子樹為空的二叉樹A左、右子樹均非空的二叉樹A左子樹為空的二叉樹關于樹的基本術語也都適用于二叉樹。二叉樹與樹的區(qū)別樹：1、樹最少有一個根結(jié)點（n>0）

2、樹的度≥

03、樹不要求子樹順序二叉樹：

1、二叉樹可以為空(n≥0)2、二叉樹的度≤2

3、二叉樹是有序樹，有左、右子樹之分。例10-1：試寫出具有3個結(jié)點的所有不同形態(tài)的樹和二叉樹。二叉樹的性質(zhì)性質(zhì)1:

在二叉樹的第i

層上至多有2i-1

個結(jié)點(i≥1)。歸納法證明:(1)i=1，只有一個根結(jié)點，2i-1

=20=

1，正確；(2)假設i-1

成立，即第i-1

層上至多有2i-2個結(jié)點；(3)由于二叉樹的結(jié)點的度至多為2

，故在第i

層上的最大結(jié)點數(shù)為第i-1

層上的最大結(jié)點數(shù)的2

倍，即2×2i-2=2i-1。性質(zhì)2:

深度為k

的二叉樹至多有2k–1

個結(jié)點(k≥1)。∑i=1k(第i層上的最大結(jié)點數(shù))＝∑i=1k2i-1＝2k–1練習:

歸納法證明。引論:

一棵樹有n個結(jié)點，則必有n–1條分支。證明:除根結(jié)點外，其它結(jié)點都有一個分支進入，設B

為分支總數(shù)，故n=B+1

，故B=n-1得證。ABCDEF性質(zhì)3:

對任何一棵二叉樹T

，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2

，則n0=n2+1

。證明:(1)已知，終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，設度為1的結(jié)點數(shù)為n1，由于二叉樹中的所有結(jié)點的度只能為0、1、2，故二叉樹的結(jié)點總數(shù)為n=n0+n1+n2

；(2)除根結(jié)點外，其它結(jié)點都有一個分支進入，設B

為分支總數(shù)，故n=B+1

，由于這些分支均是由度為1或2的結(jié)點引出的，所以有B=n1+2n2

，故n=n1+2n2+1

，由(1)和(2)，可得

n0+n1+n2

=n1+2n2+1

，故有

n0=n2+1。兩種特殊形態(tài)二叉樹:滿二叉樹、完全二叉樹。一棵深度為k

且有2k-1

個結(jié)點的二叉樹稱為滿二叉樹。特點:

1

24

5滿二叉樹3

67(1)每一層的結(jié)點數(shù)都達到最大結(jié)點數(shù)。(2)葉子結(jié)點在最大層。(3)任一結(jié)點，其左、右分支下的子孫的最大層次相等。對滿二叉樹的結(jié)點進行連續(xù)編號，從根結(jié)點起，自上而下，自左至右，1、2、3、……、2k-1

。深度為

k的，有

n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為

k的滿二叉樹中編號從

1至

n的結(jié)點一一對應時，稱為完全二叉樹。

1

24

53

6

1

23

4

5非完全二叉樹

1

24

53完全二叉樹(1)特點:(1)葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)。(2)對任一結(jié)點，若其右分支的子孫的最大層次為l

，則其左分支下的子孫的最大層次必為l

或l+1。完全二叉樹(2)

1

24

53

67滿二叉樹和完全二叉樹的區(qū)別：1、滿二叉樹一定是完全二叉樹，它是完全二叉樹的特例。2、完全二叉樹不一定是滿二叉樹。3、滿二叉樹中n1=0，完全二叉樹中n1=0或1.性質(zhì)4:具有

n個結(jié)點的完全二叉樹的深度為

log2n」+1。

證明:設n結(jié)點完全二叉樹的深度為k，k

層滿二叉樹結(jié)點數(shù)k

層完全二叉樹結(jié)點數(shù)≤k-1

層滿二叉樹結(jié)點數(shù)＜因為，故2k-1-1

＜

n≤

2k-1

有

2k-1

≤n＜

2k又

k-1

≤log2n＜

k因為k是整數(shù)，所以k=log2n」+1。性質(zhì)5:

如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號(從第

1

層到第

log2n」+1

層，每層從左到右)，則對任一結(jié)點

i(1≤i≤n)，有

(1)如果i=1，則結(jié)點i

為根，無父親；如果i＞1，則結(jié)點i

的父結(jié)點parent(i)

是結(jié)點i/2」。//求父親(2)如果2i≤n，則結(jié)點i的左兒子LChild(i)

是結(jié)點2i；否則無左兒子。//求左兒子(3)如果2i+1≤n，則結(jié)點i的右兒子RChild(i)

是結(jié)點2i+1；否則無右兒子。//求右兒子證明(1):

如果(2)、(3)成立，則(1)成立。證明(2)和(3):歸納法若有左兒子，應為2i=2；i=1:根結(jié)點

1

23若有右兒子，應為2i+1=3；設對結(jié)點i成立，即結(jié)點i的左兒子為結(jié)點2i，右兒子為結(jié)點2i+1；求證對結(jié)點i+1

也成立:完全二叉樹中，結(jié)點i和結(jié)點i+1

之間的關系通常有兩種情況，或在同一層上，或分別在相鄰兩層上，且最左和最右。i+1i2i2i+12i+22i+3情況1i+1i2i2i+12i+22i+3……情況2i+1i2i2i+12i+22i+3情況1i+1i2i2i+12i+22i+3……情況2結(jié)點i+1的兒子的序號一定緊挨在結(jié)點i的兒子的序號的后面，根據(jù)歸納假設，結(jié)點i的兒子的序號為2i和2i+1，則結(jié)點i+1的左、右兒子的序號應為2i+2=2(i+1)、2i+3=2(i+1)+1。若2(i+1)+1＞n

則無右兒子，若2(i+1)＞n

則無左兒子。得證。二叉樹的存儲結(jié)構(gòu)(順序、鏈式)1.順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲二叉樹上的結(jié)點元素。#defineMAX_TREE_SIZE100typedef

TElemType

SqBiTree[MAX_TREE_SIZE]

1

24

53完全二叉樹:

編號為i的元素存儲在數(shù)組下標為i-1

的分量中；12345012

34

1

23

4

5一般二叉樹:

對照完全二叉樹，存儲在數(shù)組的相應分量中；在最壞情況下，深度為k

的右單支二叉樹需要2k-1

個存儲空間。

1

23結(jié)論:

順序存儲結(jié)構(gòu)適用于存儲完全二叉樹?？臻g浪費12345000表示不存在此結(jié)點012

345671230000012

34567例10-3一個深度為K且只有K個結(jié)點的二叉樹順序存儲最多需要多少個存儲空間？最少需要多少個？例10-4一個完全二叉樹結(jié)點個數(shù)為1000，則n0、n1、n2和高度h各為多少？2.鏈式存儲結(jié)構(gòu)D＝(root，DL，DR)。鏈表結(jié)點包含3

個域:數(shù)據(jù)域、左指針域、右指針域數(shù)據(jù)域左指針域右指針域datarchildlchilddatalchildrchild由這種結(jié)點結(jié)構(gòu)得到的二叉樹存儲結(jié)構(gòu)稱為二叉鏈表。二叉鏈表存儲表示typedef

struct

BitNode{}BitNode,*BitTree;TElemTypedata；struct

BitNode

*

lchild

，*

rchild

；ABCDEFGH∧∧∧∧∧∧∧∧∧有時還可以在結(jié)點結(jié)構(gòu)中增加一個指向父親的指針。數(shù)據(jù)域左指針域右指針域datarchildlchildfather父指針域datalchildrchildfather采用何種存儲結(jié)構(gòu)，依賴于進行何種操作基本操作P:InitBiTree(&T)DestroyBiTree(&T)CreateBiTree(&T)BiTreeEmpty(T)InsertChild(＆T，A，X)操作:

二叉樹T

存在，向T中插入一個信息域為A的結(jié)點，作為T中信息域為X的結(jié)點的左兒子，而其原來的左子樹為新結(jié)點的左子樹

。DeleteChild(＆T，p，LR)操作:根據(jù)LR

為0或1，刪除T

中p

所指結(jié)點的左或右子樹。PreOrderTraverse(T，visit())操作:先序遍歷二叉樹T。InOrderTraverse(T，visit())操作:中序遍歷二叉樹T。PostOrderTraverse(T，visit())操作:后序遍歷二叉樹T。LevelOrderTraverse(T，visit())操作:層次遍歷二叉樹T。二叉樹的基本操作遍歷二叉樹遍歷二叉樹

:如何按某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。

D＝(root，DL，DR)。如果能依次遍歷這三部分，就可以遍歷整個二叉樹；設以D、L、R

分別表示訪問根結(jié)點、遍歷左子樹、遍歷右子樹，則可以存在

6

種遍歷方案:DLR、DRL、LDR、LRD、RDL、RLD；若限定先左后右的原則，則只有3

種情況:先(根)序遍歷、中(根)序遍歷、后(根)序遍歷。DLRLDR、LRD、DLRRDL、RLD、DRL先(根)序遍歷:若二叉樹為空，則返回；否則(1)訪問根結(jié)點；(2)先(根)序遍歷左子樹；(3)先(根)序遍歷右子樹；AAABCABCADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:printf(T->data);PreOrderTraverse

(T->lchild);PreOrderTraverse(T->rchild);{if(T){}StatusPreOrderTraverse(BiTree

T)}算法10.1

先序遍歷遞歸算法elsereturnOK;算法的C語言實現(xiàn)：voidPreOrderTraverse(BiTreeT){{if(T!=NULL){printf("%d\t",T->data);

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);}}ABCDEFGH先序遍歷000000000beginend先序遍歷順序:ABDFGCEHABDFGCEH中(根)序遍歷:若二叉樹為空，則返回；否則(2)訪問根結(jié)點；(1)中(根)序遍歷左子樹；(3)中(根)序遍歷右子樹；AAABCBACADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:printf(T->data);InOrderTraverse

(T->lchild);InOrderTraverse(T->rchild);If(T){}elsereturnOK;StatusInOrderTraverse(BiTree

T)

){}算法10.2

中序遍歷遞歸算法ABCDEFGH中序遍歷000000000beginend中序遍歷順序:ABDFGCEHBFDGACEH后(根)序遍歷:若二叉樹為空，則返回；否則(3)訪問根結(jié)點；(1)后(根)序遍歷左子樹；(2)后(根)序遍歷右子樹；AAABCBCAADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:Bprintf(T->data);PostOrderTraverse

(T->lchild);PostOrderTraverse(T->rchild);If(T){}elsereturnOK;StatusPostOrderTraverse(BiTree

T){}算法10.3

后序遍歷遞歸算法ABCDEFGH后序遍歷000000000beginend后序遍歷順序:FGDBHECAABDFGCEH例，表達式a+b*c–d/e-+

/*d

ebca先序遍歷:–+a*bc/de前綴式，波蘭式中序遍歷:a+b*c–d/e中綴式，算術表達式后序遍歷:abc*+de/-后綴式，逆波蘭式中綴表示:適于人的思維后綴表示:適于計算機的思維a+b*c–d/eabc*+de/-ABCDEFGH000000000beginend中序遍歷順序:ABDFGCEHBFDGACEH用棧實現(xiàn)中序遍歷的非遞歸算法棧用來打印結(jié)點信息及訪問右子樹

{InitStack(S);p=T;pop(S,p);p=p->rchild;//遍歷右子樹{if(p){Push(S,p);p=p->lchild;}//遍歷左子樹else{}While(p||!StackEmpty(S))}ReturnOK;StatusInOrderTraverse(BiTree

T)}printf(p->data);

//打印根結(jié)點用C語言實現(xiàn)中序遍歷的非遞歸算法voidInOrderTraverse(BiTreeT){inti=0;

BiTreep,s[M];p=T;while(p!=NULL||i>0){if(p)//如果當前結(jié)點非空

{s[i++]=p;//則當前結(jié)點入棧

p=p->lchild;//然后將p的左子樹作為新的當前結(jié)點(遍歷左子樹)}else{p=s[--i];//否則彈出當前棧頂元素

printf(“%d\t”,p->data);//輸出元素的值

p=p->rchild;//然后將p的右子樹作為新的當前結(jié)點(遍歷右子樹)}}ABCDEFGH000000000beginend中序遍歷順序:ABDFGCEH例，ABDFGCEH對二叉樹除可以進行先序、中序、后序的遍歷外，還可以進行層次遍歷。

H

CF

ED

A層次遍歷:H,C,D,F,E,A過程:打印H；打印H

的左兒子C；打印C

的左、右兒子F、E；打印D的左、右兒子A；打印H

的右兒子D；隊列實現(xiàn)層次遍歷

H

CF

ED

AH入隊出隊HCDCFEDAFEAEnQueue(Q,T);While(!QueueEmpty(Q)){}ReturnOK;StatusLevelOrderTraverse(BiTree

T){}printf(p->data);

//打印結(jié)點DeQueue(Q,p);EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);

H

CF

ED

AHCDFEA占用了六個空間HHCDCFEDAFEA二叉樹插入操作利用遍歷可以實現(xiàn)二叉樹的插入、刪除操作。InsertChild(T，A，X)操作:

二叉樹T

存在，向T中插入一個數(shù)據(jù)域為X的結(jié)點，作為T中數(shù)據(jù)域為A的結(jié)點的左兒子，而其原來的左子樹為新結(jié)點的左子樹

。思想:1.首先找到數(shù)據(jù)域為A

的結(jié)點p

。2.建立數(shù)據(jù)域為X

的新結(jié)點q

。3.q->lchild=p->lchild

。4.p->lchild=q。p

H

AF

ED

GXq//找到信息域為A的結(jié)點p

。q=(BiTNode

*)malloc

(sizeof(BiTNode))；//新結(jié)點

if(!q)exit(OVERFLOW)；q->data=x;

q->lchild=p->lchild

；p->lchild=q；InsertChild(BiTree

&T

，TElemType

A

，TElemType

X){}InitStack(S);p=T;Pop(S,p);p=p->rchild;//遍歷右子樹If(p){Push(S,p);p=p->lchild;}//遍歷左子樹Else{}While(p||!StackEmpty(S)){}ReturnERROR;StatusInOrderTraverse(BiTree

T,TElemType

A,BitNode

&p){}if(p->data==A)

returnOK;//找到結(jié)點//用中序遍歷的方法，找到信息域為A的結(jié)點p。性質(zhì):

含有n個結(jié)點的二叉鏈表中有n+1

個空鏈域。證明:(1)設，終端結(jié)點數(shù)為n0，度為1的結(jié)點數(shù)為n1，故二叉樹的結(jié)點總數(shù)為n=n0+n1+n2

；度為2的結(jié)點數(shù)為n2，(2)空鏈域個數(shù)為2n0+n1，已知，n0=n2+1

，故，2n0+n1=n0+n1+n2+1=n+1樹和森林樹的存儲結(jié)構(gòu)父親表示法兒子表示法鏈式存儲順序存儲父親兒子表示法二叉樹表示法RBACDEFHGK一.父親表示法用一組地址連續(xù)空間存儲樹的結(jié)點，每個結(jié)點由兩個域組成。RBACDEFHGKdatafather數(shù)據(jù)域指示器，指向其父結(jié)點R-1A0B0C0D1E1F30123456789G6H6K6無父結(jié)點父結(jié)點為R父結(jié)點為Atypedef

struct

PTNode{}PTNode

；//定義樹結(jié)點TElemType

data

；//數(shù)據(jù)域int

father

；//指示器，指向其父結(jié)點#defineMAX_TREE_SIZE100//定義最大結(jié)點數(shù)typedef

struct{}PTree

；//定義樹PTNode

nodes[MAX_TREE_SIZE]

；//順序結(jié)構(gòu)存儲int

r，n

；//根的位置和結(jié)點總數(shù)樹的父親表示法存儲表示R-1A0B0C0D1E1F30123456789G6H6K6結(jié)構(gòu)特點:優(yōu):

獲取祖先結(jié)點(根結(jié)點)比較方便RBACDEFHGK缺:

獲取某個結(jié)點的兒子結(jié)點需要遍歷整個結(jié)構(gòu)二.兒子表示法1.多叉樹表示法——鏈式存儲AchildA1childA2childA3BchildB1childB2childB3CchildC1childC2childC3DchildD1childD2childD3鏈表中的結(jié)點存在兩種格式:childnchild2child1data...每個結(jié)點均采用定長格式，n為樹的度。childnchild2child1data...degree每個結(jié)點采用變長格式，degree=n為該結(jié)點的度。定長操作方便，變長操作不方便結(jié)構(gòu)分析定長浪費空間，變長節(jié)省空間采用定長存儲格式，鏈表中存在很多空鏈域，造成空間浪費。定義:在一棵有n

個結(jié)點，度為k

的樹中必有(k-1)n+1

個空鏈域。證明:(1)設度為0、1、、k的結(jié)點數(shù)分別為n0、n1、、nk

......設樹中空鏈域總數(shù)為X則有X=kn0+(k-1)n1++(k-(k-1))nk-1+(k-k)nk...=kn0+kn1++knk-1+knk...-(n1+2n2++(k-1)nk-1+knk

)...(2)另外除根結(jié)點外，其它結(jié)點都有一個分支進入，設B

為分支總數(shù)，故n=B+1

，首先

n=n0+n1++nk

...又由于這些分支均是由度為1、2、、k的結(jié)點引出的，...所以有B=n1+2n2++(k-1)nk-1+knk

...=kn0+kn1++knk-1+knk...-(n1+2n2++(k-1)nk-1+knk

)...X=kn

-B=kn

–(n-1)=(k–1)n+1得證2.順序存儲把每個結(jié)點的兒子結(jié)點以單鏈表的結(jié)構(gòu)存儲；則n個結(jié)點就構(gòu)成了n條兒子單鏈表；將n條單鏈表頭指針以順序線性表存儲；RBACDEFHGK0123456789B

∧A

C

D

∧E

∧R

F

G

∧H

∧K

∧45∧13∧26∧79∧80123456789B

∧A

C

D

∧E

∧R

F

G

∧H

∧K

∧45∧13∧26∧79∧8typedef

struct

CTNode{}*

ChildPtr

；//兒子結(jié)點

int

child

；

struct

CTNode

*next

；typedef

struct{}CTBox

；//兒子頭指針

TElemType

data

；

ChildPtr

firstchild

；typedef

struct{}CTree

；//樹結(jié)構(gòu)#defineMAX_TREE_SIZE100//定義最大結(jié)點數(shù)

CTBox

nodes[MAX_TREE_SIZE]

；int

r，n

；//根的位置和結(jié)點總數(shù)RBACDEFHGK0123456789B

∧A

C

D

∧E

∧R

F

G

∧H

∧K

∧45∧13∧26∧79∧8優(yōu)點:

方便搜索兒子結(jié)點缺點:

查找父結(jié)點需要從頭遍歷整個順序表三.父親兒子表示法如何既能方便搜索兒子結(jié)點，又能方便查找父結(jié)點？0123456789B

∧A

C

D

∧E

∧R

F

G

∧H

∧K

∧45∧13∧26∧79∧8-1000113666四.二叉樹表示法將樹以二叉樹的形式表示。令結(jié)點的兩個鏈域分別指向該結(jié)點的第一個兒子和右邊的兄弟。RBACDEFHGK∧∧∧RADBE∧C∧F∧G∧∧H∧K∧∧∧∧∧RADBE∧C∧F∧G∧∧H∧K∧∧typedef

struct

CSNode{}CSNode

；//結(jié)點TElemType

data；struct

CSNode

*

firstchild

；struct

CSNode

*

nextsibling

；查找結(jié)點的兒子:沿結(jié)點的firstchild

域可找到第一個兒子，然后再沿nextsibling

域可找到其它兒子。查找結(jié)點的兄弟:沿結(jié)點的nextsibling

域可找到所有兄弟。查找結(jié)點的父親:為每個結(jié)點增加一個father

域指向父結(jié)點。RBACDEFHGK∧∧∧RADBE∧C∧F∧G∧∧H∧K∧∧性質(zhì):1.樹可以表示成二叉樹的形式啟示:

樹與二叉樹的轉(zhuǎn)換2.樹轉(zhuǎn)換成一棵只有左子樹的二叉樹森林與二叉樹的轉(zhuǎn)換ACBDEFGHIJ(1).任何一棵樹都可以轉(zhuǎn)換為一棵沒有右子樹的二叉樹。(2).森林是由若干棵樹構(gòu)成的集合，若把森林中第二棵樹的根結(jié)點看成是第一棵樹的根結(jié)點兄弟，就可以導出森林與二叉樹的轉(zhuǎn)換。1.森林轉(zhuǎn)換成二叉樹(1)增加一個根結(jié)點，作為原森林中各樹根結(jié)點的父結(jié)點。(2)將新樹轉(zhuǎn)換成二叉樹。(3)刪除二叉樹的根結(jié)點。ACBDEFGHIJRBECDFGHIJRA2.二叉樹轉(zhuǎn)換成森林(1)增加一個新根結(jié)點，原二叉樹根結(jié)點做為新根結(jié)點的左兒子。(2)將新二叉樹轉(zhuǎn)換成樹。(3)刪除樹的根結(jié)點變?yōu)樯帧ECDFGHIJARACBDEFGHIJR2.二叉樹轉(zhuǎn)換成森林(1)增加一個新根結(jié)點，原二叉樹根結(jié)點做為新根結(jié)點的左兒子。(2)將新二叉樹轉(zhuǎn)換成樹。(3)刪除樹的根結(jié)點變?yōu)樯?。BECDFGHIJARACBDEFGHIJR森林和樹的遍歷

1.分割從結(jié)構(gòu)上，可以把任意的森林分成三部分:1)第一棵樹的根結(jié)點。2)第一棵樹根結(jié)點的子樹構(gòu)成的森林。3)其余的樹構(gòu)成的森林。按這三部分的不同排列次序可把森林的遍歷次序分為前序、中序、后序。2)訪問第一棵樹的根結(jié)點。3)按前序遍歷根結(jié)點的子樹構(gòu)成的森林。4)按前序遍歷其余的樹構(gòu)成的森林。森林的前序遍歷1)如果森林中樹的個數(shù)為0，則返回。ACBDEFGHIJBECDFGHIJAABCDEFGHIJ3)訪問第一棵樹的根結(jié)點。2)按中序遍歷第一棵樹根結(jié)點的子樹構(gòu)成的森林。4)按中序遍歷其余的樹構(gòu)成的森林。森林的中序遍歷1)如果森林中樹的個數(shù)為0，則返回。ACBDEFGHIJBECDFGHIJABCDAFEHJIG4)訪問第一棵樹的根結(jié)點。2)按后序遍歷第一棵樹根結(jié)點的子樹構(gòu)成的森林。3)按后序遍歷其余的樹構(gòu)成的森林。森林的后序遍歷1)如果森林中樹的個數(shù)為0，則返回。ACBDEFGHIJBECDFGHIJABCDFHJIGEA森林的前、中、后序遍歷與對應二叉樹的前、中、后序遍歷一致。樹的應用1.二叉分類樹(二叉排序樹)2.判定樹3.赫夫曼樹(最優(yōu)二叉樹)赫夫曼樹Huffman(最優(yōu)二叉樹)基本概念:從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑。

路徑上的分支數(shù)目稱做路徑長度。

XYZX到Y(jié)的路徑路徑長度為2樹的路徑長度是從樹根到每一個結(jié)點的路徑長度之和。

在具有相同結(jié)點數(shù)的所有二叉樹中，的路徑長度是最短的。完全二叉樹推廣：為結(jié)點加權(quán)w。735ABCDE結(jié)點的帶權(quán)路徑長度為從根結(jié)點到該結(jié)點之間的路徑長度與結(jié)點上權(quán)值的乘積。樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記做WPL=∑

wk

L(vk

)

nk=1wk為葉子結(jié)點vk

的權(quán)值L(vk

)為葉子結(jié)點vk

的路徑長度例，3棵二叉樹，都有4個葉子結(jié)點a、b、c、d，分別帶權(quán)7、5、2、4，求它們各自的帶權(quán)路徑長度。abcd7524(1)abdc7542(2)cdba2457(3)(1)WPL=7×2+5×2+2×2+4×2=36(2)WPL=7×3+5×3+2×1+4×2=46(3)WPL=7×1+5×2+2×3+4×3=35假設有n個權(quán)值

{w1,w2,…

wn}，試構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子結(jié)點帶權(quán)為

wi

，則其中帶權(quán)路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或赫夫曼樹。

如何構(gòu)造赫夫曼樹？(1)根據(jù)給定的n個權(quán)值{w1,w2,…

wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…Tn}，其中每棵二叉樹Ti中只有一個權(quán)值為wi

的根結(jié)點。(2)在F中選取兩棵根結(jié)點權(quán)值最小的樹作為左、右子樹構(gòu)造一棵新的二叉樹，且置新二叉樹的根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和。(3)在F中刪除這兩棵樹，同時將新得到的二叉樹加入集合F

中。(4)重復(2)和(3)，直到F

中只含一棵樹為止。例，4個葉子結(jié)點a、b、c、d，分別帶權(quán)7、5、2、4。cd24b5a7初始cd246b5cd24611a7b5cd2461118赫夫曼編碼1.編碼例，傳送ABACCD，四種字符，可以分別編碼為00,01,10,11。則原電文轉(zhuǎn)換為000100101011。對方接收后，采用二位一分進行譯碼。電文編碼二進制二進制譯碼電文當然，為電文編碼時，總是希望總長越短越好，如果對每個字符設計長度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用較短的編碼，則可以減短電文的總長。例，對ABACCD重新編碼，分別編碼為0,00,1,01。ABCD則原電文轉(zhuǎn)換為00001101。減短了。問題:如何譯碼？前四個二進制字符就可以多種譯法。AAAABB2.前綴編碼若設計的長短不等的編碼，滿足任一個編碼都不是另一個編碼的前綴，則這樣的編碼稱為前綴編碼。例，

A,B,C,D前綴編碼可以為0,110,10,111利用二叉樹設計二進制前綴編碼。葉子結(jié)點表示A,B,C,D這4個字符ACBD000111左分支表示‘0’，右分支表示‘1’從根結(jié)點到葉子結(jié)點的路徑上經(jīng)過的二進制符號串作為該葉子結(jié)點字符的編碼A(0)B(110)C(10)D(111)路徑長度為編碼長度如何得到最短的二進制前綴編碼？3.赫夫曼編碼設每種字符在電文中出現(xiàn)的概率wi

為，則依此n個字符出現(xiàn)的概率做權(quán)，可以設計一棵赫夫曼樹，使WPL=∑

wi

li

最小ni=1wi

為葉子結(jié)點的出現(xiàn)概率(權(quán))li

為根結(jié)點到葉子結(jié)點的路徑長度例，某通信可能出現(xiàn)ABCDEFGH8個字符，其概率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，試設計赫夫曼編碼不妨設w={5,29,7,8,14,23,3,11}排序后

w={3,5,7,8,11,14,23,29}{7,8,8,11,14,23,29}{8,11,14,15,23,29}{14,15,19,23,29}{19,23,29,29}{29,29,42}{42,58}100{100}01100110101010A(0110)B(10)C(1110)D(1111)E(110)F(00)G(0111)H(010)AG8537815CD1119H1429E

F4223

B5829ACEA編碼為011011101100110如何譯碼？1.

從根結(jié)點出發(fā)，從左至右掃描編碼，2.

若為‘0’則走左分支，若為‘1’則走右分支，直至葉結(jié)點為止，3.

取葉結(jié)點字符為譯碼結(jié)果，返回重復執(zhí)行1,2,3

直至全部譯完為止10001100110101010A(0110)B(10)C(1110)D(1111)E(110)F(00)G(0111)H(010)AG8537815CD1119H1429E

F4223

B5829ACEA作業(yè):假設用于通訊的電文由8個字母組成，ABCDEFGH，字母在電文中的出現(xiàn)頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，試設計赫夫曼編碼。本章重點1．

二叉樹的存儲結(jié)構(gòu)及其各種操作，遍歷二叉樹2．

樹和森林與二叉樹的轉(zhuǎn)換關系，樹的遍歷3.哈夫曼樹和哈夫曼編碼本章難點1．

遍歷二叉樹的算法2．

樹和森林與二叉樹的轉(zhuǎn)換關系，哈夫曼樹及編碼典型例題：一、選擇題1、

在樹中，互為堂兄弟的結(jié)點擁有相同的()。

A、雙親

B、祖先

C、層次

D、孩子2、

樹最適合用來表示（）。

A、有序數(shù)據(jù)元素

B、無序數(shù)據(jù)元素

C、元素之間具有分支層次關系的數(shù)據(jù)

D、元素之間無聯(lián)系的數(shù)據(jù)3、

在一棵高度為h的滿四叉樹中，結(jié)點總數(shù)為()。

A、(4^h-1)/3

B、(4^h-1)/2

C、(4^h-1)/4

D、4^h4、

若一棵二叉樹具有10個度為2的結(jié)點，則該二叉樹的度為0的結(jié)點個數(shù)是()。

A.9

B.11

C.12

D.不確定5、

按二叉樹的定義，具有3個結(jié)點的二叉樹有()種。

A、3B、4C、5D、6二、填空1、

在樹中，度為()的結(jié)點稱為葉子。2、

在樹中，除根結(jié)點外，其他結(jié)點都有且只有一個()結(jié)點。3、

有100個結(jié)點的樹有()條邊。4、

若將樹中的每個結(jié)點的各子樹看成從左到右有次序，則該樹為()樹。5、

一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點有()個。6、深度為K的完全二叉樹至少有2^(k-1)個結(jié)點，至多有2^(k-1)+1個結(jié)點，若按自上而下，從左到右次序給結(jié)點編號（從1開始），則編號最小的葉子結(jié)點的編號是()。

三、問答題：1、若二叉樹中各結(jié)點的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。

(1)已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請畫出此二叉樹。

(2)已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，請畫出此二叉樹。

(3)已知一棵二叉樹的前序序列和后序序列分別為AB和BA，請畫出這兩棵不同的二叉樹。

2、一棵度為2的有序樹與一棵二叉樹有何區(qū)別?答：一棵度為二的有序樹與一棵二叉樹的區(qū)別在于:有序樹的結(jié)點