樹的概念二叉樹的概念二叉樹的性質二叉樹的存儲結構及實現(xiàn)樹的存儲結構樹、森林與二叉樹的轉換哈夫曼樹第6章樹和二叉樹本章的主要內容是樹的定義樹：n（n≥0）個結點的有限集合。當n＝0時，稱為空樹；任意一棵非空樹滿足以下條件：⑴

有且僅有一個特定的稱為根的結點；⑵

當n＞1時，除根結點之外的其余結點被分成m（m>0）個互不相交的有限集合T1,T2,…,Tm，其中每個集合又是一棵樹，并稱為這個根結點的子樹。6.1樹的概念樹的定義是采用遞歸方法(a)一棵樹結構(b)一個非樹結構(c)一個非樹結構樹的定義ACBGFEDHIACBGFDACBGFDE6.1樹的概念樹的應用舉例——文件結構MyComputerC:D:E:etcWINDOWSProgramFilesPictureMusic…………………………………………6.1樹的概念(A(B(E(F),G),C,D(H(I),J,K(L)))

(c)

廣義表表示法A

BDJCKLHIEFG(a)

文氏圖表示法

A

B

E

F

G

C

D

H

I

J

K

L(

b)

凹入表示法6.1樹的概念樹的基本術語結點的度：結點所擁有的子樹的個數(shù)。樹的度：樹中各結點度的最大值。CGBDEFKLHMIJA6.1樹的概念葉子結點：度為0的結點，也稱為終端結點。分支結點：度不為0的結點，也稱為非終端結點。CGBDEFKLHMIJA樹的基本術語6.1樹的概念孩子、雙親：樹中某結點子樹的根結點稱為這個結點的孩子結點，這個結點稱為它孩子結點的雙親結點；兄弟：具有同一個雙親的孩子結點互稱為兄弟。

CGBDEFKLHMIJA樹的基本術語6.1樹的概念路徑：如果樹的結點序列n1,n2,…,nk有如下關系：結點ni是ni+1的雙親（1<=i<k），則把n1,n2,…,nk稱為一條由n1至nk的路徑；路徑上經過的邊的個數(shù)稱為路徑長度。CGBDEFKLHMIJA樹的基本術語6.1樹的概念祖先、子孫：在樹中，如果有一條路徑從結點x到結點y，那么x就稱為y的祖先，而y稱為x的子孫。CGBDEFKLHMIJA樹的基本術語6.1樹的概念結點所在層數(shù)：根結點的層數(shù)為1；對其余任何結點，若某結點在第k層，則其孩子結點在第k+1層。樹的深度：樹中所有結點的最大層數(shù)，也稱高度。1層2層4層3層高度＝4CGBDEFKLHMIJA樹的基本術語6.1樹的概念CBDEFKLHJA71234568910層序編號：將樹中結點按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。樹的基本術語6.1樹的概念有序樹、無序樹：如果一棵樹中結點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結構中討論的一般都是有序樹

樹的基本術語ACBGFEDACBGFED6.1樹的概念CBDEFKLHJ森林：m(m≥0)棵互不相交的樹的集合。

樹的基本術語A6.1樹的概念同構：對兩棵樹，若通過對結點適當?shù)刂孛?，就可以使這兩棵樹完全相等（結點對應相等，結點對應關系也相等），則稱這兩棵樹同構。樹的基本術語ACBGFEDDAECFBG6.1樹的概念樹結構和線性結構的比較線性結構樹結構第一個數(shù)據(jù)元素根結點（只有一個）無前驅無雙親最后一個數(shù)據(jù)元素葉子結點(可以有多個)無后繼無孩子其它數(shù)據(jù)元素其它結點一個前驅,一個后繼一個雙親,多個孩子一對一一對多6.1樹的概念二叉樹的定義

二叉樹是n（n≥0）個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。6.2二叉樹問題轉化：將樹轉換為二叉樹，從而利用二叉樹解決樹的有關問題。研究二叉樹的意義？二叉樹的特點：⑴每個結點最多有兩棵子樹；⑵二叉樹是有序的，其次序不能任意顛倒。

ABCDEFGABAB6.2二叉樹二叉樹的基本形態(tài)Ф空二叉樹只有一個根結點左子樹根結點只有左子樹右子樹根結點只有右子樹左子樹右子樹根結點同時有左右子樹6.2二叉樹具有3個結點的樹和具有3個結點的二叉樹的形態(tài)二叉樹和樹是兩種樹結構。6.2二叉樹特殊的二叉樹斜樹1.所有結點都只有左子樹的二叉樹稱為左斜樹；2.所有結點都只有右子樹的二叉樹稱為右斜樹；3.左斜樹和右斜樹統(tǒng)稱為斜樹。1.在斜樹中，每一層只有一個結點；2.斜樹的結點個數(shù)與其深度相同。

