第7章 樹(shù)形結(jié)構(gòu)

第七章樹(shù)和二叉樹(shù)7.1-2 樹(shù)和二叉樹(shù)的概念與性質(zhì)7.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)7.4 二叉樹(shù)的操作算法7.6-7 線(xiàn)索二叉樹(shù)的操作算法樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換7.8 樹(shù)的應(yīng)用---Huffman編碼決策分析小王是一家著名高爾夫俱樂(lè)部的經(jīng)理。但是他被雇員數(shù)量問(wèn)題搞得心情十分不好。某些天好像所有人都來(lái)玩高爾夫，以至于所有員工都忙的團(tuán)團(tuán)轉(zhuǎn)還是應(yīng)付不過(guò)來(lái)，而有些天不知道什么原因卻一個(gè)人也不來(lái)，俱樂(lè)部為雇員數(shù)量浪費(fèi)了不少資金。小王的目的是通過(guò)下周天氣預(yù)報(bào)尋找什么時(shí)候人們會(huì)打高爾夫，以適時(shí)調(diào)整雇員數(shù)量。因此首先他必須了解人們決定是否打球的原因。在2周時(shí)間內(nèi)我們得到以下記錄:

天氣狀況（sun）有晴，云和雨；氣溫用華氏溫度表示；相對(duì)濕度用百分比；還有有無(wú)風(fēng)。當(dāng)然還有顧客是不是在這些日子光顧俱樂(lè)部。最終他得到了14行5列的數(shù)據(jù)表格：樹(shù)結(jié)構(gòu)和線(xiàn)性結(jié)構(gòu)的比較線(xiàn)性結(jié)構(gòu)樹(shù)結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素根結(jié)點(diǎn)（只有一個(gè)）無(wú)前驅(qū)無(wú)雙親最后一個(gè)數(shù)據(jù)元素葉子結(jié)點(diǎn)(可以有多個(gè))無(wú)后繼無(wú)孩子其它數(shù)據(jù)元素其它結(jié)點(diǎn)一個(gè)前驅(qū),一個(gè)后繼一個(gè)雙親,多個(gè)孩子一對(duì)一一對(duì)多樹(shù)的邏輯結(jié)構(gòu)7.1樹(shù)的基本概念

7.1.1樹(shù)的定義

7.1.3樹(shù)的基本術(shù)語(yǔ)7.1.2樹(shù)的表示7.1.1樹(shù)的定義：核心關(guān)系：層次關(guān)系。

樹(shù)：n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n＝0時(shí)，稱(chēng)為空樹(shù)；任意一棵非空樹(shù)滿(mǎn)足以下條件：⑴

有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)；⑵

當(dāng)n＞1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的有限集合T1,T2,…,Tm，其中每個(gè)集合又是一棵樹(shù)，并稱(chēng)為這個(gè)根結(jié)點(diǎn)的子樹(shù)。1.1通俗定義樹(shù)形表示法廣義表表示法a(b(e,f,g),c(h),d(i,j))樹(shù)是n(n>0)個(gè)結(jié)點(diǎn)的有限集，在任意一棵樹(shù)中：1有且只有一個(gè)特定的根(root)結(jié)點(diǎn)；2當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限子集T1,T2...Tm，每個(gè)子集是一棵樹(shù)，稱(chēng)為子樹(shù)。判斷以下是否為樹(shù)型結(jié)構(gòu)7.1.3樹(shù)的基本術(shù)語(yǔ)

1.樹(shù)的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素和指向其子樹(shù)的所有分支。

2.結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有的子樹(shù)的個(gè)數(shù)。

A

C

G

J

B

E

D

F

I

H

M

K

L

樹(shù)形表示法

AA的度：3B的度：2C的度：1D的度：2E的度：0I的度：33.分支結(jié)點(diǎn)與葉結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn),又叫分支結(jié)點(diǎn)。度為零的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)或葉結(jié)點(diǎn)。4.樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值max(D(I))。含義：樹(shù)中最大分支數(shù)為樹(shù)的度。A的度：3B的度：2C的度：1D的度：2E的度：0I的度：3

