樹(shù)和二叉樹(shù)part1課件

第六章樹(shù)和二叉樹(shù)

主講：戚玉濤第六章樹(shù)和二叉樹(shù)主講：戚玉濤1第6章樹(shù)和二叉樹(shù)

樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)?，F(xiàn)實(shí)生活中有著廣泛存在。如：家譜，組織機(jī)構(gòu)關(guān)系等。在計(jì)算機(jī)領(lǐng)域中樹(shù)在編譯程序和數(shù)據(jù)庫(kù)系統(tǒng)中也得到了廣泛的應(yīng)用。直觀來(lái)看樹(shù)是以分支關(guān)系來(lái)定義的層次結(jié)構(gòu)，其中以樹(shù)和二叉樹(shù)最為常用。第6章樹(shù)和二叉樹(shù)樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。2第6章樹(shù)和二叉樹(shù)6.1樹(shù)的類型定義6.2二叉樹(shù)的類型定義6.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.4二叉樹(shù)的遍歷6.5線索二叉樹(shù)6.6樹(shù)和森林的表示方法6.7樹(shù)和森林的遍歷6.8哈夫曼樹(shù)與哈夫曼編碼第6章樹(shù)和二叉樹(shù)6.1樹(shù)的類型定義3樹(shù)的類型定義數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹(shù)；否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)。樹(shù)的類型定義數(shù)據(jù)對(duì)象D：4舉例：舉例：5樹(shù)的類型定義基本操作：查找類插入類刪除類樹(shù)的類型定義基本操作：6

Root(T)//求樹(shù)的根結(jié)點(diǎn)查找類：Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹(shù)是否為空樹(shù)TreeDepth(T)//求樹(shù)的深度TraverseTree(T,Visit())//遍歷Root(T)//求樹(shù)的根結(jié)點(diǎn)查找類：Val7InitTree(&T)//初始化置空樹(shù)插入類：CreateTree(&T,definition)//按定義構(gòu)造樹(shù)Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹(shù)插入為結(jié)點(diǎn)p的第i棵子樹(shù)InitTree(&T)//初始化置空樹(shù)插入類：C8