斜樹的特點：ABCABC6.2二叉樹滿二叉樹在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上。滿二叉樹的特點：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結點。特殊的二叉樹CDEFGHIJKLMNO11121314156.2二叉樹滿二叉樹不是滿二叉樹，雖然所有分支結點都有左右子樹，但葉子不在同一層上。滿二叉樹在同樣深度的二叉樹中結點個數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結點個數(shù)最多A1523467BCDEFGLM89特殊的二叉樹6.2二叉樹完全二叉樹對一棵具有n個結點的二叉樹按層序編號，編號為i（1≤i≤n）的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中的位置完全相同。特殊的二叉樹CDEFGHIJKLMNO1112131415CDEFGHIJ6.2二叉樹在滿二叉樹中，從最后一個結點開始，連續(xù)去掉任意個結點，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結點10與滿二叉樹中的結點10不是同一個結點特殊的二叉樹6.2二叉樹1.葉子結點只能出現(xiàn)在最下兩層，且最下層的葉子結點都集中在二叉樹的左部；2.完全二叉樹中如果有度為1的結點，只可能有一個，且該結點只有左孩子。

3.深度為k的完全二叉樹在k-1層上一定是滿二叉樹。完全二叉樹的特點特殊的二叉樹CDEFGHIJ6.2二叉樹二叉樹的基本性質

性質6-1二叉樹的第i層上最多有2i-1個結點（i≥1）。

證明：當i=1時，第1層只有一個根結點，而2i-1=20=1，結論顯然成立。假定i=k（1≤k＜i）時結論成立，即第k層上至多有2k-1個結點，則

i=k+1時，因為第k+1層上的結點是第k層上結點的孩子，而二叉樹中每個結點最多有2個孩子，故在第k+1層上最大結點個數(shù)為第k層上的最大結點個數(shù)的二倍，即2×2k-1＝2k。結論成立。6.2二叉樹性質6-2一棵深度為k的二叉樹中，最多有2k-1個結點，最少有k個結點。

證明：由性質1可知，深度為k的二叉樹中結點個數(shù)最多==2k-1；每一層至少要有一個結點，因此深度為k的二叉樹，至少有k個結點。深度為k且具有2k-1個結點的二叉樹一定是滿二叉樹，深度為k且具有k個結點的二叉樹不一定是斜樹。！二叉樹的基本性質

6.2二叉樹性質6-3在一棵二叉樹中，如果葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則有:n0＝n2＋1。

證明:設n為二叉樹的結點總數(shù)，n1為二叉樹中度為1的結點數(shù)，則有：

n＝n0＋n1＋n2

在二叉樹中，除了根結點外，其余結點都有唯一的一個分枝進入，由于這些分枝是由度為1和度為2的結點射出的，一個度為1的結點射出一個分枝，一個度為2的結點射出兩個分枝，所以有：

n＝n1＋2n2＋1因此可以得到：n0＝n2＋1。二叉樹的基本性質

6.2二叉樹在有n個結點的滿二叉樹中，有多少個葉子結點？因為在滿二叉樹中沒有度為1的結點，只有度為0的葉子結點和度為2的分支結點，所以，n＝n0+n2n0＝n2+1

即葉子結點n0＝（n+1）/2

二叉樹的基本性質

性質6-3在一棵二叉樹中，如果葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則有:n0＝n2＋1。

6.2二叉樹性質6-4具有n個結點的完全二叉樹的深度為log2n+1。

證明：假設具有n個結點的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結點數(shù)最多結點數(shù)完全二叉樹的基本性質

6.2二叉樹

log2n+1[log2n]log2n[log2n]+1k所在區(qū)間證明：假設具有n個結點的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質2，有下式成立

2k-1≤n＜2k完全二叉樹的基本性質

性質6-4具有n個結點的完全二叉樹的深度為log2n+1。

對不等式取對數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數(shù)，故必有k＝log2n+1。6.2二叉樹性質6-5對一棵具有n個結點的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1≤i≤n）的結點（簡稱為結點i），有：

（1）如果i＞1，則結點i的雙親結點的序號為

i/2；如果i＝1，則結點i是根結點，無雙親結點。(2)如果2i≤n，則結點i的左孩子的序號為2i；如果2i＞n，則結點i無左孩子。(3)如果2i＋1≤n，則結點i的右孩子的序號為2i＋1；如果2i＋1＞n，則結點