A

C

G

B

D

I

JEFH

MKL

樹(shù)形表示法

樹(shù)的度：3結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)，也稱(chēng)高度。1層2層4層3層高度＝4CGBDEFKLHMIJC樹(shù)的基本術(shù)語(yǔ) 5.CBDEFKLHJA71234568910層序編號(hào)：將樹(shù)中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開(kāi)始的連續(xù)自然數(shù)。樹(shù)的基本術(shù)語(yǔ)有序樹(shù)、無(wú)序樹(shù)：如果一棵樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的，稱(chēng)這棵樹(shù)為有序樹(shù)；反之，稱(chēng)為無(wú)序樹(shù)。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹(shù)

樹(shù)的基本術(shù)語(yǔ) 6.ACBGFEDACBGFEDCBDEFKLHJ森林：m(m≥0)棵互不相交的樹(shù)的集合。

樹(shù)的基本術(shù)語(yǔ) 7.A路徑：如果樹(shù)的結(jié)點(diǎn)序列n1,n2,…,nk有如下關(guān)系：則把n1,n2,…,nk稱(chēng)為一條由n1至nk的路徑；路徑上經(jīng)過(guò)的邊的個(gè)數(shù)稱(chēng)為路徑長(zhǎng)度。CGBDEFKLHMIJA樹(shù)的基本術(shù)語(yǔ) 8.祖先、子孫：在樹(shù)中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y，那么x就稱(chēng)為y的祖先，而y稱(chēng)為x的子孫。CGBDEFKLHMIJA樹(shù)的基本術(shù)語(yǔ) 9.

總結(jié)基本術(shù)語(yǔ)的理解：結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度；如結(jié)點(diǎn)D含有3個(gè)子樹(shù)，則結(jié)點(diǎn)D的度為3，而結(jié)點(diǎn)C的度為1，結(jié)點(diǎn)K的度為0。葉結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)；如結(jié)點(diǎn)F的度為0，則為葉子結(jié)點(diǎn)。非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)；

雙親結(jié)點(diǎn)（父結(jié)點(diǎn)）：含有孩子的結(jié)點(diǎn)稱(chēng)為其孩子的雙親結(jié)點(diǎn)；例如，結(jié)點(diǎn)B是E,F的雙親結(jié)點(diǎn)（父結(jié)點(diǎn)）。孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)；例如，結(jié)點(diǎn)B的孩子結(jié)點(diǎn)有E,F兩個(gè)。兄弟結(jié)點(diǎn)：具有相同雙親結(jié)點(diǎn)的結(jié)點(diǎn)互稱(chēng)為兄弟結(jié)點(diǎn)；如E,F互為兄弟結(jié)點(diǎn)。CGBDEFKLHMIJA

總結(jié)基本術(shù)語(yǔ)的理解：樹(shù)的度：一棵樹(shù)中，最大的結(jié)點(diǎn)的度稱(chēng)為樹(shù)的度；結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第一層，根的孩子為第二層；

樹(shù)的高度或深度：樹(shù)中結(jié)點(diǎn)的最大層次；堂兄弟：雙親在同一層的結(jié)點(diǎn)互為堂兄弟；

結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)；子孫：以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的子孫。森林：由m（m>=0）棵互不相交的樹(shù)的集合稱(chēng)為森林；CGBDEFKLHMIJA1.有一棵樹(shù)如圖所示，回答下面的問(wèn)題（1）這棵樹(shù)的葉子結(jié)點(diǎn)是___________。（2）結(jié)點(diǎn)k3的度是______________（3）這棵樹(shù)的度是_____________（4）這棵樹(shù)的深度是____________（5）結(jié)點(diǎn)k3的孩子結(jié)點(diǎn)是___________（6）這棵樹(shù)的根結(jié)點(diǎn)是___________（7）結(jié)點(diǎn)k3的雙親結(jié)點(diǎn)是____________樹(shù)的表示方法（廣義表法）二叉樹(shù)的定義