ClearTree(&T)//將樹(shù)清空刪除類：DestroyTree(&T)//銷毀樹(shù)的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹(shù)ClearTree(&T)//將樹(shù)清空刪除類：De9樹(shù)的邏輯表示法(1)樹(shù)型表示法。這是樹(shù)的最基本的表示,使用一棵倒置的樹(shù)表示樹(shù)結(jié)構(gòu),非常直觀和形象。樹(shù)的邏輯表示法(1)樹(shù)型表示法。這是樹(shù)的最基本的表示,使10樹(shù)的邏輯表示法(2)文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹(shù)結(jié)構(gòu)。樹(shù)的邏輯表示法(2)文氏圖表示法。使用集合以及集合的包含關(guān)系11樹(shù)的邏輯表示法(3)凹入表示法。使用線段的伸縮描述樹(shù)結(jié)構(gòu)。樹(shù)的邏輯表示法(3)凹入表示法。使用線段的伸縮描述樹(shù)結(jié)構(gòu)。12樹(shù)的邏輯表示法(4)括號(hào)表示法(廣義表表示法)。將樹(shù)的根結(jié)點(diǎn)寫(xiě)在括號(hào)的左邊,除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫(xiě)在括號(hào)中并用逗號(hào)間隔來(lái)描述樹(shù)結(jié)構(gòu)。樹(shù)的邏輯表示法(4)括號(hào)表示法(廣義表表示法)。將樹(shù)的根結(jié)點(diǎn)13樹(shù)的分類有向樹(shù)：(１)有確定的根；(２)樹(shù)根和子樹(shù)根之間為有向關(guān)系。有序樹(shù)：子樹(shù)之間存在確定的次序關(guān)系。無(wú)序樹(shù)：子樹(shù)之間不存在確定的次序關(guān)系。樹(shù)的分類有向樹(shù)：14對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)線性結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)樹(shù)型結(jié)構(gòu)根結(jié)點(diǎn)(無(wú)前驅(qū))多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)15樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。結(jié)點(diǎn)的度(degree)：結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)。樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。葉子(leaf)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。16樹(shù)的基本術(shù)語(yǔ)(從根到結(jié)點(diǎn)的)路徑：由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成。孩子、雙親、兄弟、堂兄弟：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子。相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親。同一雙親的孩子之間互稱兄弟。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。B、C、D是A的孩子。A是B、C、D的雙親。結(jié)點(diǎn)H、I、J互為兄弟結(jié)點(diǎn)。樹(shù)的基本術(shù)語(yǔ)(從根到結(jié)點(diǎn)的)路徑：由從根到該結(jié)點(diǎn)所經(jīng)分支和17樹(shù)的基本術(shù)語(yǔ)路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)結(jié)點(diǎn)ki和kj,若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一結(jié)點(diǎn)都是其在序列中的前一個(gè)結(jié)點(diǎn)的后繼,則稱該結(jié)點(diǎn)序列為由ki到kj的一條路徑。用路徑所通過(guò)的結(jié)點(diǎn)序列(ki,ki1,ki2,…,kj)表示這條路徑。路徑的長(zhǎng)度等于路徑所通過(guò)的結(jié)點(diǎn)數(shù)目減1(即路徑上分支數(shù)目)?？梢?jiàn),路徑就是從ki出發(fā)“自上而下”到達(dá)kj所通過(guò)的樹(shù)中結(jié)點(diǎn)序列。顯然,從樹(shù)的根結(jié)點(diǎn)到樹(shù)中其余結(jié)點(diǎn)均存在一條路徑。樹(shù)的基本術(shù)語(yǔ)路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)結(jié)點(diǎn)ki和kj,若樹(shù)18樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)的祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。結(jié)點(diǎn)的子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。1234結(jié)點(diǎn)的層次：假設(shè)根結(jié)點(diǎn)的層次為1，第l層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為l+1樹(shù)的高度(深度)：樹(shù)中結(jié)點(diǎn)的最大層次。樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)的祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。19樹(shù)的基本術(shù)語(yǔ)森林：m（m≥0）棵互不相交的樹(shù)的集合。將一棵非空樹(shù)的根結(jié)點(diǎn)刪去，樹(shù)就變成一個(gè)森林；反之，給m棵獨(dú)立的樹(shù)增加一個(gè)根結(jié)點(diǎn)，并把這m棵樹(shù)作為該結(jié)點(diǎn)的子樹(shù)，森林就變成一棵樹(shù)。任何一棵非空樹(shù)是一個(gè)二元組Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點(diǎn)F被稱為子樹(shù)森林rootABCDEFGHIJMKLF樹(shù)的基本術(shù)語(yǔ)森林：m（m≥0）棵互不相交的樹(shù)的集合。將一棵20第六章樹(shù)和二叉樹(shù)

主講：戚玉濤第六章樹(shù)和二叉樹(shù)主講：戚玉濤21第6章樹(shù)和二叉樹(shù)

樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。現(xiàn)實(shí)生活中有著廣泛存在。如：家譜，組織機(jī)構(gòu)關(guān)系等。在計(jì)算機(jī)領(lǐng)域中樹(shù)在編譯程序和數(shù)據(jù)庫(kù)系統(tǒng)中也得到了廣泛的應(yīng)用。直觀來(lái)看樹(shù)是以分支關(guān)系來(lái)定義的層次結(jié)構(gòu)，其中以樹(shù)和二叉樹(shù)最為常用。第6章樹(shù)和二叉樹(shù)樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。22第6章樹(shù)和二叉樹(shù)6.1樹(shù)的類型定義6.2二叉樹(shù)的類型定義6.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.4二叉樹(shù)的遍歷6.5線索二叉樹(shù)6.6樹(shù)和森林的表示方法6.7樹(shù)和森林的遍歷6.8哈夫曼樹(shù)與哈夫曼編碼第6章樹(shù)和二叉樹(shù)6.1樹(shù)的類型定義23樹(shù)的類型定義數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹(shù)；否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)。樹(shù)的類型定義數(shù)據(jù)對(duì)象D：24舉例：舉例：25樹(shù)的類型定義基本操作：查找類插入類刪除類樹(shù)的類型定義基本操作：26

Root(T)//求樹(shù)的根結(jié)點(diǎn)查找類：Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹(shù)是否為空樹(shù)TreeDepth(T)//求樹(shù)的深度TraverseTree(T,Visit())//遍歷Root(T)//求樹(shù)的根結(jié)點(diǎn)查找類：Val27InitTree(&T)//初始化置空樹(shù)插入類：CreateTree(&T,definition)//按定義構(gòu)造樹(shù)Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹(shù)插入為結(jié)點(diǎn)p的第i棵子樹(shù)InitTree(&T)//初始化置空樹(shù)插入類：C28

