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

《數(shù)據(jù)結(jié)構(gòu)與算法》

廊坊師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院第五章二叉樹★★★★★樹型結(jié)構(gòu)--實(shí)例:五子棋DEFBCA…...........…...........第五章二叉樹本章重點(diǎn)難點(diǎn)

重點(diǎn)：二叉樹的定義，性質(zhì)，存儲(chǔ)結(jié)構(gòu)以及相關(guān)的應(yīng)用——遍歷，二叉搜索樹，堆優(yōu)先隊(duì)列，Huffman樹等

難點(diǎn)：二叉樹的遍歷算法及相關(guān)應(yīng)用5.1二叉樹的概念●二叉樹遞歸定義：

由n(n>=0)個(gè)結(jié)點(diǎn)的有限集合，或?yàn)榭占?，或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。●二叉樹的五種基本形態(tài)：空僅有根右子樹為空左子樹為空左右均非空5.1二叉樹的概念

相關(guān)概念根：二叉樹中唯一的起始結(jié)點(diǎn)父結(jié)點(diǎn)：非根結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)孩子結(jié)點(diǎn)：二叉樹中，任何結(jié)點(diǎn)的后繼結(jié)點(diǎn)（左孩子，右孩子）兄弟結(jié)點(diǎn)：父結(jié)點(diǎn)相同的結(jié)點(diǎn)葉子結(jié)點(diǎn)：沒有子結(jié)點(diǎn)的結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)：除葉子結(jié)點(diǎn)以外的非終端結(jié)點(diǎn)BDFEGCAABDFEGCA根BDA5.1二叉樹的概念

相關(guān)概念

度：一個(gè)結(jié)點(diǎn)的子樹數(shù)目

邊：父結(jié)點(diǎn)結(jié)點(diǎn)和子結(jié)點(diǎn)之間的連線

路徑：從一個(gè)結(jié)點(diǎn)到另外一個(gè)結(jié)點(diǎn)的邊的集合，邊的個(gè)數(shù)稱為路徑的長度

層數(shù)：從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑長度稱為結(jié)點(diǎn)的層數(shù)BDFEGCA二叉樹的度最多為20層1層2層3層5.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹BDFEGCA

滿二叉樹：所有層數(shù)的結(jié)點(diǎn)都達(dá)到最大值的二叉樹（與書中不同）1231145891213671014155.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹BDFEGCA

滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)

1231145891213671014155.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹

完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1--n的結(jié)點(diǎn)一一對應(yīng)1234567滿二叉樹12345完全二叉樹5.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹

完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1--n的結(jié)點(diǎn)一一對應(yīng)1234567滿二叉樹12345完全二叉樹5.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹12345完全二叉樹

完全二叉樹特點(diǎn)：

只有最下面兩層的結(jié)點(diǎn)度數(shù)小于2

最下面一層的結(jié)點(diǎn)都集中在該層最左邊連續(xù)的位置上5.1二叉樹的概念

第三種特殊的二叉樹---正則二叉樹正則二叉樹

正則二叉樹：若二叉樹的所有結(jié)點(diǎn)，或者是樹葉，或者左右子樹均非空，即除了葉子結(jié)點(diǎn)就是度為2的結(jié)點(diǎn)12345675.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)1：二叉樹中第i層上最多有2i個(gè)結(jié)點(diǎn)0層1層2層BDFEGCA3層HGJILKNM數(shù)學(xué)歸納法證明：1.當(dāng)i=0時(shí)：成立2.假設(shè)所有的j(0<j<i)層都成立3.j=i時(shí)也成立i-1層:2i-1i層：2×2i-1

=

2i

5.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)2：深度為k的二叉樹，至多有2k+1-1個(gè)結(jié)點(diǎn)深度：二叉樹中層數(shù)最大的葉結(jié)點(diǎn)的層數(shù)0層1層2層BDFEGCA3層HGJILKNM1+2+4+8+…..2k等比數(shù)列的求和公式：

a1-an*q1-2k*21-q1-22k+1-1==證明：由性質(zhì)1可知：第i層的最大結(jié)點(diǎn)數(shù)為2i，因此：