二叉樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（稱(chēng)為空二叉樹(shù)），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱(chēng)為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。二叉樹(shù)的邏輯結(jié)構(gòu)問(wèn)題轉(zhuǎn)化：將樹(shù)轉(zhuǎn)換為二叉樹(shù)，從而利用二叉樹(shù)解決樹(shù)的有關(guān)問(wèn)題。研究二叉樹(shù)的意義？設(shè)有八枚硬幣，分別表示為a、b、c、d、e、f、g、h，其中有且僅有一枚硬幣是假幣，并且假幣的重量與真幣的重量不同，可能輕，也可能重?，F(xiàn)要求以天平為工具，用最少的比較次數(shù)挑選出假幣，并同時(shí)確定這枚假幣的重量比其它真幣是輕還是重。把硬幣分成三組，從八枚硬幣中任取六枚a、b、c、d、e、f，在天平兩端各放三枚進(jìn)行比較。假設(shè)a、b、c三枚放在天平的一端，d、e、f三枚放在天平的另一端，可能出現(xiàn)如圖所示的三種比較結(jié)

7.2二叉樹(shù)概念和性質(zhì)

7.2.1二叉樹(shù)概念7.2.2二叉樹(shù)性質(zhì)7.2.3二叉樹(shù)存儲(chǔ)結(jié)構(gòu)7.2.1二叉樹(shù)概念二叉樹(shù)也稱(chēng)為二次樹(shù)或二分樹(shù)，它是結(jié)點(diǎn)數(shù)為0或當(dāng)節(jié)點(diǎn)數(shù)不為0時(shí)每個(gè)結(jié)點(diǎn)最多只有左右兩棵子樹(shù)的樹(shù)。特點(diǎn)是：（1）每個(gè)結(jié)點(diǎn)最多只有兩棵樹(shù)，既不存在度大于2的結(jié)點(diǎn)。（2）子樹(shù)有左右之分，不能顛倒。思考：二叉樹(shù)和度為2的樹(shù)一樣嗎有什么區(qū)別？結(jié)點(diǎn)的孩子數(shù)結(jié)點(diǎn)孩子的有序性二叉樹(shù)的特點(diǎn)：⑴每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)；⑵二叉樹(shù)是有序的，其次序不能任意顛倒。

7.2.1二叉樹(shù)的邏輯結(jié)構(gòu)注意：二叉樹(shù)和樹(shù)是兩種樹(shù)結(jié)構(gòu)。ABCDEFGABAB二叉樹(shù)的基本形態(tài)Ф空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)左子樹(shù)根結(jié)點(diǎn)只有左子樹(shù)右子樹(shù)根結(jié)點(diǎn)只有右子樹(shù)左子樹(shù)右子樹(shù)根結(jié)點(diǎn)同時(shí)有左右子樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)二叉樹(shù)的邏輯結(jié)構(gòu)具有3個(gè)結(jié)點(diǎn)的樹(shù)和具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)的形態(tài)二叉樹(shù)和樹(shù)是兩種樹(shù)結(jié)構(gòu)。特殊的二叉樹(shù)斜樹(shù)1.所有結(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)稱(chēng)為左斜樹(shù)；2.所有結(jié)點(diǎn)都只有右子樹(shù)的二叉樹(shù)稱(chēng)為右斜樹(shù)；3.左斜樹(shù)和右斜樹(shù)統(tǒng)稱(chēng)為斜樹(shù)。1.在斜樹(shù)中，每一層只有一個(gè)結(jié)點(diǎn)；2.斜樹(shù)的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。