i無右孩子。

完全二叉樹的基本性質

6.2二叉一棵具有n個結點的完全二叉樹中從1開始按層序編號，則結點i的雙親結點為

i/2；結點i的左孩子為2i；結點i的右孩子為2i＋1。

性質5表明，在完全二叉樹中，結點的層序編號反映了結點之間的邏輯關系。完全二叉樹的基本性質

6.2二叉樹二叉樹的遍歷操作

二叉樹的遍歷是指從根結點出發(fā)，按照某種次序訪問二叉樹中的所有結點，使得每個結點被訪問一次且僅被訪問一次。二叉樹遍歷操作的結果？非線性結構線性化6.3二叉樹的遍歷抽象操作，可以是對結點進行的各種處理，這里簡化為輸出結點的數(shù)據(jù)。前序遍歷中序遍歷后序遍歷層序遍歷

二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD

如果限定先左后右，則二叉樹遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號的次序訪問各結點。

考慮二叉樹的組成：根結點D左子樹L右子樹R二叉樹6.3二叉樹的遍歷前序（根）遍歷若二叉樹為空，則空操作返回；否則：①訪問根結點；②前序遍歷根結點的左子樹；③前序遍歷根結點的右子樹。前序遍歷序列：ABDGCEFABCDEFG二叉樹的遍歷操作

6.3二叉樹的遍歷中序（根）遍歷若二叉樹為空，則空操作返回；否則：①中序遍歷根結點的左子樹；②訪問根結點；③中序遍歷根結點的右子樹。

中序遍歷序列：DGBAECFABCDEFG二叉樹的遍歷操作

6.3二叉樹的遍歷后序（根）遍歷若二叉樹為空，則空操作返回；否則：①后序遍歷根結點的左子樹；②后序遍歷根結點的右子樹。③訪問根結點；后序遍歷序列：GDBEFCAABCDEFG二叉樹的遍歷操作

6.3二叉樹的遍歷層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。

層序遍歷序列：ABCDEFGABCDEFG二叉樹的遍歷操作

6.3二叉樹的遍歷-%/+*abcdef二叉樹遍歷操作練習前序遍歷結果：-+a*b%cd/ef中序遍歷結果：a+b*c%d-e/f后序遍歷結果：abcd%*+ef/-6.3二叉樹的遍歷若已知一棵二叉樹的前序（或中序，或后序，或層序）序列，能否唯一確定這棵二叉樹呢？ABC例：已知前序序列為ABC，則可能的二叉樹有5種。ABC二叉樹的遍歷操作

6.3二叉樹的遍歷例：已知前序遍歷序列為ABC，后序遍歷序列為CBA，則下列二叉樹都滿足條件。ABCABC若已知一棵二叉樹的前序序列和后序序列，能否唯一確定這棵二叉樹呢？二叉樹的遍歷操作

6.3二叉樹的遍歷若已知一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定？

例如：已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI，如何構造該二叉樹呢?

二叉樹的遍歷操作

6.3二叉樹的遍歷前序：ABCDEFG

HI中序：BCAEDGHFI前序：BC中序：BC

BCDEFGHIA前序：DEFGHI中序：EDGHFIABCDEFGHI6.3二叉樹的遍歷前序：FG

HI中序：GHFI前序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH6.3二叉樹的遍歷1.根據(jù)前序序列的第一個元素建立根結點；2.在中序序列中找到該元素，確定根結點的左右子樹的中序序列；3.在前序序列中確定左右子樹的前序序列；4.由左子樹的前序序列和中序序列建立左子樹；5.由右子樹的前序序列和中序序列建立右子樹。已知一棵二叉樹的前序序列和中序序列，構造該二叉樹的過程如下：

二叉樹的遍歷操作

6.3二叉樹的遍歷順序存儲結構二叉樹的順序存儲結構就是用一維數(shù)組存儲二叉樹中的結點，并且結點的存儲位置（下標）應能體現(xiàn)結點之間的邏輯關系——父子關系。

如何利用數(shù)組下標來反映結點之間的邏輯關系?完全二叉樹和滿二叉樹中結點的序號可以唯一地反映出結點之間的邏輯關系。6.4二叉樹的存儲結構及實現(xiàn)

A

B

C

D

E

F

G

H

I

