樹的概念和定義（課堂PPT）

1、第十四講1樹的概念與定義樹的概念與定義 第十四講2 樹是n（n0）個(gè)結(jié)點(diǎn)的有限集合T。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n0時(shí)， 該集合滿足如下條件： (1) 其中必有一個(gè)稱為根（root）的特定結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 (2) 其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m0）個(gè)互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵樹，稱為根root的子樹。 每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 第十四講3圖6.1 樹的圖示方法EFBAGKLMHIJCD第十四講4結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其它結(jié)點(diǎn)的分支信息。 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)稱為此結(jié)點(diǎn)的度。 葉結(jié)

2、點(diǎn)：度為0的結(jié)點(diǎn)，即無后繼的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。 孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。雙親結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接前驅(qū)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。兄弟結(jié)點(diǎn)：同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。第十四講5祖先結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。在圖6.1中，結(jié)點(diǎn)K的祖先是A、B、E。 子孫結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼和間接后繼稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。在圖6.1中，結(jié)點(diǎn)D的子孫是H、I、 J、 M。 樹的度： 樹中所有結(jié)點(diǎn)的度的最大值。 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始定義，根結(jié)點(diǎn)的層次為1，根的直接后繼的層次為2，依此類推。 樹

3、的高度（深度）： 樹中所有結(jié)點(diǎn)的層次的最大值。 有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。 森林： m（m0）棵互不相交的樹的集合。將一棵非空樹的根結(jié)點(diǎn)刪去，樹就變成一個(gè)森林；反之，給森林增加一個(gè)統(tǒng)一的根結(jié)點(diǎn)，森林就變成一棵樹。 第十四講6 ADT Tree 數(shù)據(jù)對(duì)象D：一個(gè)集合，該集合中的所有元素具有相同的特性。 數(shù)據(jù)關(guān)系R： 若D為空集，則為空樹。 若D中僅含有一個(gè)數(shù)據(jù)元素，則R為空集，否則R=H，H是如下的二元關(guān)系： (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root， 它在關(guān)系H下沒有前驅(qū)。 (2) 除root以外， D中每個(gè)結(jié)點(diǎn)在關(guān)系H下都有且僅有一個(gè)前驅(qū)。 第

4、十四講7 基本操作：基本操作： (1) InitTree（Tree）： 將Tree初始化為一棵空樹。 (2) DestoryTree（Tree）： 銷毀樹Tree。 (3) CreateTree（Tree）： 創(chuàng)建樹Tree。 (4) TreeEmpty（Tree）： 若Tree為空， 則返回TRUE， 否則返回FALSE。 (5) Root（Tree）： 返回樹Tree的根。 (6) Parent（Tree， x）： 樹Tree存在， x是Tree中的某個(gè)結(jié)點(diǎn)。 若x為非根結(jié)點(diǎn)，則返回它的雙親， 否則返回“空”。 第十四講8 (7) FirstChild（Tree，x）： 樹Tree存在，

5、x是Tree中的某個(gè)結(jié)點(diǎn)。若x為非葉子結(jié)點(diǎn)，則返回它的第一個(gè)孩子結(jié)點(diǎn)， 否則返回“空”。 (8) NextSibling（Tree，x）： 樹Tree存在，x是Tree中的某個(gè)結(jié)點(diǎn)。若x不是其雙親的最后一個(gè)孩子結(jié)點(diǎn)，則返回x后面的下一個(gè)兄弟結(jié)點(diǎn)， 否則返回“空”。 第十四講9 (9) InsertChild（Tree， p， Child）：樹Tree存在，p指向Tree中某個(gè)結(jié)點(diǎn)，非空樹Child與Tree不相交。將Child插入Tree中， 做p所指向結(jié)點(diǎn)的子樹。 (10) DeleteChild（Tree，p，i）： 樹Tree存在， p指向Tree中某個(gè)結(jié)點(diǎn)， 1id，d為p所指向結(jié)點(diǎn)的

6、度。 刪除Tree中p所指向結(jié)點(diǎn)的第i棵子樹。 (11) TraverseTree（Tree，Visit（）： 樹Tree存在，Visit（）是對(duì)結(jié)點(diǎn)進(jìn)行訪問的函數(shù)。按照某種次序?qū)銽ree的每個(gè)結(jié)點(diǎn)調(diào)用Visit（）函數(shù)訪問一次且最多一次。若Visit（）失敗， 則操作失敗。 第十四講10二叉樹的定義與基本操作二叉樹的定義與基本操作 第十四講11 定義：我們把滿足以下兩個(gè)條件的樹形結(jié)構(gòu)叫做二叉樹二叉樹（Binary Tree）： （1） 每個(gè)結(jié)點(diǎn)的度都不大于2； （2） 每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。 由此定義可以看出，一個(gè)二叉樹中的每個(gè)結(jié)點(diǎn)只能含有0、 1或2個(gè)孩子，而且每個(gè)孩子有左