二叉樹(shù)的邏輯結(jié)構(gòu)---斜樹(shù)的特點(diǎn)：ABCABC滿(mǎn)二叉樹(shù)在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上。滿(mǎn)二叉樹(shù)的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點(diǎn)。CDEFGHIJKLMNO1112131415特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---滿(mǎn)二叉樹(shù)?不是滿(mǎn)二叉樹(shù)，雖然所有分支結(jié)點(diǎn)都有左右子樹(shù)，但葉子不在同一層上。滿(mǎn)二叉樹(shù)在同樣深度的二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多滿(mǎn)二叉樹(shù)在同樣深度的二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)最多A1523467BCDEFGLM89特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---完全二叉樹(shù)對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與同樣深度的滿(mǎn)二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置完全相同。CDEFGHIJKLMNO1112131415CDEFGHIJ特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---在滿(mǎn)二叉樹(shù)中，從最后一個(gè)結(jié)點(diǎn)開(kāi)始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹(shù)。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹(shù)，結(jié)點(diǎn)10與滿(mǎn)二叉樹(shù)中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---1.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹(shù)的左部；2.完全二叉樹(shù)中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。

3.深度為k的完全二叉樹(shù)在k-1層上一定是滿(mǎn)二叉樹(shù)。完全二叉樹(shù)的特點(diǎn)CDEFGHIJ特殊的二叉樹(shù)二叉樹(shù)的邏輯結(jié)構(gòu)---總結(jié)二叉樹(shù)的概念二叉樹(shù)的五種形態(tài)斜二叉樹(shù)滿(mǎn)二叉樹(shù)完全二叉樹(shù)7.2.2二叉樹(shù)性質(zhì)（5個(gè)）

性質(zhì)1非空二叉樹(shù)上第i層上至多有2i-1個(gè)結(jié)點(diǎn),這里應(yīng)有i≥1。

性質(zhì)1非空二叉樹(shù)上第i層上至多有2i-1個(gè)結(jié)點(diǎn),這里應(yīng)有i≥1。證明：用歸納法（1）當(dāng)i=120有一個(gè)根結(jié)點(diǎn)成立（2）假設(shè)對(duì)所有的j(1<=j<i)上述性質(zhì)成立。即第j層上至多有2j-1個(gè)結(jié)點(diǎn)成立（3）要證明j=i時(shí)，命題也成立由歸納假設(shè)：第j=i-1層上至多有2i-2

個(gè)結(jié)點(diǎn)，又由于二叉樹(shù)上每個(gè)結(jié)點(diǎn)的度最大為2，所以第i層上結(jié)點(diǎn)總數(shù)最大為第i-1層上最大結(jié)點(diǎn)數(shù)的2倍，即2×2i-2=2i-1

性質(zhì)2高度為h的二叉樹(shù)至多有2h-1個(gè)結(jié)點(diǎn)(h≥1)。證明：深度為h的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是二叉樹(shù)中每層結(jié)點(diǎn)的最大數(shù)之和，即=20+21+22+……+2h-1=2h-1(等比級(jí)數(shù)求和)

性質(zhì)3非空二叉樹(shù)上葉結(jié)點(diǎn)數(shù)等于度為2的結(jié)點(diǎn)數(shù)加1。有如下關(guān)系：n0=n2+1

證明：設(shè)二叉樹(shù)上葉結(jié)點(diǎn)數(shù)為n0,單分支結(jié)點(diǎn)數(shù)為n1,雙分支結(jié)點(diǎn)數(shù)為n2,則總結(jié)點(diǎn)數(shù)n=n0+n1+n2。在一棵二叉樹(shù)中,度為i(i=0,1,2)的結(jié)點(diǎn)，有i個(gè)孩子。孩子數(shù)=n1+2n2。由于二叉樹(shù)中除根結(jié)點(diǎn)以外,每個(gè)結(jié)點(diǎn)都是另一個(gè)結(jié)點(diǎn)的孩子,因此二叉樹(shù)中有：孩子數(shù)=總結(jié)點(diǎn)數(shù)-1=n-1。由上述三個(gè)等式可得：n1+2n2=n-1=n0+n1+n2-1即：n0=n2+1

A

B

C

D

E

H

J

K

F

G

L

M

N

O

二叉樹(shù)