J數(shù)組下標12345678910完全二叉樹的順序存儲CDEFGHIJ以編號為下標6.4二叉樹的存儲結構及實現(xiàn)二叉樹的順序存儲ABC∧DE∧∧∧F∧∧G數(shù)組下標12345678910111213ABCDFGE以編號為下標ABCDFGE123561013按照完全二叉樹編號6.4二叉樹的存儲結構及實現(xiàn)一棵斜樹的順序存儲會怎樣呢？深度為k的右斜樹，k個結點需分配2k－1個存儲單元。

一棵二叉樹改造后成完全二叉樹形態(tài)，需增加很多空結點，造成存儲空間的浪費。二叉樹的順序存儲結構一般僅存儲完全二叉樹ABC137D156.4二叉樹的存儲結構及實現(xiàn)二叉鏈表基本思想：令二叉樹的每個結點對應一個鏈表結點，鏈表結點除了存放與二叉樹結點有關的數(shù)據(jù)信息外，還要設置指示左右孩子的指針。

結點結構：

lchild

data

rchild其中，data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)信息；lchild：左指針域，存放指向左孩子的指針；rchild：右指針域，存放指向右孩子的指針。

6.4二叉樹的存儲結構及實現(xiàn)typedefintdatatypetypedefstructBiNode{datatypedata;structBiNode*lchild,*rchild;}bitree;lchild

datarchild左孩子結點右孩子結點二叉鏈表6.4二叉樹的存儲結構及實現(xiàn)GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表具有n個結點的二叉鏈表中，有多少個空指針？6.4二叉樹的存儲結構及實現(xiàn)GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表6.4二叉樹的存儲結構及實現(xiàn)具有n個結點的二叉鏈表中，有n+1個空指針。前序遍歷——遞歸算法voidPreOrder(bitree*root)

{if(root==NULL)return;else{printf(“%d”,root->data);

PreOrder(root->lchild);PreOrder(root->rchild);}}6.4二叉樹的存儲結構及實現(xiàn)AGBCDFE6.4二叉樹的存儲結構及實現(xiàn)前序遍歷算法的執(zhí)行軌跡二叉樹前序遍歷的非遞歸算法的關鍵：在前序遍歷過某結點的整個左子樹后，如何找到該結點的右子樹的根指針。解決辦法：在訪問完該結點后，將該結點的指針保存在棧中，以便以后能通過它找到該結點的右子樹。

在前序遍歷中，設要遍歷二叉樹的根指針為root，則有兩種可能：⑴若root!=NULL，則表明？如何處理？⑵若root==NULL，則表明？如何處理？6.4二叉樹的存儲結構及實現(xiàn)前序遍歷——非遞歸算法訪問結點序列:A棧S內容:BD

A

B前序遍歷的非遞歸實現(xiàn)

6.4二叉樹的存儲結構及實現(xiàn)ADBC訪問結點序列:A棧S內容:BD

A前序遍歷的非遞歸實現(xiàn)

6.4二叉樹的存儲結構及實現(xiàn)ADBC

D訪問結點序列:A棧S內容:BD

C前序遍歷的非遞歸實現(xiàn)

6.4二叉樹的存儲結構及實現(xiàn)ADBCC1.棧s初始化；2.循環(huán)直到root為空且棧s為空

2.1當root不空時循環(huán)

2.1.1輸出root->data;2.1.2將指針root的值保存到棧中；

2.1.3繼續(xù)遍歷root的左子樹

2.2如果棧s不空，則

2.2.1將棧頂元素彈出至root；

2.2.2準備遍歷root的右子樹；前序遍歷——非遞歸算法（偽代碼）6.4二叉樹的存儲結構及實現(xiàn)前序遍歷——非遞歸算法（偽代碼）6.4二叉樹的存儲結構及實現(xiàn)//bitree*s[Maxsize];inttop;voidPreOrder(bitree*root){bitree*p=root;top=-1;//采用順序棧，并假定不會發(fā)生上溢

while(p!=NULL||top!=-1){while(p!=NULL){

printf(“%d”,p->data);s[++top]=p;p=p->lchild;}if(top!=-1){p=s[top--];p=p->rchild;}}}中序遍歷——遞歸算法