∑2i=2k+1-1ki=05.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)3：任何一棵二叉樹，若其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1BDFGCAG證明：(1)總結(jié)點(diǎn)數(shù)為

n=n0+n1+n2(2)除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)邊e進(jìn)入

n=e+1(3)邊e又是由度為1或2的點(diǎn)射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)3：任何一棵二叉樹，若其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1BDFGCAG證明：(1)總結(jié)點(diǎn)數(shù)為

n=n0+n1+n2(2)除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)邊e進(jìn)入

n=e+1(3)邊e又是由度為1或2的點(diǎn)射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)3：任何一棵二叉樹，若其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1BDFGCAG證明：(1)總結(jié)點(diǎn)數(shù)為

n=n0+n1+n2(2)除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)邊e進(jìn)入

n=e+1(3)邊e又是由度為1或2的點(diǎn)射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)3：任何一棵二叉樹，若其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1BDFGCAG證明：(1)總結(jié)點(diǎn)數(shù)為

n=n0+n1+n2(2)除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)邊e進(jìn)入

n=e+1(3)邊e又是由度為1或2的點(diǎn)射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)3：任何一棵二叉樹，若其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1BDFGCAG證明：(1)總結(jié)點(diǎn)數(shù)為

n=n0+n1+n2(2)除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)邊e進(jìn)入

n=e+1(3)邊e又是由度為1或2的點(diǎn)射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)4：正則二叉樹定理：非空正則二叉樹樹葉數(shù)目等于其分支結(jié)點(diǎn)數(shù)加1證明：可由性質(zhì)3直接推出性質(zhì)3：n0=n2+1BDFEGCA5.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)5：正則二叉樹定理推論：一個(gè)非空二叉樹的空子樹數(shù)目等于其結(jié)點(diǎn)數(shù)加1證明：由性質(zhì)4可推出BDGCAFE5.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)6：有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的高度為「log2(n+1),深度為「log2(n+1)-1

高度:二叉樹中最大葉結(jié)點(diǎn)的層數(shù)+1123450層1層2層高度=3,深度=2證明：由性質(zhì)2（深度為k的二叉樹，至多有2k+1-1個(gè)結(jié)點(diǎn)）可知，高度為h(k+1)的二叉樹，其結(jié)點(diǎn)個(gè)數(shù)n滿足：

2h-1-1<n<=2h-12h-1<n+1<=2h取對數(shù)得到：

h-1<log2(n+1)<=h因?yàn)閔是整數(shù)，所以

h=log2(n+1)

上取整：大于該數(shù)的最小整數(shù)3.4->45.1二叉樹的概念●二叉樹的主要性質(zhì)

●性質(zhì)7：具有n個(gè)結(jié)點(diǎn)的完全二叉樹，結(jié)點(diǎn)按層次由左到右編號(hào)，則對任一結(jié)點(diǎn)i（0<=i<=n-1)有：（2）2i+1<=n-1i的左孩子結(jié)點(diǎn)是2i+12i+2<=n-1i的右孩子結(jié)點(diǎn)是2i+2（1）i=0i是根結(jié)點(diǎn)

i>0其父結(jié)點(diǎn)=（i-1）/2（3）0<i<ni為偶數(shù)時(shí)，其左兄弟結(jié)點(diǎn)是i-1i+1<ni為奇數(shù)時(shí)，其右兄弟結(jié)點(diǎn)是i+101234562k-22i+22k-1i

2k+1-12k+12i+32i+4i+12k+1-22i+12k+2-32k+2-2K-1層K層K+1層………..………..………..………..5.2二叉樹的遍歷（周游）●二叉樹遍歷：

按照一定的順序依次訪問樹中的所有結(jié)點(diǎn)，并使得每個(gè)結(jié)點(diǎn)僅被訪問一次。