(1)一棵二叉樹(shù)中雙分支結(jié)點(diǎn)有15個(gè)，單分支結(jié)點(diǎn)30個(gè)，則葉子結(jié)點(diǎn)有（）。(2)若一棵滿(mǎn)二叉樹(shù)有2047個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)為

A)512 B)1024 C)2048 D)4096(3)若一棵度為7的樹(shù)具有n1=8,n2=7,n3=6,n4=5,n5=4,n6=3,n7=2,則該樹(shù)一共有（）個(gè)葉結(jié)點(diǎn)[提示：此不是二叉樹(shù)，用性質(zhì)3的證明方法來(lái)推導(dǎo)]

在一棵二叉樹(shù)中,如果所有分支結(jié)點(diǎn)都有左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn),并且葉結(jié)點(diǎn)都集中在二叉樹(shù)的最下一層,這樣的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。下圖所示就是一棵滿(mǎn)二叉樹(shù)。可以對(duì)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),約定編號(hào)從樹(shù)根為1開(kāi)始,按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。每一層上結(jié)點(diǎn)樹(shù)都達(dá)到最大度為1的結(jié)點(diǎn)n1=0完全二叉樹(shù):若二叉樹(shù)中度小于2的結(jié)點(diǎn)只能出現(xiàn)在最大層或次大層,并且最下面一層的葉結(jié)點(diǎn)都依次排列在該層最左邊的位置上,則這樣的二叉樹(shù)稱(chēng)為完全二叉樹(shù)。如下圖所示為一棵完全二叉樹(shù)。同樣可以對(duì)完全二叉樹(shù)中每個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),編號(hào)的方法同滿(mǎn)二叉樹(shù)相同。

12

3

4

1

2

3

4

5

6

判斷是否為：完全二叉樹(shù)？（1）LH1=2RH1=1LH2=0RH2=10-1=-1不滿(mǎn)足（2）葉結(jié)點(diǎn)只能出現(xiàn)在最大層或次大層從左邊開(kāi)始結(jié)論：不是（1）LH1=3RH1=1LH1-RH1=2不滿(mǎn)足（2）葉結(jié)點(diǎn)只能出現(xiàn)在最大層或次大層且從從左邊開(kāi)始結(jié)論：不是

性質(zhì)4具有n個(gè)(n＞0)結(jié)點(diǎn)的完全二叉樹(shù)的高（深）度為log2n+1。證明：設(shè)深度為H余下的性質(zhì)是針對(duì)完全二叉樹(shù)的：證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k，根據(jù)完全二叉樹(shù)的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)

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

2k-1≤n＜2k性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1。

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

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數(shù)，故必有k＝log2n+1一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中從1開(kāi)始按層序編號(hào)，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)為

i/2；結(jié)點(diǎn)i的左孩子為2i；結(jié)點(diǎn)i的右孩子為2i＋1。

在完全二叉樹(shù)中，結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系。完全二叉樹(shù)的基本性質(zhì)

性質(zhì)5對(duì)n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)(1≤i≤n,n≥1,n為結(jié)點(diǎn)數(shù))有：

(1)若i=1時(shí)，結(jié)點(diǎn)i是樹(shù)根；否則（i>1）,結(jié)點(diǎn)i的雙親為

i/2.(2)若2i>n時(shí)。結(jié)點(diǎn)i無(wú)左孩子，是葉結(jié)點(diǎn)；否則結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2i。

(3)若2i+1>n時(shí)。結(jié)點(diǎn)i無(wú)右孩子；否則結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2i+1。余下的性質(zhì)是針對(duì)完全二叉樹(shù)的（很重要）：先證明（2）（3）用歸納法

(2)若2i>n時(shí)。結(jié)點(diǎn)i無(wú)左孩子，是葉結(jié)點(diǎn)；否則結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2i。