voidInOrder(bitree*root){if(root==NULL)return;else{InOrder(root->lchild);

printf(“%d”,root->data);

InOrder(root->rchild);}}6.4二叉樹的存儲結構及實現(xiàn)后序遍歷——遞歸算法voidPostOrder(bitree*root){if(root==NULL)return;else{PostOrder(root->lchild);

PostOrder(root->rchild);

printf(“%d”,root->data);}}6.4二叉樹的存儲結構及實現(xiàn)層序遍歷6.4二叉樹的存儲結構及實現(xiàn)ABCDEFG遍歷序列：AABCBDCEFGDEFG層序遍歷隊列Q初始化；2.如果二叉樹非空，將根指針入隊；3.循環(huán)直到隊列Q為空3.1q=隊列Q的隊頭元素出隊；3.2訪問結點q的數(shù)據(jù)域；3.3若結點q存在左孩子，則將左孩子指針入隊；3.4若結點q存在右孩子，則將右孩子指針入隊；6.4二叉樹的存儲結構及實現(xiàn)二叉樹的建立為了建立一棵二叉樹，將二叉樹中每個結點的空指針引出一個虛結點，其值為一特定值如“#”，以標識其為空，把這樣處理后的二叉樹稱為原二叉樹的擴展二叉樹。

為什么如此處理?6.4二叉樹的存儲結構及實現(xiàn)如何由一種遍歷序列生成該二叉樹？遍歷是二叉樹各種操作的基礎，可以在遍歷的過程中進行各種操作，例如建立一棵二叉樹。擴展二叉樹的前序遍歷序列:AB#D##C##6.4二叉樹的存儲結構及實現(xiàn)DBAC#DBAC####二叉樹的建立設二叉樹中的結點均為一個字符。假設擴展二叉樹的前序遍歷序列由鍵盤輸入，root為指向根結點的指針，二叉鏈表的建立過程是：首先輸入根結點，若輸入的是一個“#”字符，則表明該二叉樹為空樹，即root=NULL；否則輸入的字符應該賦給root->data,，之后依次遞歸建立它的左子樹和右子樹。6.4二叉樹的存儲結構及實現(xiàn)二叉樹的建立bitree*creatBitree(){bitree*root;charch;ch=getchar();if(ch=='#')root=NULL;else{root=(bitree*)malloc(sizeof(bitree));root->data=ch;root->lchild=creatBitree();root->rchild=creatBitree();}

returnroot;}建立二叉遞歸算法6.4二叉樹的存儲結構及實現(xiàn)二叉樹算法設計練習 遍歷二叉樹是二叉樹各種操作的基礎，遍歷算法中對每個結點的訪問操作可以是多種形式及多個操作，根據(jù)遍歷算法的框架，適當修改訪問操作的內容，可以派生出很多關于二叉樹的應用算法。voidInOrder(bitree*root){if(root==NULL)return;else{InOrder(root->lchild);

printf(“%d”,root->rchild);InOrder(root->rchild);}}二叉樹算法設計練習設計算法求二叉樹的結點個數(shù)。voidCount(bitree*root)//n為全局量并已初始化為0{if(root){Count(root->lchild);

n++;Count(root->rchild);}}二叉樹算法設計練習設計算法按前序次序打印二叉樹中的葉子結點。voidPreOrder(bitree*root){if(root){

if(!root->lchild&&!root->rchild)

printf(“%d”,root->rchild);PreOrder(root->lchild);PreOrder(root->rchild);}}二叉樹算法設計練習設計算法求二叉樹的深度。

intDepth(bitree*root){if(root==NULL)return0;else{hl=Depth(root->lchild);hr=Depth(root->rchild);returnmax(hl,hr)+1;}}三叉鏈表6.4二叉樹的存儲結構及實現(xiàn)GFEDBAABCDEFG∧∧∧∧∧∧∧∧C在二叉鏈表中，如何求某結點的雙親？三叉鏈表

lchild

dataparentrchild在二叉鏈表的基礎上增加了一個指向雙親的指針域。結點結構其中：data、lchild和rchild三個域的含義同二叉鏈表的結點結構；parent域為指向該結點的雙親結點的指針。

6.4二叉樹的存儲結構及實現(xiàn)ABCDEFGA∧B∧D∧E∧F∧CG∧∧∧∧三叉鏈表6.4二叉樹的存儲結構及實現(xiàn)線索鏈表6.4二叉樹的存儲結構及實現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：DGBAECF如果二叉樹不改變，如何保存？順序存儲DGBAECF線索鏈表6.4二叉樹的存儲結構及實現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：DGBAECF如果二叉樹改變，如何保存？鏈接存儲DF

線索鏈表6.4二叉樹的存儲結構及實現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：DGBAECF如何將二叉鏈表與中序鏈表結合？鏈接存儲DF