ClearTree(&T)//將樹(shù)清空刪除類：DestroyTree(&T)//銷毀樹(shù)的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹(shù)ClearTree(&T)//將樹(shù)清空刪除類：De29樹(shù)的邏輯表示法(1)樹(shù)型表示法。這是樹(shù)的最基本的表示,使用一棵倒置的樹(shù)表示樹(shù)結(jié)構(gòu),非常直觀和形象。樹(shù)的邏輯表示法(1)樹(shù)型表示法。這是樹(shù)的最基本的表示,使30樹(shù)的邏輯表示法(2)文氏圖表示法。使用集合以及集合的包含關(guān)系描述樹(shù)結(jié)構(gòu)。樹(shù)的邏輯表示法(2)文氏圖表示法。使用集合以及集合的包含關(guān)系31樹(shù)的邏輯表示法(3)凹入表示法。使用線段的伸縮描述樹(shù)結(jié)構(gòu)。樹(shù)的邏輯表示法(3)凹入表示法。使用線段的伸縮描述樹(shù)結(jié)構(gòu)。32樹(shù)的邏輯表示法(4)括號(hào)表示法(廣義表表示法)。將樹(shù)的根結(jié)點(diǎn)寫(xiě)在括號(hào)的左邊,除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫(xiě)在括號(hào)中并用逗號(hào)間隔來(lái)描述樹(shù)結(jié)構(gòu)。樹(shù)的邏輯表示法(4)括號(hào)表示法(廣義表表示法)。將樹(shù)的根結(jié)點(diǎn)33樹(shù)的分類有向樹(shù)：(１)有確定的根；(２)樹(shù)根和子樹(shù)根之間為有向關(guān)系。有序樹(shù)：子樹(shù)之間存在確定的次序關(guān)系。無(wú)序樹(shù)：子樹(shù)之間不存在確定的次序關(guān)系。樹(shù)的分類有向樹(shù)：34對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)線性結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)樹(shù)型結(jié)構(gòu)根結(jié)點(diǎn)(無(wú)前驅(qū))多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)35樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。結(jié)點(diǎn)的度(degree)：結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)。樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。葉子(leaf)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。36樹(shù)的基本術(shù)語(yǔ)(從根到結(jié)點(diǎn)的)路徑：由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成。孩子、雙親、兄弟、堂兄弟：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子。相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親。同一雙親的孩子之間互稱兄弟。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。B、C、D是A的孩子。A是B、C、D的雙親。結(jié)點(diǎn)H、I、J互為兄弟結(jié)點(diǎn)。樹(shù)的基本術(shù)語(yǔ)(從根到結(jié)點(diǎn)的)路徑：由從根到該結(jié)點(diǎn)所經(jīng)分支和37樹(shù)的基本術(shù)語(yǔ)路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)結(jié)點(diǎn)ki和kj,若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一結(jié)點(diǎn)都是其在序列中的前一個(gè)結(jié)點(diǎn)的后繼,則稱該結(jié)點(diǎn)序列為由ki到kj的一條路徑。用路徑所通過(guò)的結(jié)點(diǎn)序列(ki,ki1,ki2,…,kj)表示這條路徑。路徑的長(zhǎng)度等于路徑所通過(guò)的結(jié)點(diǎn)數(shù)目減1(即路徑上分支數(shù)目)?？梢?jiàn),路徑就是從ki出發(fā)“自上而下”到達(dá)kj所通過(guò)的樹(shù)中結(jié)點(diǎn)序列。顯然,從樹(shù)的根結(jié)點(diǎn)到樹(shù)中其余結(jié)點(diǎn)均存在一條路徑。樹(shù)的基本術(shù)語(yǔ)路徑與路徑長(zhǎng)度：對(duì)于任意兩個(gè)結(jié)點(diǎn)ki和kj,若樹(shù)38樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)的祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。結(jié)點(diǎn)的子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。1234結(jié)點(diǎn)的層次：假設(shè)根結(jié)點(diǎn)的層次為1，第l層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為l+1樹(shù)的高