(3)若2i+1>n時(shí)。結(jié)點(diǎn)i無(wú)右孩子；否則結(jié)點(diǎn)i的左孩子為結(jié)點(diǎn)2i+1。1）當(dāng)i=1時(shí)，如果2i=2>n無(wú)左孩子，否則2i=2<=n

結(jié)點(diǎn)2存在是結(jié)點(diǎn)1的左孩子。第二條成立當(dāng)i=1時(shí)，如果2i+1=3>n無(wú)右孩子，否則2i+1=3<=n

結(jié)點(diǎn)3存在是結(jié)點(diǎn)1的右孩子。第三條成立2）假設(shè)對(duì)所有的結(jié)點(diǎn)j(1<=j<=i)有：j的左孩子為2j(2j<=n),右孩子為2j+1(2j+1<=n)3)要證明j=i+1時(shí)等式成立i+1的左孩子為2（i+1） (2(i+1)<=n)i+1的右孩子為2（i+1）+1 (2(i+1)+1<=n)i2i2i+1

i+12i+22i+3…………i與i+1同層……

i2i2i+1……

i+12i+22i+3……i與i+1不同層結(jié)論：得證(1)若i=1時(shí)，結(jié)點(diǎn)i是樹(shù)根；否則（i>1）,結(jié)點(diǎn)i的雙親為

i/2.用歸納法自己證明第五條性質(zhì)非常重要，是二叉樹(shù)順序存儲(chǔ)的理論基礎(chǔ)7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換1.兄弟加線(xiàn).樹(shù)轉(zhuǎn)化為二叉樹(shù)ABCDEFG2.保留雙親與第一孩子連線(xiàn),刪去與其他孩子的連線(xiàn).ABCDEFG1.兄弟加線(xiàn).7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線(xiàn),刪去與其他孩子的連線(xiàn).1.兄弟加線(xiàn).ABCDEFG7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系3.順時(shí)針轉(zhuǎn)動(dòng),使之層次分明.2.保留雙親與第一孩子連線(xiàn),刪去與其他孩子的連線(xiàn).1.兄弟加線(xiàn).GDABECF7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和二叉樹(shù)之間的對(duì)應(yīng)關(guān)系總結(jié)：樹(shù)轉(zhuǎn)換為二叉樹(shù)

⑴加線(xiàn)——樹(shù)中所有相鄰兄弟之間加一條連線(xiàn)。

⑵去線(xiàn)——對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線(xiàn)，刪去它與其它孩子結(jié)點(diǎn)之間的連線(xiàn)。

⑶層次調(diào)整——以根結(jié)點(diǎn)為軸心，將樹(shù)順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之層次分明。

森林轉(zhuǎn)換為二叉樹(shù)

⑴將森林中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)；⑵從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹(shù)連起來(lái)后，此時(shí)所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換IHGBCDAFE二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林

⑴加線(xiàn)——若某結(jié)點(diǎn)x是其雙親y的左孩子，則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子、……，都與結(jié)點(diǎn)y用線(xiàn)連起來(lái)；⑵去線(xiàn)——?jiǎng)h去原二叉樹(shù)中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線(xiàn)；⑶

層次調(diào)整——整理由⑴、⑵兩步所得到的樹(shù)或森林，使之層次分明。

7.2.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換FHGEAICDBFHGDCEBAIFEDCBAHGI加線(xiàn)去線(xiàn)層次調(diào)整IHGBCDAFE樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換例題:將下面的深林轉(zhuǎn)化為二叉樹(shù)ACDBEFGJIH7.3二叉樹(shù)存儲(chǔ)結(jié)構(gòu)

7.3.1二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)

7.3.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.3.1二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元，以層序的順序存放二叉樹(shù)的數(shù)據(jù)元素，結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)的關(guān)系?！咀⒁狻窟壿嬯P(guān)系蘊(yùn)含在這里：結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)的關(guān)系。ABCDEFGHIJK123456789101112131415順序存儲(chǔ)結(jié)構(gòu)一般二叉樹(shù)的順序存儲(chǔ)沒(méi)有左右孩子的地方填0

A

B

C

D