線索鏈表線索：將二叉鏈表中的空指針域指向前驅結點和后繼結點的指針被稱為線索；線索化：使二叉鏈表中結點的空鏈域存放其前驅或后繼信息的過程稱為線索化；線索二叉樹：加上線索的二叉樹稱為線索二叉樹。6.4二叉樹的存儲結構及實現(xiàn)如何保存二叉樹的某種遍歷序列？將二叉鏈表中的空指針域指向其前驅結點和后繼結點

ltag

lchild

data

rchild

rtag0:lchild指向該結點的左孩子1:lchild指向該結點的前驅結點0:rchild指向該結點的右孩子1:rchild指向該結點的后繼結點ltag=rtag=6.4二叉樹的存儲結構及實現(xiàn)結點結構線索鏈表enumflag{Child,Thread};typedefstructThrNode{datatypedata;structThrNode*lchild,*rchild;flagltag,rtag;}bithptr;6.4二叉樹的存儲結構及實現(xiàn)線索鏈表

ltag

lchild

data

rchild

rtag結點結構二叉樹的遍歷方式有4種，故有4種意義下的前驅和后繼，相應的有4種線索二叉樹：⑴前序線索二叉樹⑵中序線索二叉樹⑶后序線索二叉樹⑷層序線索二叉樹6.4二叉樹的存儲結構及實現(xiàn)線索二叉樹FABDCEG中序線索二叉樹6.4二叉樹的存儲結構及實現(xiàn)線索二叉樹中序序列：DGBAECF分析：建立線索鏈表，實質上就是將二叉鏈表中的空指針改為指向前驅或后繼的線索，而前驅或后繼的信息只有在遍歷該二叉樹時才能得到。6.4二叉樹的存儲結構及實現(xiàn)建立二叉鏈表遍歷二叉樹，將空指針改為線索中序線索鏈表的建立:A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程6.4二叉樹的存儲結構及實現(xiàn)已經建立起二叉鏈表A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程6.4二叉樹的存儲結構及實現(xiàn)中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點p1A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程6.4二叉樹的存儲結構及實現(xiàn)中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre1p1A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧中序線索鏈表的建立過程6.4二叉樹的存儲結構及實現(xiàn)中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p1A頭指針BCDEFG∧∧∧∧∧∧00000000000000中序線索鏈表的建立過程6.4二叉樹的存儲結構及實現(xiàn)中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p11A頭指針BCDEFG∧∧∧∧∧00000000000000中序線索鏈表的建立過程6.4二叉樹的存儲結構及實現(xiàn)中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p111A頭指針BCDEFG∧∧∧∧00000000000000中序線索鏈表的建立過程6.4二叉樹的存儲結構及實現(xiàn)中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p1111A頭指針BCDEFG∧∧∧00000000000000中序線索鏈表的建立過程6.4二叉樹的存儲結構及實現(xiàn)中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p11111A頭指針BCDEFG∧∧00000000000000中序線索鏈表的建立過程6.4二叉樹的存儲結構及實現(xiàn)中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre111111116.5樹、森林與二叉樹的轉換樹和二叉樹之間具有對應關系AEBCFDGA∧BC∧E∧D∧F∧∧G∧∧ABCDEFG6.5樹、森林與二叉樹的轉換樹和二叉樹之間的對應關系樹：兄弟關系二叉樹：雙親和右孩子樹：雙親和長子二叉樹：雙親和左孩子AEBCFDGABCDEFG1.兄弟加線.樹和二叉樹之間的對應關系ABCDEFG6.5.1樹、森林與二叉樹的轉換6.5.1樹、森林與二叉樹的轉換2.保留雙親與第一孩子連線,刪去與其他孩子的連線.ABCDEFG樹和二叉樹之間的對應關系1.兄弟加線.3.順時針轉動,使之層次分明.樹和二叉樹之間的對應關系2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.ABCDEFG6.5.1樹、森林與二叉樹的轉換3.順時針轉動,使之層次分明.樹和二叉樹之間的對應關系2.保留雙親與第一孩子連線,刪去與其他孩子的連線.1.兄弟加線.GDABECF6.5.1樹、森林與二叉樹的轉換CBEDFGAABEFCDG前序遍歷AEBCFDGABEFCDG前序遍歷樹的前序遍歷等價于二叉樹的前序遍歷！6.5.1樹、森林與二叉樹的轉換EFBCGDA后序遍歷EFBCGDA中序遍歷樹的后序遍歷等價于二叉樹的中序遍歷！CBEDFGAAEBCFDG6.5.1樹、森林與二叉樹的轉換森林轉換為二叉樹