7、右之分。我們把位于左邊的孩子叫做左孩子，位于右邊的孩子叫做右孩子。 第十四講12圖6.2給出了二叉樹的五種基本形態(tài)。 (a) 空二叉樹(b) 只有根結(jié)點(diǎn) 的二叉樹(c) 只有左子樹 的二叉樹(d) 左右子樹均非 空的二叉樹(e) 只有右子樹的二叉樹第十四講13 與樹的基本操作類似，二叉樹有如下基本操作： (1) Initiate（bt）：將bt初始化為空二叉樹。 (2) Create(bt)： 創(chuàng)建一棵非空二叉樹bt。 (3) Destory（bt）： 銷毀二叉樹bt。 (4) Empty（bt）：若bt為空，則返回TRUE，否則返回FALSE。 (5) Root(bt)： 求二叉樹bt的根結(jié)

8、點(diǎn)。若bt為空二叉樹， 則函數(shù)返回“空”。 第十四講14 (6) Parent（bt， x）：求雙親函數(shù)。求二叉樹bt中結(jié)點(diǎn)x的雙親結(jié)點(diǎn)。若結(jié)點(diǎn)x是二叉樹的根結(jié)點(diǎn)或二叉樹bt中無結(jié)點(diǎn)x， 則返回“空”。 (7) LeftChild（bt， x）：求左孩子。 若結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或x不在bt中， 則返回“空”。 (8) RightChild（bt， x）：求右孩子。 若結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或x不在bt中， 則返回“空”。 (9) Traverse（bt）: 遍歷操作。按某個(gè)次序依次訪問二叉樹中每個(gè)結(jié)點(diǎn)一次且僅一次。 (10) Clear（bt）： 清除操作。 將二叉樹bt置為空樹。 第十四講15二叉樹

9、的性質(zhì)二叉樹的性質(zhì) 第十四講16 性質(zhì)性質(zhì)1: 在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。 證明：證明： 用數(shù)學(xué)歸納法。 歸納基礎(chǔ)：當(dāng)i=1時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，結(jié)論成立。 歸納假設(shè)：假設(shè)i=k時(shí)結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)。 現(xiàn)證明當(dāng)i=k+1時(shí)， 結(jié)論成立： 因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為2，則第k+1層的結(jié)點(diǎn)總數(shù)最多為第k層上結(jié)點(diǎn)最大數(shù)的2倍，即22k-1=2(k+1)-1，故結(jié)論成立。 第十四講17 性質(zhì)性質(zhì)2: 深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k1）。 證明證明：因?yàn)樯疃葹閗的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是將二叉樹每層上結(jié)點(diǎn)的最

10、大值相加，所以深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為 kikikii111122層上的最大結(jié)點(diǎn)個(gè)數(shù)第故結(jié)論成立。 第十四講18 性質(zhì)性質(zhì)3: 對(duì)任意一棵二叉樹T，若終端結(jié)點(diǎn)數(shù)為n0，而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。 證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n， n1為二叉樹中度為1的結(jié)點(diǎn)總數(shù)。 因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度小于等于2，所以有n=n0+n1+n2 設(shè)二叉樹中分支數(shù)目為B， 因?yàn)槌Y(jié)點(diǎn)外， 每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有n=B+1第十四講19 又因?yàn)槎鏄渲械姆种Ф际怯啥葹?和度為2的結(jié)點(diǎn)發(fā)出， 所以分支數(shù)目為B=n1+2n2 整理上述兩式可得到 n=B+1=n1+2n2+1 將n