E

FG

一般二叉樹(shù)

ABCDE0000FG0000123456789101112131415順序存儲(chǔ)結(jié)構(gòu)例：深度為K,只有K個(gè)結(jié)點(diǎn)的右單支樹(shù)的存放：分析:根據(jù)性質(zhì)2：二叉樹(shù)深度為K最多有2k-1個(gè)結(jié)點(diǎn)按順序存儲(chǔ)實(shí)際只使用K個(gè)存儲(chǔ)單元，浪費(fèi)掉2k-1-K

1

2

K

1

K

結(jié)論：順序存儲(chǔ)只適合完全二叉樹(shù)，既不浪費(fèi)空間，又能很快的確定結(jié)點(diǎn)存放的位置，以及結(jié)點(diǎn)的雙親和左右孩子。但是對(duì)于一般二叉樹(shù)可能造成存儲(chǔ)空間的浪費(fèi)。7.3.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

常用的：二叉鏈表三叉鏈表線(xiàn)索鏈表

A

B

C

D

E

FG

一般二叉樹(shù)

在二叉樹(shù)的鏈接存儲(chǔ)中,結(jié)點(diǎn)的結(jié)構(gòu)如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹(shù)的根結(jié)點(diǎn))的存儲(chǔ)位置。lchilddatarchild二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)點(diǎn)：找孩子比較容易，找雙親很難

A

B

C

E

F

D

G

A

B∧

C

∧

D

∧

E∧

∧

F∧

∧

G∧

(a)

(b)

在三叉鏈表的存儲(chǔ)中,結(jié)點(diǎn)的結(jié)構(gòu)如下:

typedefstructnode{ ElemTypedata; structnode*lchild,*parent,*rchild;}BTNode;

其中,data表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹(shù)的根結(jié)點(diǎn))的存儲(chǔ)位置，parent

指向結(jié)點(diǎn)的雙親。lchilddataparentrchild二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

A

B

C

E

F

D

G

(a)

∧A∧BCD∧∧F∧∧E∧∧G∧性質(zhì)6：含有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空鏈域證明：（1）n=n0+n1+n2（2）空鏈域=2n0+n1（3）no=n2+1

A

B

C

E

F

D

G

A

B∧

C

∧

D

∧

E∧

∧

F∧

∧

G∧

(a)

(b)

7.5二叉樹(shù)的遍歷7.5.1二叉樹(shù)遍歷的概念7.5.2二叉樹(shù)遍歷的實(shí)現(xiàn)遞歸及非遞歸算法二叉樹(shù)的遍歷操作

二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪(fǎng)問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次。二叉樹(shù)遍歷操作的結(jié)果？非線(xiàn)性結(jié)構(gòu)線(xiàn)性化7.5二叉樹(shù)的邏輯結(jié)構(gòu)抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡(jiǎn)化為輸出結(jié)點(diǎn)的數(shù)據(jù)。前序遍歷中序遍歷后序遍歷層序遍歷

如果限定先左后右，則二叉樹(shù)遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹(shù)的層序編號(hào)的次序訪(fǎng)問(wèn)各結(jié)點(diǎn)。

7.5.1二叉樹(shù)的邏輯結(jié)構(gòu)考慮二叉樹(shù)的組成：根結(jié)點(diǎn)D左子樹(shù)L右子樹(shù)R二叉樹(shù)前序遍歷若二叉樹(shù)為空，則空操作返回；否則：①訪(fǎng)問(wèn)根結(jié)點(diǎn)；②前序遍歷根結(jié)點(diǎn)的左子樹(shù)；③前序遍歷根結(jié)點(diǎn)的右子樹(shù)。前序遍歷序列：ABDGCEFABCDEFG二叉樹(shù)的遍歷操作

7.5二叉樹(shù)的邏輯結(jié)構(gòu)中序遍歷若二叉樹(shù)為空，則空操作返回；否則：①中序遍歷根結(jié)點(diǎn)的左子樹(shù)；②訪(fǎng)問(wèn)根結(jié)點(diǎn)；③中序遍歷根結(jié)點(diǎn)的右子樹(shù)。