⑴將森林中的每棵樹轉換成二叉樹；⑵從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連起來后，此時所得到的二叉樹就是由森林轉換得到的二叉樹。6.5.1樹、森林與二叉樹的轉換FEDCBAGHIJBAFEDCGHIJJIFEHABCGD6.5.1樹、森林與二叉樹的轉換FHGEAICDBFHGDCEBAIFEDCBAHGI加線去線層次調整IHGBCDAFE6.5.1樹、森林與二叉樹的轉換森林的遍歷森林有兩種遍歷方法：⑴前序（根）遍歷：前序遍歷森林即為前序遍歷森林中的每一棵樹。⑵后序（根）遍歷：后序遍歷森林即為后序遍歷森林中的每一棵樹。

6.5.1樹、森林與二叉樹的轉換雙親表示法基本思想：用一維數(shù)組來存儲樹的各個結點（一般按層序存儲），數(shù)組中的一個元素對應樹中的一個結點，包括結點的數(shù)據(jù)信息以及該結點的雙親在數(shù)組中的下標。

data

parentdata：存儲樹中結點的數(shù)據(jù)信息parent：存儲該結點的雙親在數(shù)組中的下標6.5.2樹的存儲結構structPNode{

datatypedata;//數(shù)據(jù)域intparent;//指針域，雙親在數(shù)組中的下標};

data

parent樹的雙親表示法實質上是一個靜態(tài)鏈表。雙親表示法6.5.2樹的存儲結構下標

dataparent012345678

A-1B0C0D1E1F1G2H2I

4如何查找雙親結點？時間性能？雙親表示法ACBHFEDGI6.5.2樹的存儲結構雙親表示法ACBHFEDGI如何查找孩子結點？時間性能？下標

dataparentfirstchild136-18-1-1-1-1012345678

A-1B0C0D1E1F1G2H2I

46.5.2樹的存儲結構下標

dataparentrightsib-12-145-17-1-1雙親表示法012345678

A-1B0C0D1E1F1G2H2I

4ACBHFEDGI如何查找兄弟結點？時間性能？6.5.2樹的存儲結構鏈表中的每個結點包括一個數(shù)據(jù)域和多個指針域，每個指針域指向該結點的一個孩子結點。如何確定鏈表中的結點結構？孩子鏈表表示法方案一：指針域的個數(shù)等于樹的度datachild1child2……childd其中：data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)信息；

child1~childd：指針域，指向該結點的孩子。

6.5.2樹的存儲結構∧缺點：浪費空間ACBHFEDGIAB∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧6.5.2樹的存儲結構鏈表中的每個結點包括一個數(shù)據(jù)域和多個指針域，每個指針域指向該結點的一個孩子結點。如何確定鏈表中的結點結構？孩子鏈表表示法方案二：指針域的個數(shù)等于該結點的度data

degree

child1

child2

……

childd其中：data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)信息；

degree：度域，存放該結點的度；

child1~childd：指針域，指向該結點的孩子。

6.5.2樹的存儲結構缺點：結點結構不一致ACBHFEDGIA2B3C2E1I0G0H0F0D06.5.2樹的存儲結構孩子鏈表表示法基本思想：把每個結點的孩子排列起來，看成是一個線性表，且以單鏈表存儲，則n個結點共有n個孩子鏈表。這n個單鏈表共有n個頭指針，這n個頭指針又組成了一個線性表，為了便于進行查找采用順序存儲。最后，將存放n個頭指針的數(shù)組和存放n個結點的數(shù)組結合起來，構成孩子鏈表的表頭數(shù)組。

如何確定鏈表中的結點結構？將結點的所有孩子放在一起，構成線性表。6.5.2樹的存儲結構childnext孩子結點structCTNode{

intchild;CTNode*next;};structCBNode{datatypedata;CTNode*firstchild;};孩子鏈表表示法datafirstchild表頭結點6.5.2樹的存儲結構ACBHFEDGI012345678下標

datafirstchild

ABCDEFG

H

I

∧∧∧∧如何查找孩子結點？時間性能？∧12∧345∧7∧68∧6.5.2樹的存儲結構ACBHFEDGI012345678下標

datafirstchild

ABCDEFG

H

I

∧∧∧∧∧12∧345∧7∧68∧如何查找雙親結點？時間性能？6.5.2樹的存儲結構雙親孩子表示法012345678

A-1B0C0D1∧

E1F1∧

G

2∧H

2∧I

4∧dataparentfirstchild12∧345∧7∧68∧ACBHFEDGI6.5.2樹的存儲結構孩子兄弟表示法ACBHFEDGI某結點的第一個孩子是惟一的某結點的右兄弟是惟一的設置兩個分別指向該結點的第一個孩子和右兄弟的指針