11、=n0+n1+n2代入上式，得出n0+n1+n2=n1+2n2+1，整理后得n0=n2+1，故結(jié)論成立。 第十四講20滿二叉樹：滿二叉樹： 深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。 圖6.3(a)所示的二叉樹，即為一棵滿二叉樹。 滿二叉樹的順序表示，即從二叉樹的根開始， 層間從上到下， 層內(nèi)從左到右，逐層進(jìn)行編號(hào)（1， 2， ， n）。例如圖6.3(a)所示的滿二叉樹的順序表示為(1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11， 12， 13， 14， 15)。 第十四講21 完全二叉樹：完全二叉樹： 深度為k，結(jié)點(diǎn)數(shù)

12、為n的二叉樹，如果其結(jié)點(diǎn)1n的位置序號(hào)分別與滿二叉樹的結(jié)點(diǎn)1n的位置序號(hào)一一對(duì)應(yīng)，則為完全二叉樹， 如圖6.3(b)所示。 滿二叉樹必為完全二叉樹， 而完全二叉樹不一定是滿二叉樹。 第十四講22圖6.3 滿二叉樹與完全二叉樹 8910111213452136714158910111213452136714(a) 滿二叉樹(b) 完全二叉樹第十四講23 性質(zhì)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。 證明：假設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹的結(jié)點(diǎn)總數(shù)為n1=2k-1-1 k層滿二叉樹的結(jié)點(diǎn)總數(shù)為n2=2k-1 顯然有n1nn2，進(jìn)一步可以推出n1+

13、1nn2+1。 將n1=2k-1-1和n2=2k-1代入上式，可得2k-1n2k，即k-1log2n1， 則序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào)為i/2。 （2） 如2in，則序號(hào)為i的結(jié)點(diǎn)無左孩子；如2in，則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i。 （3） 如2i1n，則序號(hào)為i的結(jié)點(diǎn)無右孩子；如2i1n， 則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i1。 第十四講25 可以用歸納法證明其中的（2）和（3）： 當(dāng)i=1時(shí)，由完全二叉樹的定義知，如果2i=2n，說明二叉樹中存在兩個(gè)或兩個(gè)以上的結(jié)點(diǎn)，所以其左孩子存在且序號(hào)為2； 反之，如果2n，說明二叉樹中不存在序號(hào)為2的結(jié)點(diǎn)，其左孩子不存在。同理，如果

14、2i+1=3n， 說明其右孩子存在且序號(hào)為3；如果3n，則二叉樹中不存在序號(hào)為3的結(jié)點(diǎn)， 其右孩子不存在。 假設(shè)對(duì)于序號(hào)為j(1ji)的結(jié)點(diǎn)，當(dāng)2jn時(shí)，其左孩子存在且序號(hào)為2j，當(dāng)2jn 時(shí)，其左孩子不存在；當(dāng)2j+1n時(shí)， 其右孩子存在且序號(hào)為2j+1，當(dāng)2j+1n時(shí)，其右孩子不存在。 第十四講26 當(dāng)i=j+1時(shí)，根據(jù)完全二叉樹的定義， 若其左孩子存在， 則其左孩子結(jié)點(diǎn)的序號(hào)一定等于序號(hào)為j的結(jié)點(diǎn)的右孩子的序號(hào)加1， 即其左孩子結(jié)點(diǎn)的序號(hào)等于 （2j+1）+1=2（j+1）=2i， 且有2in；如果2in， 則左孩子不存在。 若右孩子結(jié)點(diǎn)存在，則其右孩子結(jié)點(diǎn)的序號(hào)應(yīng)等于其左孩子結(jié)點(diǎn)的序號(hào)

15、加1，即右孩子結(jié)點(diǎn)的序號(hào)為2i+1，且有2i+1n；如果2i+1n，則右孩子不存在。 故（2）和（3）得證。 第十四講27 由（2）和（3）我們可以很容易證明（1）。 當(dāng)i=1時(shí)， 顯然該結(jié)點(diǎn)為根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。當(dāng)i1時(shí)，設(shè)序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為m，如果序號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，根據(jù)（2）有i=2m，即m=i/2; 如果序號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，根據(jù)（3）有i=2m+1， 即m=（i-1）/2=i/2-1/2，綜合這兩種情況，可以得到，當(dāng)i1時(shí)， 其雙親結(jié)點(diǎn)的序號(hào)等于i/2。證畢。 第十四講28二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu) 第十四講29二叉樹的結(jié)構(gòu)是非線性的