中序遍歷序列：DGBAECFABCDEFG二叉樹(shù)的遍歷操作

7.5二叉樹(shù)的邏輯結(jié)構(gòu)后序遍歷若二叉樹(shù)為空，則空操作返回；否則：①后序遍歷根結(jié)點(diǎn)的左子樹(shù)；②后序遍歷根結(jié)點(diǎn)的右子樹(shù)。③訪(fǎng)問(wèn)根結(jié)點(diǎn)；后序遍歷序列：GDBEFCAABCDEFG二叉樹(shù)的遍歷操作

7.5二叉樹(shù)的邏輯結(jié)構(gòu)層序遍歷二叉樹(shù)的層次遍歷是指從二叉樹(shù)的第一層（即根結(jié)點(diǎn)）開(kāi)始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪(fǎng)問(wèn)。

層序遍歷序列：ABCDEFGABCDEFG二叉樹(shù)的遍歷操作

7.5二叉樹(shù)的邏輯結(jié)構(gòu)

A

B

C

D

E

H

I

J

K

F

G

1

2

3

4

5

6

7

8

9

10

11

先序序列：ABDHIEJKCFG中序序列：HDIBJEKAFCG后序序列：HIDJKEBFGCA先序序列：ABDEHJKLMNCFGI中序序列：DBJHLKMNEAFCGI后序序列：DJLMNKHEBFGICA在二叉樹(shù)的鏈接存儲(chǔ)中,結(jié)點(diǎn)的結(jié)構(gòu)如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹(shù)的根結(jié)點(diǎn))的存儲(chǔ)位置。lchilddatarchild二叉樹(shù)及其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

(a)

(b)

A

B

C

E

F

D

A

B

C

∧

D∧

∧

E∧

∧

F∧

∧1.先序遍歷DLR先序遍歷二叉樹(shù)的過(guò)程是：(1)訪(fǎng)問(wèn)根結(jié)點(diǎn)D；(2)先序遍歷左子樹(shù)L；(3)先序遍歷右子樹(shù)R。先序序列：ABDECF/*先序遍歷的遞歸算法*/voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/PreOrder(b->lchild);PreOrder(b->rchild);}}

A

B

C

E

F

D

lchilddatarchild/*先序遍歷的遞歸算法*/voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);

/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/PreOrder(b->lchild);PreOrder(b->rchild);}}PreOrder(&A)APreOrder(A->lchild=B);BPreOrder(B->lchild=D);DPreOrder(D->lchild=NULL);PreOrder(D->rchild=NULL);PreOrder(B->rchild=E);EPreOrder(E->lchild=NULL);PreOrder(E->rchild=NULL);PreOrder(A->rchild=C);CPreOrder(C->lchild=NULL);PreOrder(C->rchild=F);FPreOrder(F->lchild=NULL);PreOrder(F->rchild=NULL);

A

B

C

∧

D∧

∧

E∧

∧

F∧

∧2.中序遍歷LDR中序遍歷二叉樹(shù)的過(guò)程是：(1)中序遍歷左子樹(shù)L；(2)訪(fǎng)問(wèn)根結(jié)點(diǎn)D；(3)中序遍歷右子樹(shù)R。中序序列：DBEACF/*中序遍歷的遞歸算法*/voidInOrder(BTNode*b){if(b!=NULL){/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/

InOrder(b->lchild);

printf("%c",b->data);

InOrder(b->rchild);}}

A

B

C

E

F

D

3.后序遍歷后序遍歷二叉樹(shù)的過(guò)程是：(1)后序遍歷左子樹(shù)；(2)后序遍歷右子樹(shù)；(3)訪(fǎng)問(wèn)根結(jié)點(diǎn)。后序序列：DEBFCA

voidPostOrder(BTNode*b)/*后序遍歷遞歸算法*/{if(b!=NULL)