6.5.2樹的存儲結構structTNode{datatypedata;TNode<T>*firstchild,*rightsib;};結點結構firstchild

data

rightsibdata：數(shù)據(jù)域，存儲該結點的數(shù)據(jù)信息；firstchild：指針域，指向該結點第一個孩子；rightsib：指針域，指向該結點的右兄弟結點。

孩子兄弟表示法6.5.2樹的存儲結構孩子兄弟表示法ACBHFEDGI

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧如何查找兄弟結點？時間性能？6.5.2樹的存儲結構孩子兄弟表示法ACBHFEDGI

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧如何查找孩子結點？時間性能？6.5.2樹的存儲結構相關概念葉子結點的權值：葉子結點的一個有意義的數(shù)值。

二叉樹的帶權路徑長度：設二叉樹具有n個帶權值的葉子結點，從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和。記為：6.6哈夫曼樹及哈夫曼編碼WPL=?=nkkklw1第k個葉子的權值；從根結點到第k個葉子的路徑長度哈夫曼樹：給定一組具有確定權值的葉子結點，帶權路徑長度最小的二叉樹。例：給定4個葉子結點，其權值分別為{2，3，4，7}，可以構造出形狀不同的多個二叉樹。

6.6哈夫曼樹及哈夫曼編碼WPL=32WPL=41WPL=30234723477423哈夫曼樹的特點：1.權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。2.只有度為0（葉子結點）和度為2（分支結點）的結點，不存在度為1的結點.

6.6哈夫曼樹及哈夫曼編碼2347WPL=32WPL=41WPL=3023477423哈夫曼算法基本思想：⑴初始化：由給定的n個權值{w1，w2，…，wn}構造n棵只有一個根結點的二叉樹，從而得到一個二叉樹集合F＝{T1，T2，…，Tn}；⑵選取與合并：在F中選取根結點的權值最小的兩棵二叉樹分別作為左、右子樹構造一棵新的二叉樹，這棵新二叉樹的根結點的權值為其左、右子樹根結點的權值之和；⑶刪除與加入：在F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；

⑷

重復⑵、⑶兩步，當集合F中只剩下一棵二叉樹時，這棵二叉樹便是哈夫曼樹。

6.6哈夫曼樹及哈夫曼編碼第1步：初始化W＝{2，3，4，5}

哈夫曼樹的構造過程6.6哈夫曼樹及哈夫曼編碼3524第2步：選取與合并32

5第3步：刪除與加入5432

5W＝{2，3，4，5}

哈夫曼樹的構造過程6.6哈夫曼樹及哈夫曼編碼重復第2步5432

554

9重復第3步

554

932W＝{2，3，4，5}

哈夫曼樹的構造過程6.6哈夫曼樹及哈夫曼編碼重復第2步重復第3步

554

932

554

93214哈夫曼算法的存儲結構

1.設置一個數(shù)組huffTree[2n-1]保存哈夫曼樹中各點的信息，數(shù)組元素的結點結構。

weightlchildrchildparent其中：weight：權值域，保存該結點的權值；

lchild：指針域，結點的左孩子結點在數(shù)組中的下標；

rchild：指針域，結點的右孩子結點在數(shù)組中的下標；

parent：指針域，該結點的雙親結點在數(shù)組中的下標。structelement{intweight;intlchild,rchild,parent;};6.6哈夫曼樹及哈夫曼編碼偽代碼數(shù)組huffTree初始化，所有元素結點的雙親、左右孩子都置為-1；2.數(shù)組huffTree的前n個元素的權值置給定值w[n]；3.進行n-1次合并

3.1在二叉樹集合中選取兩個權值最小的根結點，其下標分別為i1,i2；

3.2將二叉樹i1、i2合并為一棵新的二叉樹k；6.6哈夫曼樹及哈夫曼編碼weightparentlchildrchild-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-10123456初態(tài)6.6哈夫曼樹及哈夫曼編碼352424532-1-1-14-1-1-15-1-1-13-1-1-1

-1-1-1

-1-1-1

-1-1-10123456過程6.6哈夫曼樹及哈夫曼編碼3524i1i2k503445432

5weightparentlchildrchild2

-1-1-14

-1-1-15-1-1-13

-1-1-1

-1-1-1

-1-1-1

-1-1-10123456過程6.6哈夫曼樹及哈夫曼編碼i1i2k503445432

591255

554

932weightparentlchildrchild2

-1-1-14

-1-1-15-1-1-1