遍歷的目的：初始化一棵二叉樹在樹中查找具有某種特征的結(jié)點(diǎn)對樹中全部結(jié)點(diǎn)逐一進(jìn)行某種處理。5.2二叉樹的遍歷（周游）遍歷分類：深度優(yōu)先：盡可能沿分支結(jié)點(diǎn)向深度方向遍歷廣度優(yōu)先：按二叉樹的層次進(jìn)行遍歷

BDFGCAGTLR—先（根）序遍歷，LTR—中（根）序遍歷，LRT—后（根）序遍歷。尋找遍歷二叉樹的規(guī)律二叉樹基本組成單元：根結(jié)點(diǎn)T、左子樹Ｌ和右子樹Ｒ。遍歷二叉樹有TLR、LTR、LRT、TRL、RTL、RLT六種方案。規(guī)定先左后右，則只有三種：T左子樹右子樹根結(jié)點(diǎn)5.2二叉樹的遍歷（周游）深度優(yōu)先遍歷：DLR—先（根）序遍歷5.2二叉樹的遍歷（周游）深度優(yōu)先遍歷：

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

（2）先序遍歷左子樹；

（3）

先序遍歷右子樹；ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B第五章二叉樹內(nèi)容回顧二叉樹的概念空僅有根右子樹為空左子樹為空左右均非空二叉樹的性質(zhì)滿二叉樹，完全二叉樹，正則二叉樹0256134滿二叉樹完全二叉樹0213正則二叉樹02341第五章二叉樹內(nèi)容回顧二叉樹的概念二叉樹的性質(zhì)滿二叉樹，完全二叉樹，正則二叉樹012103478111256913140層1層2層3層2i2i+1-1n0=n2+1....「log2(n+1)2i+1;2i+2第五章二叉樹內(nèi)容回顧二叉樹的概念二叉樹的性質(zhì)滿二叉樹，完全二叉樹，正則二叉樹二叉樹的遍歷深度優(yōu)先廣度優(yōu)先BDFGCAG根二叉樹的深度優(yōu)先遍歷根：root左子樹：left右子樹：rightTLRTLR—先（根）序遍歷LTR—中（根）序遍歷LRT—后（根）序遍歷規(guī)定遍歷順序自左至右：創(chuàng)建、復(fù)制一棵二叉樹遍歷一棵二叉搜索樹可以得到有序序列求樹的高度，葉結(jié)點(diǎn)的數(shù)量BDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習(xí)ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBA5.2二叉樹的遍歷（周游）廣度優(yōu)先遍歷：BDFEGCA廣度優(yōu)先遍歷序列：

ABCDEFG內(nèi)存使用模擬：1.不同任務(wù)的數(shù)據(jù)申請使用內(nèi)存2.部分程序結(jié)束，此時(shí)內(nèi)存可用空間已經(jīng)呈不連續(xù)狀態(tài)5.3二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)：連續(xù)存儲(chǔ)：占用一片連續(xù)的存儲(chǔ)區(qū)域優(yōu)點(diǎn)：隨機(jī)讀取，存儲(chǔ)密度大缺點(diǎn)：插入和刪除元素費(fèi)時(shí)，不適合存儲(chǔ)數(shù)據(jù)量無法預(yù)知的數(shù)據(jù)5.3二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)：連續(xù)存儲(chǔ)：占用一片連續(xù)的存儲(chǔ)區(qū)域優(yōu)點(diǎn)：隨機(jī)讀取，存儲(chǔ)密度大缺點(diǎn)：插入和刪除元素費(fèi)時(shí)，不適合存儲(chǔ)數(shù)據(jù)量無法預(yù)知的數(shù)據(jù)5.3二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)：連續(xù)存儲(chǔ)：占用一片連續(xù)的存儲(chǔ)區(qū)域優(yōu)點(diǎn)：隨機(jī)讀取，存儲(chǔ)密度大缺點(diǎn)：插入和刪除元素費(fèi)時(shí)，不適合存儲(chǔ)數(shù)據(jù)量無法預(yù)知的數(shù)據(jù)5.3二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)：