16、， 每一結(jié)點(diǎn)最多可有兩個(gè)后繼。 二叉樹的存儲(chǔ)結(jié)構(gòu)有兩種： 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 1. 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 圖6.4 二叉樹與順序存儲(chǔ)結(jié)構(gòu) HIJKLDEBACFG(a) 滿二叉樹(b) 二叉樹的順序存儲(chǔ)結(jié)構(gòu)ABCDEFGHIJKL第十四講30圖6.5 單支二叉樹與其順序存儲(chǔ)結(jié)構(gòu) ABCD(a) 單支二叉樹ABCD(b) 順 序 存 儲(chǔ) 結(jié) 構(gòu)第十四講31 2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 對(duì)于任意的二叉樹來說，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、 左孩子域和右孩子： LChildDataRChild其中，LChild域指向該結(jié)點(diǎn)的左孩子，

17、Data域記錄該結(jié)點(diǎn)的信息，RChild域指向該結(jié)點(diǎn)的右孩子。 第十四講32用C語言可以這樣聲明二叉樹的二叉鏈表結(jié)點(diǎn)的結(jié)構(gòu)： typedef struct NodeDataType data; struct Node *LChild; struct Node *RChild; BiTNode, *BiTree; 有時(shí)，為了便于找到父結(jié)點(diǎn)，可以增加一個(gè)Parent域， Parent域指向該結(jié)點(diǎn)的父結(jié)點(diǎn)。 該結(jié)點(diǎn)結(jié)構(gòu)如下： LChildDataparentRChild第十四講33圖6.6 二叉樹和二叉鏈表 BCDGEFADEFCBGA(a) 二叉樹T(b) 二叉樹 T 的 二 叉 鏈 表第十四講3

18、4 若一個(gè)二叉樹含有n個(gè)結(jié)點(diǎn)，則它的二叉鏈表中必含有2n個(gè)指針域， 其中必有n1個(gè)空的鏈域。此結(jié)論證明如下： 證明：分支數(shù)目B=n-1，即非空的鏈域有n-1個(gè)，故空鏈域有2n-(n-1)=n+1個(gè)。 不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹的操作也不同。如要找某個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，在三叉鏈表中很容易實(shí)現(xiàn)；在二叉鏈表中則需從根指針出發(fā)一一查找?？梢姡诰唧w應(yīng)用中，需要根據(jù)二叉樹的形態(tài)和需要進(jìn)行的操作來決定二叉樹的存儲(chǔ)結(jié)構(gòu)。 第十四講35二叉樹的遍歷二叉樹的遍歷第十四講36圖6.7 二叉樹結(jié)點(diǎn)的基本結(jié)構(gòu) LChildDataRChildLChildRChildData第十四講37 我們用L、D、R分別表示遍歷左子樹、

19、訪問根結(jié)點(diǎn)、 遍歷右子樹， 那么對(duì)二叉樹的遍歷順序就可以有六種方式： (1) 訪問根，遍歷左子樹，遍歷右子樹（記做DLR）。 (2) 訪問根，遍歷右子樹，遍歷左子樹（記做DRL）。 (3) 遍歷左子樹，訪問根，遍歷右子樹（記做LDR）。 (4) 遍歷左子樹，遍歷右子樹，訪問根（記做LRD）。 (5) 遍歷右子樹，訪問根，遍歷左子樹（記做RDL）。 (6) 遍歷右子樹，遍歷左子樹，訪問根（記做RLD）。 第十四講38 注意：先序、中序、后序遍歷是遞歸定義的， 即在其子樹中亦按上述規(guī)律進(jìn)行遍歷。 下面就分別介紹三種遍歷方法的遞歸定義。 先序遍歷（DLR）操作過程： 若二叉樹為空，則空操作，否則依次執(zhí)行如下3個(gè)操作： (1) 訪問根結(jié)點(diǎn)； (2) 按