軟件技術(shù)基礎(chǔ)1

一.樹結(jié)構(gòu)樹結(jié)構(gòu)的基本概念和術(shù)語二.二叉樹結(jié)構(gòu)基本概念二叉樹的存儲二叉樹的遍歷二叉樹的應(yīng)用第1頁，共25頁。一.樹結(jié)構(gòu)結(jié)點、根、分支結(jié)點、葉子結(jié)點、兄弟結(jié)點的度、樹的度、樹的深度/高度/層次EBJKAFCDGHIMNL第1層第2層第3層第4層第2頁，共25頁。第3頁，共25頁。a*(b＋c/d)＋e*h－g*f(s，t，x＋y)第4頁，共25頁。樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。樹是由n（n≥1）個結(jié)點組成的有限集合。（1）有一個特定的稱為根（root）的結(jié)點。它可有直接后繼，沒有直接前驅(qū)；（2）除根結(jié)點以外的其它結(jié)點可以劃分為m(m≥0)個互不相交的有限集合T0,T1,…,Tm-1,每個集合Ti又是一棵樹，稱為根的子樹(subTree)，每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。一.樹結(jié)構(gòu)第5頁，共25頁。

二叉樹是n（n≥0）個結(jié)點組成的有限集，它或者是空集（n=0），或是由一個根結(jié)點及兩棵不相交的左子樹和右子樹組成。特點：

(1)二叉樹的特點是每個結(jié)點最多有兩個孩子，或者說，在二叉樹中不存在度大于2的結(jié)點。

(2)二叉樹是有序樹，其子樹的順序不能顛倒。一、二叉樹的定義二.二叉樹結(jié)構(gòu)第6頁，共25頁。二.二叉樹結(jié)構(gòu)(a)空二叉樹(b)只有一個結(jié)點(c)只有左子樹(d)只有右子樹(e)有左右子樹二叉樹有五種不同的形態(tài)：第7頁，共25頁。ABCDEFGHIJKLM123456二.二叉樹結(jié)構(gòu)ABC第8頁，共25頁。二叉樹與一般樹的概念區(qū)別：樹至少應(yīng)有一個結(jié)點，而二叉樹可以是空的；二叉樹的所有子樹要區(qū)分為左子樹和右子樹，其結(jié)點的度不超過2。二.二叉樹結(jié)構(gòu)第9頁，共25頁。思考題任意三個結(jié)點可構(gòu)造多少種樹?

多少種二叉樹?二.二叉樹結(jié)構(gòu)第10頁，共25頁。性質(zhì)1：在二叉樹的第i層上至多有2i-1

個結(jié)點(i>=1)。二、二叉樹的性質(zhì)

i=1時，只有一個根結(jié)點，假設(shè)對所有j(1j<i)命題成立，即第j層上至多有

個結(jié)點。

那么，第i-1層至多有

個結(jié)點。又二叉樹每個結(jié)點的度至多為2，

第i層上最大結(jié)點數(shù)是第i-1層的2倍，即

二.二叉樹結(jié)構(gòu)第11頁，共25頁。性質(zhì)2：深度為k的二叉樹至多有2k

–1

個結(jié)點(k>=1)。證明：由性質(zhì)1，可得深度為k的二叉樹最大結(jié)點數(shù)是（證明用求等比級數(shù)前k項和的公式）二.二叉樹結(jié)構(gòu)第12頁，共25頁。性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。二.二叉樹結(jié)構(gòu)ABCDEF第13頁，共25頁。證明：

設(shè)n1為二叉樹T中度為1的結(jié)點數(shù)；因為：二叉樹中所有結(jié)點的度均小于或等于2所以：其結(jié)點總數(shù)n=n0+n1+n2

又二叉樹中，除根結(jié)點外，其余結(jié)點都只有一個分支進(jìn)入，設(shè)B為分支總數(shù)，則n=B+1

又分支由度為1和度為2的結(jié)點發(fā)出，故B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2

n0=n2+1二.二叉樹結(jié)構(gòu)第14頁，共25頁。三、幾種特殊形式的二叉樹1231145891213671014151234567二.二叉樹結(jié)構(gòu)（1）滿二叉樹：

特點：每一層上的結(jié)點數(shù)都達(dá)到最大結(jié)點個數(shù)。第15頁，共25頁。（2）完全二叉樹定義：深度為k,有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為~123114589126710123456二.二叉樹結(jié)構(gòu)第16頁，共25頁。（2）完全二叉樹葉子結(jié)點只可能在層次最大的兩層上出現(xiàn);對任一結(jié)點，若其右分支下子孫的最大層次為L，則其左分支下子孫的最大層次必

為L或L+1。123114589126710思考題:第五層有5個葉子結(jié)點的完全二叉樹，最多有多少個結(jié)點?二.二叉樹結(jié)構(gòu)第17頁，共25頁。（3）二叉排序樹或者為一棵空樹、或者：左子樹所有結(jié)點的關(guān)鍵字均小于根；右子樹所有結(jié)點的關(guān)鍵字均大于根。子樹本身也是一棵二叉排序樹。8412635291016二.二叉樹結(jié)構(gòu)第18頁，共25頁。1、順序存儲：

用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素。ABCDEFG1234567ABCDEFG二.二叉樹結(jié)構(gòu)四、二叉樹的存儲結(jié)構(gòu)第19頁，共25頁。對于一般二叉樹，則應(yīng)將其每個結(jié)點與完全二叉樹上的結(jié)點相對應(yīng)，不存在的結(jié)點用用“0”填充。四、二叉樹的存儲結(jié)構(gòu)ABCDEFGABCDE0000FG1234567891011特點：結(jié)點間關(guān)系蘊含在其存儲位置中浪費空間，適于存儲滿二叉樹和完全二叉樹二.二叉樹結(jié)構(gòu)第20頁，共25頁。BCDAEFG

ABDCEFrootG

四、二叉樹的存儲結(jié)構(gòu)2、二叉鏈表二.二叉樹結(jié)構(gòu)typedefstructnode{

datatypedata;structnode*lchild,*rchild;}TREENODE;第21頁，共25頁。??四、二叉樹的存儲結(jié)構(gòu)二.二叉樹結(jié)構(gòu)ABCDEGHFK第22頁，共25頁。1、二叉樹中分支數(shù)B和結(jié)點數(shù)n的關(guān)系

，2、二叉鏈樹中空指針數(shù)用結(jié)點數(shù)n表示為

。3、對于滿二叉樹或完全二叉樹：①若i<=n/2，則i的左孩子編號為

,否則i沒有左孩子；②若i<=(n-1)/2，則i的右孩子編號

，否則i