鏈?zhǔn)酱鎯?chǔ)：使用不連續(xù)的存儲(chǔ)區(qū)域，使用附加的指針信息，體現(xiàn)其邏輯關(guān)系優(yōu)點(diǎn)：適于動(dòng)態(tài)變化的數(shù)據(jù)結(jié)構(gòu)缺點(diǎn)：隨機(jī)查找困難，存儲(chǔ)密度小5.3二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)域指針域數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)：

鏈?zhǔn)酱鎯?chǔ)：使用不連續(xù)的存儲(chǔ)區(qū)域，使用附加的指針信息，體現(xiàn)其邏輯關(guān)系優(yōu)點(diǎn)：適于動(dòng)態(tài)變化的數(shù)據(jù)結(jié)構(gòu)缺點(diǎn)：隨機(jī)查找困難，存儲(chǔ)密度小5.3二叉樹的存儲(chǔ)結(jié)構(gòu)5.3二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)：

用一組地址連續(xù)的存儲(chǔ)單元，依次按滿二叉樹的結(jié)點(diǎn)編號(hào)位序，存儲(chǔ)二叉樹的結(jié)點(diǎn)。特點(diǎn)：適用于完全二叉樹。否則可能對存儲(chǔ)空間造成極大的浪費(fèi)，比如單支樹。abcdefg5.3二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：完全二叉樹0a1b2c3d4e5f6g1234560順序方式是完全二叉樹存儲(chǔ)的最簡單，最節(jié)省空間的方式abcdefg5.3二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：非完全二叉樹abcgg‘/’‘/’‘/’cba1234560非完全二叉樹順序存儲(chǔ)時(shí)，會(huì)浪費(fèi)一定的空間3’/’4’/’5’/’0a1b2c6g5.3二叉樹的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉鏈表：從任何一個(gè)結(jié)點(diǎn)都可找到其左右孩子結(jié)點(diǎn)lChilddata0rChildlChilddata1rChildlChilddata2rChildRoot缺點(diǎn)：很難獲取某個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)5.3二叉樹的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：三叉鏈表：從任何一個(gè)結(jié)點(diǎn)都可找到其父結(jié)點(diǎn)和左右孩子結(jié)點(diǎn)lChildparentdatarChildlChildparentdatarChildlChildparentdatarChildnullRoot5.3二叉樹的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的程序?qū)崿F(xiàn)：結(jié)點(diǎn)類定義：//樹結(jié)點(diǎn)類的定義template<classT>classTreeNode{public：

Tdata;TreeNode*lchild;//左，右子樹

TreeNode*rchild;public:TreeNode(){ lchild=NULL; rchild=NULL;}};lChilddata0rChild5.3二叉樹的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的程序?qū)崿F(xiàn)：二叉樹類定義：//樹類的定義template<classT>classBinTree{private: TreeNode<T>*root;//樹的根結(jié)點(diǎn)public: BinTree() { root=NULL; } ~BinTree() { Destroy(root); }rootnull5.3二叉樹的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的程序?qū)崿F(xiàn)：二叉樹類定義：//樹類的定義template<classT>classBinTree{private: TreeNode<T>*root;//樹的根結(jié)點(diǎn)public: BinTree() { root=NULL; } ~BinTree() { Destroy(root); }BDCAroot//***************創(chuàng)建二叉樹,主過程

voidCreatTree(){

cout<<"請按前序遍歷輸入結(jié)點(diǎn)元素值，空節(jié)點(diǎn)用/代替:"<<endl; CreatTree(root);}//***************創(chuàng)建二叉樹,子過程voidCreatTree(TreeNode<T>*&p1){Tc; cin>>c; TreeNode<T>*point;point=newTreeNode<T>; if(c!='/') { p1=point;point->data=c;CreatTree(point->lchild);CreatTree(point->rchild); }}創(chuàng)建二叉樹BDCAroot‘/’‘/’‘/’‘/’‘/’

//先序遍歷二叉樹

voidPreTree(){ PreTree(root);}voidPreTree(TreeNode<T>*point){ if(point!=NULL) { cout<<""<<point->data;PreTree(point->lchild);PreTree(point->rchild); }}BDCAroot‘/’‘/’‘/’‘/’‘/’

