4-1引言v第四章樹和二叉樹文件系統(tǒng)許多問題抽象出的數(shù)據模型具有層次關系例1

操作系統(tǒng)的文件目錄結構。表達式樹例2一個算術表達式可以用表達式樹來表示，并且具有以下兩個特點（1）葉子結點是操作數(shù)；（2）分支結點是運算符。后序遍歷轉換為后綴表達式（逆波蘭式）：abcd

-*+ef/-aefbcd-+/*-表達式：a+b*(c–d)–e/f隨處可見的樹結構例3

計算機系統(tǒng)中隨處可見的樹結構。例4

日常生活中隨處可見的樹結構。隨處可見的樹結構例4

日常生活中隨處可見的樹結構。吉林省市區(qū)街道朝陽南關二道高新寬城綠園雙陽九臺湖西桂林永昌紅旗清和……吉林長春四平通化遼源松原白城白山延邊隨處可見的樹結構知識樹思維導圖關于樹結構什么是樹？在邏輯上有什么特點？有哪些基本術語？如何存儲樹結構？什么是二叉樹？在邏輯上有什么特點？有哪些基本性質？如何存儲二叉樹？如何實現(xiàn)二叉樹的遍歷操作？最優(yōu)二叉樹及應用4-2樹的邏輯結構v第四章樹和二叉樹樹的定義和基本術語樹的抽象數(shù)據類型定義樹的遍歷操作學什么？4-2-1樹的定義和基本術語v第四章樹和二叉樹樹的定義樹：n（n≥0）個結點的有限集合數(shù)據元素樹的定義是采用遞歸方法，當n＝0時，稱為空樹；任意一棵非空樹T滿足以下條件：（1）有且僅有一個特定的稱為根的結點；（2）當n＞1時，除根結點之外的其余結點被分成m（m>0）個互不相交的有限集合T1,T2,…,Tm，其中每個集合又是一棵樹，并稱為這個根結點的子樹。ACBGFEDHIACBGFDACBGFDE互不相交的含義是什么？結點：結點不能屬于多個子樹邊：子樹之間不能有關系互不相交沒有回路樹的邏輯特征樹結構具有層次性樹的基本術語ACBGFEDHI樹的度：樹中各結點度的最大值結點的度：結點所擁有的子樹的個數(shù)分支結點：度不為0的結點，也稱為非終端結點葉子結點：度為0的結點，也稱為終端結點ACBGFEDHI雙親：這個結點稱為它孩子結點的雙親結點孩子：樹中某結點子樹的根結點稱為這個結點的孩子結點兄弟：具有同一個雙親的孩子結點互稱為兄弟a1ana2ai-1ai在線性結構中，邏輯關系表現(xiàn)為前驅——后繼在樹結構中，邏輯關系表現(xiàn)為雙親——孩子樹的基本術語ACBGFEDHI路徑：結點序列n1,n2,…,nk稱為一條由n1至nk的路徑，當且僅當滿足如下關系：結點ni是ni+1的雙親（1<=i<k）路徑長度：路徑上經過的邊的個數(shù)在樹結構中，路徑是唯一的祖先、子孫：如果有一條路徑從結點x到結點y，則x稱為y的祖先，而y稱為x的子孫樹的基本術語ACBGFEDHI結點所在層數(shù)：根結點的層數(shù)為1；對其余結點，若某結點在第k

層，則其孩子結點在第k+1層樹的深度（高度）：樹中所有結點的最大層數(shù)樹的寬度：樹中每一層結點個數(shù)的最大值深度=4寬度=4樹的基本術語線性結構和樹結構的比較開始結點（只有一個）：無前驅根結點（只有一個）：無雙親終端結點（只有一個）：無后繼葉子結點（可以多個）：無孩子其它元素：一個前驅，一個后繼其它結點：一個雙親，多個孩子一對一

一對多ACBGFEDHIa1ana2ai-1ai線性結構樹結構4-2-2樹的抽象數(shù)據類型定義v第四章樹和二叉樹樹的抽象數(shù)據類型定義樹的應用很廣泛，在不同的實際應用中，樹的基本操作不盡相同ADTTreeDataModel

樹由一個根結點和若干棵子樹構成，樹中結點具有層次關系OperationInitTree：初始化一棵樹

DestroyTree：銷毀一棵樹PreOrder：前序遍歷樹PostOrder：后序遍歷樹LevelOrder：層序遍歷樹endADT簡單起見，只討論樹的遍歷樹的遍歷什么是遍歷？線性結構如何遍歷？簡言之，遍歷是對數(shù)據集合進行沒有遺漏、沒有重復的訪問樹的遍歷：從根結點出發(fā)，按照某種次序訪問樹中所有結點，并且每個結點僅被訪問一次抽象操作，可以是對結點進行的各種處理，這里簡化為輸出結點的數(shù)據先序（根）、后序（根）和層序（次）等a1ana2ai樹的先序遍歷操作定義：若樹為空，則空操作返回；否則（1）訪問根結點（2）從左到右先序遍歷根結點的每一棵子樹先序：ABDEHIFCG樹的遍歷樹的后序遍歷操作定義：若樹為空，則空操作返回；否則（1）從左到右后序遍歷根結點的每一棵子樹（2）訪問根結點后序：DHIEFBGCAACBGFEDHI樹的層序遍歷操作定義：從樹的根結點開始，自上而下逐層遍歷，同一層從左到右對結點逐個訪問層序：ABCDEFGHI4-3樹的存儲結構v第四章樹和二叉樹思考問題的出發(fā)點：如何表示結點的雙親和孩子如何表示樹中結點之間的邏輯關系數(shù)據元素及其邏輯關系在存儲器中的表示實現(xiàn)樹的存儲結構，關鍵是什么?什么是存儲結構?樹中結點之間的邏輯關系是什么?CBGFEDHIA學什么？4-3-1樹的雙親表示法v第四章樹和二叉樹雙親表示法CBGFEDHIA樹的雙親表示法：用一維數(shù)組存儲樹中各個結點（一般按層序存儲）的數(shù)據信息以及該結點的雙親在數(shù)組中的下標012345678dataparent

ABCDEFGHI

-100111224如何定義樹的雙親表示法?template<typename

DataType>struct

PNode

{

DataTypedata;

intparent;};012345678

A-1B0C0D1E1F1G2H2I

4dataparent如何查找雙親結點？時間性能？O(1)如何查找孩子結點？時間性能？O(n)數(shù)據表示firstChild

136

-18-1-1-1-1雙親表示法CBGFEDHIA4-3-2樹的孩子表示法v第四章樹和二叉樹孩子表示法CBGFEDHIA如何表示結點的孩子呢？方案一：指針域的個數(shù)等于樹的度

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

child1~childd：指針域，指向該結點的孩子∧AB∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧缺點：浪費空間CBGFEDHIA方案二：指針域的個數(shù)等于該結點的度

datadegreechild1child2……childd其中：data：存放該結點的數(shù)據；degree：存放該結點的度；

child1~childd：指針域，指向該結點的孩子孩子表示法如何表示結點的孩子呢？A2B3C2E1I0G0H0F0D0缺點：結點結構不一致CBGFEDHIA方案三：將結點的所有孩子構成一個單鏈表12∧345∧7∧68∧∧∧∧∧∧firstChild

012345678

ABCDEFGHIdata孩子表示法如何表示結點的孩子呢？如何定義樹的孩子表示法呢？12∧345∧7∧68∧∧∧∧∧∧firstChild

012345678

ABCDEFGHIdatachildnext孩子結點datafirstChild表頭結點孩子表示法structChildNode//孩子結點{

intchild;ChildNode*next;};template<typenameDataType>structTreeNode//表頭結點{DataTypedata;ChildNode*firstChild;//指向孩子鏈表的頭指針};如何定義樹的孩子表示法呢？孩子表示法childnext孩子結點datafirstChild表頭結點ACBGFEDHI如何查找孩子結點？時間性能？O(1)12∧345∧7∧68∧∧∧∧∧∧firstchild

012345678

ABCDEFGHIdata孩子表示法ACBGFEDHI如何查找雙親結點？時間性能？O(n)12∧345∧7∧68∧∧∧∧∧∧firstchild

ABCDEFGHIdata012345678

ABCDEFGHIdata

parent-100111224孩子表示法4-3-3樹的孩子兄弟表示法v第四章樹和二叉樹孩子兄弟表示法CBGFEDHIA樹的孩子兄弟表示法（二叉鏈表）：鏈表中的每個結點包括數(shù)據域和分別指向該結點的第一個孩子和右兄弟的指針某結點的第一個孩子是惟一的某結點的右兄弟是惟一的設置兩個分別指向該結點的第一個孩子和右兄弟的指針CBGFEDHIA

B∧

D

C

F

I

G∧

H∧

E∧∧∧∧∧∧∧

A孩子兄弟表示法樹的孩子兄弟表示法（二叉鏈表）：鏈表中的每個結點包括數(shù)據域和分別指向該結點的第一個孩子和右兄弟的指針如何定義樹的孩子兄弟存儲結構?firstChilddata

rightSibtemplate<typenameDataType>structTNode{

DataTypedata;

TNode<DataType>*firstChild,*rightSib;};

孩子兄弟表示法

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧ACBGFEDHI

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧如何查找兄弟結點？時間性能？O(1)孩子兄弟表示法如何查找孩子結點？時間性能？O(n)已知該結點指針：O(1)4-4二叉樹的邏輯結構v第四章樹和二叉樹二叉樹的定義二叉樹的基本性質二叉樹的抽象數(shù)據類型定義學什么？二叉樹的構造二叉樹的遍歷操作4-4-1二叉樹的定義v第四章樹和二叉樹二叉樹的定義二叉樹：是n（n≥0）個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。二叉樹是度為2的樹嗎？AB二叉樹是度小于等于2的樹嗎？ABACBDEFGACBDEFG二叉樹有什么特點？（1）每個結點最多有兩棵子樹（2）二叉樹是有序的，其次序不能任意顛倒

為什么要研究二叉樹？（1）二叉樹是最簡單的樹結構（2）將樹轉換為二叉樹，

從而利用二叉樹解決樹的有關問題二叉樹的特點斜樹斜樹：左斜樹和右斜樹的統(tǒng)稱左斜樹：所有結點都只有左子樹的二叉樹ABD右斜樹：所有結點都只有右子樹的二叉樹ABD斜樹有什么特點呢？（1）每一層只有一個結點（2）結點個數(shù)與其深度相同斜樹是樹結構的特例，是從樹結構退化成了線性結構滿二叉樹滿二叉樹：所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層的二叉樹ABCDEFHIJKLMNOGABCDEFLMG所有分支結點都有左右子樹，但葉子不在同一層滿二叉樹有什么特點呢？（1）葉子只能出現(xiàn)在最下一層滿二叉樹是樹結構的特例，是最豐滿的二叉樹ABCDEFHIJKLMNOG（4）在同樣深度的二叉樹中葉子結點個數(shù)最多（2）只有度為0和度為2的結點（3）在同樣深度的二叉樹中結點個數(shù)最多滿二叉樹滿二叉樹：所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上的二叉樹L完全二叉樹完全二叉樹：在滿二叉樹中，從最后一個結點開始，連續(xù)去掉任意個結點得到的二叉樹ABCDEFHIJKMNOGABCDEFHIJKMG完全二叉樹有什么特點呢？（1）葉子結點只能出現(xiàn)在最下兩層且最下層的葉子結點都集中在二叉樹的左面ABCDEFHIJG（3）深度為k

的完全二叉樹在

k-1層上一定是滿二叉樹（2）完全二叉樹中如果有度為1的結點，只可能有一個，且該結點只有左孩子（4）在同樣結點個數(shù)的二叉樹中，完全二叉樹的深度最小完全二叉樹完全二叉樹：在滿二叉樹中，從最后一個結點開始，連續(xù)去掉任意個結點得到的二叉樹4-4-2二叉樹的基本性質v第四章樹和二叉樹二叉樹的性質性質5-1：在一棵二叉樹中，如果葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則有:n0＝n2＋1ACBE證明:設n為二叉樹的結點總數(shù)，n1為二叉樹中度為1的結點數(shù)，則有：

n＝n0＋n1＋n2

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

n＝n1＋2n2＋1兩式聯(lián)立，可以得到：

n0＝n2＋1性質5-2：二叉樹的第

i

層上最多有2i-1個結點（i≥1）證明：采用歸納法證明。當

i=1時，只有一個根結點，而2i-1=20=1，結論成立。假設

i=k時結論成立，即第

k層上最多有2k-1個結點。考慮

i=k+1時的情形。由于第

k+1層上的結點是第

k層上結點的孩子，而二叉樹中每個結點最多有兩個孩子，故在第

k+1層上的最多大結點個數(shù)有2×2k-1＝2k個結點，則在

i=k+1時結論也成立。由此，結論成立。二叉樹的性質性質5-3：一棵深度為k

的二叉樹中，最多有2k-1個結點證明：設深度為k的二叉樹中結點個數(shù)最多為n，則深度為k且具有2k-1個結點的二叉樹一定是滿二叉樹二叉樹的性質證明：設具有n

個結點的完全二叉樹的深度為k，則2k-1-12k-1…2k-1第k層…第k-1層對不等式取對數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1二叉樹的性質性質5-4：具有n個結點的完全二叉樹的深度為log2n+1。由于k

是整數(shù)，故必有

k＝log2n+1性質5-5：對一棵具有n

個結點的完全二叉樹中從1開始按層序編號，對于編號為i（1≤i≤n）的結點（簡稱結點i），有：（1）如果i＞1，則結點i

的雙親結點的編號為i/2，否則結點i

無雙親結點（2）如果2i≤n，則結點i

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

無左孩子（3）如果2i+1≤n，則結點i

的右孩子的編號為2i+1，否則結點i

無右孩子12345689107二叉樹的性質4-4-3二叉樹的抽象數(shù)據類型定義v第四章樹和二叉樹二叉樹的抽象數(shù)據類型定義ADTBiTreeDataModel

二叉樹由一個根結點和兩棵互不相交的左右子樹構成，結點具有層次關系OperationInitBiTree：初始化一棵空的二叉樹

CreateBiTree：建立一棵二叉樹

DestroyBiTree：銷毀一棵二叉樹PreOrder：前序遍歷二叉樹InOrder：中序遍歷二叉樹PostOrder：后序遍歷二叉樹LevelOrder：層序遍歷二叉樹endADT簡單起見，只討論二叉樹的遍歷二叉樹的遍歷二叉樹的遍歷：從根結點出發(fā)，按照某種次序訪問樹中所有結點，并且每個結點僅被訪問一次抽象操作，可以是對結點進行的各種處理，這里簡化為輸出結點的數(shù)據限定先左后右：先序、中序、后序根結點D左子樹L右子樹R二叉樹按照什么次序對二叉樹進行遍歷呢？二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD

層序遍歷：按二叉樹的層序編號的次序訪問各結點二叉樹的先序遍歷操作定義：若二叉樹為空，則空操作返回；否則：（1）訪問根結點（2）先序遍歷根結點的左子樹（3）先序遍歷根結點的右子樹ACBDEFG先序：ABDGCEF二叉樹的遍歷二叉樹的中序遍歷操作定義：若二叉樹為空，則空操作返回；否則：（1）中序遍歷根結點的左子樹（2）訪問根結點（3）中序遍歷根結點的右子樹中序：DGBAECF二叉樹的后序遍歷操作定義：若二叉樹為空，則空操作返回；否則：（1）后序遍歷根結點的左子樹（2）后序遍歷根結點的右子樹（3）訪問根結點ACBDEFG后序：GDBEFCA二叉樹的遍歷層序：ABCDEFG二叉樹的層序遍歷操作定義：從二叉樹的根結點開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問若已知一棵二叉樹的先序（或中序，或后序，或層序）序列，能否唯一確定這棵二叉樹呢？ABCABC先序遍歷序列：ABC若已知一棵二叉樹的先序序列和后序序列，能否唯一確定這棵二叉樹呢？后序遍歷序列：CBA二叉樹的構造先序：ABCDEFG

HI中序：BCA

EDGHFIADEFG

HIBC先序：BC中序：BC先序：DEFGHI中序：EDGHFIDEFGHIABC二叉樹的構造例4-1已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABCDEFGH和CDBAFEHG，請確定該二叉樹。先序：FG

HI中序：GHFIADEBCFGIH層序：

ABCDEFGHI中序：

DBGEHACIFACIFDBGEHCAB二叉樹的構造例4-2已知一棵二叉樹的層序遍歷序列和中序遍歷序列分別為ABCDEFGHI和DBGEHACIF，請構造該二叉樹。層序：

A

B

CDEFGHI中序：

DBGEHA

CIFGEHDIFCABDEGHFI4-5二叉樹的存儲結構v第四章樹和二叉樹二叉樹的順序存儲結構二叉鏈表三叉鏈表學什么？4-5-1二叉樹的順序存儲結構v第四章樹和二叉樹二叉樹的順序存儲結構順序存儲結構的要求是什么？用一組連續(xù)的存儲單元依次存儲數(shù)據元素，由存儲位置表示元素之間的邏輯關系如何利用數(shù)組下標來反映結點之間的邏輯關系?完全二叉樹中結點的編號可以唯一地反映結點之間的邏輯關系二叉樹的順序存儲結構是用一維數(shù)組存儲二叉樹的結點，結點的存儲位置（下標）應能體現(xiàn)結點之間的邏輯關系——父子關系ABCDEFHIJ編號為下標

A12345678910

B

C

D

E

F

G

H

I

JconstMaxSize=100;template<typenameDataType>structSeqBiTree{

DataTypedata[MaxSize];intbiTreeNum;};如何定義二叉樹的順序存儲結構呢？二叉樹的順序存儲結構如果從下標0開始存儲，如何表示邏輯關系？ABCDFEG152361310以編號為下標

A12345678910111213

B

C∧

D

F∧

∧

∧

E

∧

∧

G將二叉樹按完全二叉樹編號：（1）根結點的編號為1（2）若某結點

i有左孩子，則其左孩子的編號為2i（3）若某結點

i有右孩子，則其右孩子的編號為2i+1對于普通的二叉樹，如何順序存儲呢？二叉樹的順序存儲結構二叉樹的順序存儲結構一般僅存儲完全二叉樹順序存儲一棵右斜樹會發(fā)生什么情況？ACOG缺點：浪費存儲空間二叉樹的順序存儲結構4-5-2二叉鏈表v第四章樹和二叉樹如何用鏈接存儲方式存儲二叉樹呢？firsta1a2an∧二叉鏈表：二叉樹的每個結點對應一個鏈表結點，存放結點的數(shù)據信息和指示左右孩子的指針二叉鏈表的存儲方法lchild

datarchildACBDEFGACBDEFGGFEDB∧∧∧∧∧∧∧∧CAroot二叉鏈表的存儲方法葉子結點的標志？左右孩子指針均為空二叉鏈表的存儲結構定義GFEDBA∧∧∧∧∧∧∧∧Ctemplate<typenameDataType>structBiNode{

DataTypedata;BiNode<DataType>*lchild,*rchild;};root如何定義二叉鏈表的結點呢？n個結點的二叉鏈表有多少個空指針？2n-(n-1)=n+1個空指針三叉鏈表的存儲方法GFEDBA∧∧∧∧∧∧∧∧C如何查找雙親？時間性能？O(n)在二叉鏈表中增加一個指向雙親的指針域

lchild

dataparentrchildrootA∧B∧D∧E∧F∧CG∧∧∧∧ACBDEFGroot三叉鏈表的存儲方法二叉鏈表的類定義二叉樹的抽象數(shù)據類型定義？template<typenameDataType>classBiTree{public:

BiTree(){root=CreateBiTree(root);}

~BiTree(){ReleaseBiTree(root);}

voidPreOrder(){PreOrder(root);}

voidInOrder(){InOrder(root);}

voidPostOrder(){PostOrder(root);}

voidLevelOrder();private:

BiNode<DataType>*CreateBiTree(BiNode<DataType>*bt);

voidReleaseBiTree(BiNode<DataType>*bt);

voidPreOrder(BiNode<DataType>*bt);

voidInOrder(BiNode<DataType>*bt);

voidPostOrder(BiNode<DataType>*bt);

BiNode<DataType>*root;};InitBiTree：初始化一棵空的二叉樹

CreateBiTree：建立一棵二叉樹

DestroyBiTree：銷毀一棵二叉樹PreOrder：前序遍歷二叉樹InOrder：中序遍歷二叉樹PostOrder：后序遍歷二叉樹LevelOrder：層序遍歷二叉樹先序遍歷算法template<typenameDataType>voidBiTree<DataType>::PreOrder(BiNode<DataType>*bt){

if(bt==nullptr)return;

//遞歸調用的結束條件

else{

cout<<bt->data;

//訪問根結點bt的數(shù)據域

PreOrder(bt->lchild);

//先序遞歸遍歷bt的左子樹

PreOrder(bt->rchild);

//先序遞歸遍歷bt的右子樹

}}按照先左后右的方式掃描二叉樹，區(qū)別僅在于訪問結點的時機LRACBDPre(*A)

（1）APre(A->lchild);

Pre(*B)

（2）BPre(B->lchild);

Pre(∧)Pre(*D)

（3）DPre(D->lchild);

Pre(∧)Pre(∧)Pre(B->rchild);Pre(D->rchild);約定：*A表示根指針指向結點Aif(bt==nullptr)return;else{

①

cout<<bt->data;

②

PreOrder(bt->lchild);

③

PreOrder(bt->rchild);}先序遍歷算法ACBDPre(*A)

（1）APre(A->lchild);

Pre(*B)

（2）BPre(B->lchild);

Pre(∧)Pre(*D)

（3）DPre(D->lchild);

Pre(∧)Pre(∧)Pre(B->rchild);Pre(D->rchild);Pre(∧)Pre(∧)Pre(*C)

（4）CPre(C->lchild);

Pre(A->rchild);Pre(C->rchild);得到先序遍歷序列：ABDCif(bt==nullptr)return;else{

①

cout<<bt->data;

②

PreOrder(bt->lchild);

③

PreOrder(bt->rchild);}先序遍歷算法遍歷序列：AABCBDCEFGDEFGACBDEFG隊列Q初始化；2.如果二叉樹非空，將根指針入隊；入隊出隊3.3若結點q存在左孩子，則將左孩子指針入隊；3.4若結點q存在右孩子，則將右孩子指針入隊；3.循環(huán)直到隊列Q為空3.1q=隊列Q的隊頭元素出隊；3.2訪問結點q的數(shù)據域；

層序遍歷算法template<typenameDataType>voidBiTree<DataType>::LevelOrder(){

BiNode<DataType>*Q[100],*q=nullptr;

intfront=-1,rear=-1;

if(root==nullptr)return;

Q[++rear]=root;

while(front!=rear)

{

q=Q[++front];cout<<q->data;

if(q->lchild!=nullptr)Q[++rear]=q->lchild;

if(q->rchild!=nullptr)Q[++rear]=q->rchild;

}}時間復雜度？每個結點進隊一次出隊一次O(n)O(n)層序遍歷算法遍歷是二叉樹各種操作的基礎，可以在遍歷的過程中建立一棵二叉鏈表在內存中建立一棵二叉鏈表，如何輸入二叉樹的信息？構造二叉鏈表如何由一種遍歷序列生成該二叉樹？擴展二叉樹：將每個結點的空指針引出一個虛結點，其值為一特定值如'#'ACBD先序：AB#D##C##ACBD#####template<typename

DataType>BiNode<DataType>*BiTree<DataType>::CreateBiTree(BiNode<DataType>*bt){

charch;

cin>>ch;

//輸入結點的數(shù)據信息，假設為字符

if(ch==‘#’)bt=nullptr;

//建立一棵空樹

else{

bt=newBiNode<DataType>;

bt->data=ch;

bt->lchild

=CreateBiTree(bt->lchild);//遞歸建立左子樹

bt->rchild

=CreateBiTree(bt->rchild);//遞歸建立右子樹

}

returnbt;}構造二叉鏈表銷毀二叉鏈表為什么要銷毀內存中的二叉鏈表？二叉鏈表是動態(tài)存儲分配，二叉鏈表的結點是在程序運行過程中動態(tài)申請的，在二叉鏈表變量退出作用域前，要釋放二叉鏈表的存儲空間template<typenameDataType>voidBiTree<DataType>::ReleaseBiTree(BiNode<DataType>*bt){

if(bt==nullptr)return;

else{

ReleaseBiTree(bt->lchild);

//釋放左子樹

ReleaseBiTree(bt->rchild);

//釋放右子樹

deletebt;

//釋放根結點

}}4-6森林v第四章樹和二叉樹森林的邏輯結構樹、森林與二叉樹的轉換學什么？4-6-1森林的邏輯結構v第四章樹和二叉樹CBGFEDHIEHIA對于樹：刪去根結點就變成了森林對于森林：增加一個根結點，將森林中的每一棵樹作為這個根結點的子樹，則森林就變成了一棵樹森林的定義森林：m（m≥0）棵互不相交的樹的集合森林的遍歷ABCEFDGJIH第3棵是度為2的樹還是二叉樹？森林的遍歷：按照某種次序依次遍歷構成森林的m（m≥0）棵樹先序（根）、后序（根）先序：ABCDEFGHIJ后序：BADEFCHJIG4-6-2樹、森林與二叉樹的轉換v第四章樹和二叉樹樹與二叉樹的對應關系A∧BC∧E∧D∧F∧∧G∧∧CBFEDGAACBEGDF

A

B

D

E

F

G∧∧∧∧∧∧

C∧Page02邏輯關系有什么變化?

樹：兄弟關系二叉樹：雙親和右孩子

樹：雙親和長子二叉樹：雙親和左孩子CBFEDGAACBEGDF樹與二叉樹的對應關系樹轉換為二叉樹CBFEDGA將一棵樹轉換為二叉樹的方法是：（1）加線——樹中所有相鄰兄弟之間加一條連線（2）去線——對樹中的每個結點，只保留它與第一個孩子結點之間的連線，刪去它與其它孩子結點之間的連線。（3）層次調整——以根結點為軸心，將樹順時針轉動一定的角度，使之層次分明。ACBEGDF樹的先序遍歷等價于二叉樹的先序遍歷！樹的后序遍歷等價于二叉樹的中序遍歷！樹轉換為二叉樹CBFEDGAACBEGDF二叉樹根結點的右子樹為空樹的根結點沒有兄弟樹的先序和后序遍歷序列？二叉樹的先序和中序遍歷序列？森林轉換為二叉樹（1）將森林中的每棵樹轉換為二叉樹（2）將每棵樹的根結點視為兄弟，在所有根結點之間加上連線（3）按照二叉樹結點之間的關系進行層次調整將一個森林轉換為二叉樹的方法是ABCEFDGJIHABCEFDGJIHABCDEFGJIHABCDEFGJIH森林轉換為二叉樹二叉樹轉換為樹（森林）將一棵二叉樹還原為樹或森林，具體轉換方法是（1）加線——若某結點x

是其雙親y

的左孩子，則把結點x

的右孩子、右孩子的右孩子、……，與結點y

連線（2）去線——刪去所有雙親結點與右孩子結點的連線（3）層次調整——整理由（1）、（2）兩步所得到的樹（森林），使之層次分明。ACBEGDFCBFEDGA4-7最優(yōu)二叉樹v第四章樹和二叉樹哈夫曼算法學什么？哈夫曼編碼最優(yōu)二叉樹（哈夫曼樹）的基本概念最優(yōu)二叉樹葉子結點的權值：對葉子結點賦予的一個有意義的數(shù)值量二叉樹的帶權路徑長度：從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和取決于具體問題第k個葉子的權值從根結點到第k個葉子的路徑長度最優(yōu)二叉樹（哈夫曼樹）：給定一組具有確定權值的葉子結點，帶權路徑長度最小的二叉樹323428324552345432最優(yōu)二叉樹最優(yōu)二叉樹有什么特點?（1）權值越大的葉子結點越靠近根結點（2）只有度為0和度為2的結點，不存在度為1的結點4-7-1哈夫曼算法v第四章樹和二叉樹哈夫曼算法【問題】給定一組權值，構造最優(yōu)二叉樹1.初始化：由n個權值構造n棵只有一個根結點的二叉樹，得到一個二叉樹集合F＝{T1，T2，…，Tn}；2.重復下述操作，直到集合F中只剩下一棵二叉樹

2.1選取與合并：在F中選取根結點的權值最小的兩棵二叉樹分別作為左右子樹構造一棵新的二叉樹，這棵新二叉樹的根結點的權值為其左右子樹根結點的權值之和；

2.2刪除與加入：在F中刪除作為左右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；【想法——哈夫曼算法的基本思想】例給定權值集合{2，4，5，3}初始化選取與合并刪除與加入245323

54523

5運行實例23

545

923

545

914【算法——數(shù)據表示】如何存儲哈夫曼樹呢？23

545

914采用數(shù)組還是鏈表呢？

n

個葉子結點合并

n-1次n-1個分支結點哈夫曼樹共有2n-1個結點設數(shù)組huffTree[2n-1]須存儲哪些關系呢？選取根結點權值最小的二叉樹存儲parent信息作為左右子樹進行合并存儲lchild和rchild信息weightlchildrchildparent哈夫曼算法23

545

914weightlchildrchildparentstructElemType{

intweight;/*假定權值為整數(shù)*/

intparent,lchild,rchild;};函數(shù)原型：voidHuffmanTree(ElemTypehuffTree[],intw[],intn)哈夫曼算法【算法——數(shù)據表示】如何存儲哈夫曼樹呢？【算法——數(shù)據處理過程】-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1例給定權值集合{2，4，5，3}24530123456weightparentlchildrchildfor(i=0;i<2*n-1;i++){huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}算法描述：哈夫曼算法-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-124530123456weightparentlchildrchildfor(i=0;i<n;i++)huffTree[i].weight=w[i];算法描述：例給定權值集合{2，4，5，3}哈夫曼算法【算法——數(shù)據處理過程】2453-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-124530123456weightparentlchildrchild4523

5i1i25huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;算法描述：k例給定權值集合{2，4，5，3}哈夫曼算法【算法——數(shù)據處理過程】2453-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-