樹和二叉樹part1課件

第六章樹和二叉樹

主講：戚玉濤第六章樹和二叉樹主講：戚玉濤1第6章樹和二叉樹

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

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

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

主講：戚玉濤第六章樹和二叉樹主講：戚玉濤21第6章樹和二叉樹

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

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

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