//先序遍歷二叉樹

voidPreTree(){ PreTree(root);}voidPreTree(TreeNode<T>*point){ if(point!=NULL) { cout<<""<<point->data;PreTree(point->lchild);PreTree(point->rchild); }}BDCAroot‘/’‘/’‘/’‘/’‘/’//中序遍歷二叉樹voidInoTree(){ InoTree(root);}voidInoTree(TreeNode<T>*point){

if(point!=NULL)

{

InoTree(point->lchild);

cout<<""<<point->data;

InoTree(point->rchild);

}}BDCAroot‘/’‘/’‘/’‘/’‘/’//后序遍歷二叉樹

voidPosTree(){ PosTree(root);}voidPosTree(TreeNode<T>*point){if(point!=NULL){PosTree(point->lchild);

PosTree(point->rchild);cout<<""<<point->data;}}BDCAroot‘/’‘/’‘/’‘/’‘/’#include<iostream>#include"BinTree.h"usingnamespacestd;//主函數(shù)voidmain(){BinTree<char>BinTreeOPP;BinTreeOPP.CreatTree();cout<<"先序："<<endl;BinTreeOPP.PreTree();cout<<endl;cout<<"中序："<<endl;BinTreeOPP.InoTree();cout<<endl;cout<<"后序："<<endl;BinTreeOPP.levelorder();cout<<endl;}BDCAroot‘/’‘/’‘/’‘/’‘/’《數(shù)據(jù)結(jié)構(gòu)與算法》

廊坊師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院授課教師：崔業(yè)勤第五章二叉樹★★★★★根二叉樹的遍歷TLRTLR—先（根）序遍歷LTR—中（根）序遍歷LRT—后（根）序遍歷規(guī)定遍歷順序自左至右：內(nèi)容回顧根二叉樹的遍歷TLRTLR—先（根）序遍歷LTR—中（根）序遍歷LRT—后（根）序遍歷規(guī)定遍歷順序自左至右：內(nèi)容回顧根LR二叉樹的遍歷TLR—先（根）序遍歷規(guī)定遍歷順序自左至右：根TL根LRBDFECALTR—中（根）序遍歷LRT—后（根）序遍歷ABDEFCBEDFACEFDBCA中序遍歷一棵二叉搜索樹可以得到所有結(jié)點(diǎn)的有序序列二叉搜索樹的用途：快速查找特定的元素5.4二叉搜索樹構(gòu)造二叉樹搜索的過程就是給數(shù)據(jù)排序的過程，中序遍歷可得到有序序列二分法思想二叉搜索樹：其內(nèi)部結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值，均小于它的根結(jié)點(diǎn)，右子樹上所有結(jié)點(diǎn)的值，均大于它的根結(jié)點(diǎn)35403878942356515.4二叉搜索樹構(gòu)造二叉搜索樹：從二叉樹的根結(jié)點(diǎn)開始創(chuàng)建比根節(jié)點(diǎn)小的值作為左子樹的根，比根結(jié)點(diǎn)大的值作為右子樹的根重復(fù)值不允許插入56,34,78,4,7,98,64563478479864練習(xí)5.4二叉搜索樹二叉搜索樹插入結(jié)點(diǎn)：（同創(chuàng)建）25二叉搜索樹刪除結(jié)點(diǎn)：若該結(jié)點(diǎn)無左子樹，則直接用該結(jié)點(diǎn)的右子樹的根代替該結(jié)點(diǎn)56347847986470765.4二叉搜索樹二叉搜索樹插入結(jié)點(diǎn)：（同創(chuàng)建）56347849864725二叉搜索樹刪除結(jié)點(diǎn)：若該結(jié)點(diǎn)無左子樹，則直接用該結(jié)點(diǎn)的右子樹的根代替該結(jié)點(diǎn)4若該結(jié)點(diǎn)有左子樹，則在左子樹中找到最大的結(jié)點(diǎn)代替它70765.4二叉搜索樹二叉搜索樹插入結(jié)點(diǎn)：（同創(chuàng)建）56347849864725二叉搜索樹刪除結(jié)點(diǎn)：若該結(jié)點(diǎn)無左子樹，則直接用該結(jié)點(diǎn)的右子樹的根代替該結(jié)點(diǎn)4若該結(jié)點(diǎn)有左子樹，則在左子樹中找到最大的結(jié)點(diǎn)代替它707856765.4二叉搜索樹二叉搜索樹插入結(jié)點(diǎn)：（同創(chuàng)建）56347849864725二叉搜索樹刪除結(jié)點(diǎn)：若該結(jié)點(diǎn)無左子樹，則直接用該結(jié)點(diǎn)的右子樹的根代替該結(jié)點(diǎn)4若該結(jié)點(diǎn)有左子樹，則在左子樹中找到最大的結(jié)點(diǎn)代替它70785676左子樹中的最大結(jié)點(diǎn)：1.該子樹中沒有右子樹，根既是最大2.該子樹中有右子樹，則順著右子樹分支找到的最后一個(gè)結(jié)點(diǎn)為最大5.4二叉搜索樹3422789864736刪除結(jié)點(diǎn)練習(xí)：6146992278687263365.4二叉搜索樹二叉搜索樹特點(diǎn)：是一種插入，刪除，檢索效率都較高的數(shù)據(jù)組織方法123456788490939901234567線性順序結(jié)構(gòu)：檢索快，插入刪除效率低同其它數(shù)據(jù)組織方法的比較：

