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

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

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

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

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

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

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

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

個(gè)結(jié)點(diǎn)。

那么，第i-1層至多有

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

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

二.二叉樹結(jié)構(gòu)性質(zhì)2：深度為k的二叉樹至多有2k

–1

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

設(shè)n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)；因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2

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

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

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

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

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

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

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

ABDCEFrootG

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

datatypedata;structnode*lchild,*rchild;}TREENODE;??四、二叉樹的存儲(chǔ)結(jié)構(gòu)二.二叉樹結(jié)構(gòu)ABCDEGHFK1、二叉樹中分支數(shù)B和結(jié)點(diǎn)數(shù)n的關(guān)系

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

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

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