線性鏈?zhǔn)浇Y(jié)構(gòu)：插入刪除快，檢索效率低3456788490939912堆的用途：

在一組數(shù)據(jù)中快速查找最大值或最小值堆：是一種特殊的完全二叉樹，其內(nèi)部結(jié)點(diǎn)的值均不大于（或小于）其左右結(jié)點(diǎn)的值5.5堆與優(yōu)先隊(duì)列42345345767899958最小堆9823451418339911最大堆

局部有序士兵1士兵3********公主***士兵2誰先救走了公主？構(gòu)造最小堆：按層次結(jié)構(gòu)放置各個(gè)元素，構(gòu)造一棵完全二叉樹從最后一個(gè)非終端結(jié)點(diǎn)即無序序列中第

n/2

個(gè)元素開始，將該結(jié)點(diǎn)的左右子結(jié)點(diǎn)中較小的值與該結(jié)點(diǎn)互換位置。依次調(diào)整到根結(jié)點(diǎn)，在調(diào)整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊(duì)列98234514183399119823451418339911構(gòu)造最小堆：按層次結(jié)構(gòu)放置各個(gè)元素，構(gòu)造一棵完全二叉樹從最后一個(gè)非終端結(jié)點(diǎn)即無序序列中第

n/2

個(gè)元素開始，將該結(jié)點(diǎn)的左右子結(jié)點(diǎn)中較小的值與該結(jié)點(diǎn)互換位置。依次調(diào)整到根結(jié)點(diǎn)，在調(diào)整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊(duì)列98234514183399119823451418339911構(gòu)造最小堆：按層次結(jié)構(gòu)放置各個(gè)元素，構(gòu)造一棵完全二叉樹從最后一個(gè)非終端結(jié)點(diǎn)即無序序列中第

n/2

個(gè)元素開始，將該結(jié)點(diǎn)的左右子結(jié)點(diǎn)中較小的值與該結(jié)點(diǎn)互換位置。依次調(diào)整到根結(jié)點(diǎn)，在調(diào)整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊(duì)列98234514183399119823451418339911構(gòu)造最小堆：按層次結(jié)構(gòu)放置各個(gè)元素，構(gòu)造一棵完全二叉樹從最后一個(gè)非終端結(jié)點(diǎn)即無序序列中第

n/2

個(gè)元素開始，將該結(jié)點(diǎn)的左右子結(jié)點(diǎn)中較小的值與該結(jié)點(diǎn)互換位置。依次調(diào)整到根結(jié)點(diǎn)，在調(diào)整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊(duì)列98234514183399119823451418339911構(gòu)造最小堆：按層次結(jié)構(gòu)放置各個(gè)元素，構(gòu)造一棵完全二叉樹從最后一個(gè)非終端結(jié)點(diǎn)即無序序列中第

n/2

個(gè)元素開始，將該結(jié)點(diǎn)的左右子結(jié)點(diǎn)中較小的值與該結(jié)點(diǎn)互換位置。依次調(diào)整到根結(jié)點(diǎn)，在調(diào)整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊(duì)列98234514183399119823451418339911構(gòu)造最小堆：按層次結(jié)構(gòu)放置各個(gè)元素，構(gòu)造一棵完全二叉樹從最后一個(gè)非終端結(jié)點(diǎn)即無序序列中第

n/2

個(gè)元素開始，將該結(jié)點(diǎn)的左右子結(jié)點(diǎn)中較小的值與該結(jié)點(diǎn)互換位置。依次調(diào)整到根結(jié)點(diǎn)，在調(diào)整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊(duì)列98234514183399119823451418339911構(gòu)造最小堆：按層次結(jié)構(gòu)放置各個(gè)元素，構(gòu)造一棵完全二叉樹從最后一個(gè)非終端結(jié)點(diǎn)即無序序列中第

n/2

個(gè)元素開始，將該結(jié)點(diǎn)的左右子結(jié)點(diǎn)中較小的值與該結(jié)點(diǎn)互換位置。依次調(diào)整到根結(jié)點(diǎn)，在調(diào)整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊(duì)列98234514183399119823451418339911堆插入結(jié)點(diǎn)：先將該元素排列到最后按堆性質(zhì)調(diào)整元素到合適位置5.5堆與優(yōu)先隊(duì)列98234514183399116堆插入結(jié)點(diǎn)：先將該元素排列到最后按堆性質(zhì)調(diào)整元素到合適位置5.5堆與優(yōu)先隊(duì)列98234514183399116堆插入結(jié)點(diǎn)：先將該元素排列到最后按堆性質(zhì)調(diào)整元素到合適位置5.5堆與優(yōu)先隊(duì)列98234514183399116堆插入結(jié)點(diǎn)：先將該元素排列到最后按堆性質(zhì)調(diào)整元素到合適位置5.5堆與優(yōu)先隊(duì)列98234514183399116堆刪除結(jié)點(diǎn)：先將最后一個(gè)元素調(diào)整到刪除元素位置按堆性質(zhì)依次向下調(diào)整堆插入結(jié)點(diǎn)：先將該元素排列到最后按堆性質(zhì)調(diào)整元素到合適位置5.5堆與優(yōu)先隊(duì)列982345143399116堆刪除結(jié)點(diǎn)：先將最后一個(gè)元素調(diào)整到刪除元素位置按堆性質(zhì)依次向下調(diào)整18堆插入結(jié)點(diǎn)：先將該元素排列到最后按堆性質(zhì)調(diào)整元素到合適位置5.5堆與優(yōu)先隊(duì)列98234514339911堆刪除結(jié)點(diǎn)：先將最后一個(gè)元素調(diào)整到刪除元素位置按堆性質(zhì)依次向下調(diào)整18堆練習(xí)：5.5堆與優(yōu)先隊(duì)列18214724191339451845139194732124構(gòu)造最小堆3451824191347921插入結(jié)點(diǎn)4堆練習(xí)：5.5堆與優(yōu)先隊(duì)列1821472419133945構(gòu)造最小堆3451824191347921插入結(jié)點(diǎn)434518249134742119//創(chuàng)建二叉搜索樹voidcreatbst(){creatbst(root);}voidcreatbst(TreeNode<T>*&root){ Tn; cin>>n;TreeNode<T>*point=root;TreeNode<T>*newpoint; newpoint=newTreeNode<T>; newpoint->data=n; if(root==NULL) { root=newpoint;return；} while(point!=NULL){//關(guān)鍵字相同的元素不予處理 if(newpoint->data==point->data)

return; elseif(newpoint->data<point->data){

if(point->lchild==NULL){

point->lchild=newpoint;

return;