數(shù)據(jù)結(jié)構(gòu)與算法chapter6樹和二叉樹教學(xué)課件

第6章樹和二叉樹61應(yīng)用實例62樹的概念6.3二又樹64二又樹的遍歷65線索二叉樹6.6樹和森林67哈夫曼樹及其應(yīng)用68實例分析與實現(xiàn)6.9算法總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法chapter6樹和二叉樹第6章樹和二叉樹61應(yīng)用實例62樹的概念6.3二又樹64二又樹的遍歷65線索二叉樹6.6樹和森林67哈夫曼樹及其應(yīng)用68實例分析與實現(xiàn)6.9算法總結(jié)第6章樹和二叉樹6.1應(yīng)用實例實例一:數(shù)據(jù)壓縮問題在信息傳輸、數(shù)據(jù)壓縮問題中,我們總是希望找到一種編碼能將待處理數(shù)據(jù)壓縮得盡可能的短。實例二:表達式的樹形表示任意一個表達式,均可以用樹形結(jié)構(gòu)來表示,由于大部分的算術(shù)運算符有兩個操作數(shù),所以可用二叉樹來表示個算術(shù)表達式,表達式樹中并無括號,但其結(jié)構(gòu)卻有效地表達了其運算符間的運算次序。另外,利用二叉樹的遍歷等操作,還可得到表達式的三種不同的表示形式:前綴表達式、中綴表達式、后綴表達式,并可以實現(xiàn)表達式的求值運算第6章樹和二叉樹6.1應(yīng)用實例實例三:等價類劃分問題等價關(guān)系是現(xiàn)實世界中廣泛存在的一種關(guān)系,許多應(yīng)用問題可歸結(jié)為按給定的等價關(guān)系將集合劃分為等價類的問題。問題可描述為:若月是集合S上的一個等價關(guān)系,則由阿可得到集合S的唯一劃分,即可以按R將S劃分為若干個不相交的子集S,S2,…,這些子集的并集等于S,子集S稱為s的R等價類實例四:N皇后問題N皇后問題要求在一個MN格的棋盤上放置N個皇后,使其互不攻擊。按規(guī)則,互不攻擊的約束條件為:任意兩個皇后不能處于同一行、同一列或同一對角線上,現(xiàn)要求給出滿足約束條件的所有棋盤布局。第6章樹和二叉樹6.1應(yīng)用實例實例一:數(shù)據(jù)壓縮問題在信息傳輸、數(shù)據(jù)壓縮問題中,我們總是希望找到一種編碼能將待處理數(shù)據(jù)壓縮得盡可能的短。實例二:表達式的樹形表示任意一個表達式,均可以用樹形結(jié)構(gòu)來表示,由于大部分的算術(shù)運算符有兩個操作數(shù),所以可用二叉樹來表示個算術(shù)表達式,表達式樹中并無括號,但其結(jié)構(gòu)卻有效地表達了其運算符間的運算次序。另外,利用二叉樹的遍歷等操作,還可得到表達式的三種不同的表示形式:前綴表達式、中綴表達式、后綴表達式,并可以實現(xiàn)表達式的求值運算第6章樹和二叉樹6.1應(yīng)用實例實例三:等價類劃分問題等價關(guān)系是現(xiàn)實世界中廣泛存在的一種關(guān)系,許多應(yīng)用問題可歸結(jié)為按給定的等價關(guān)系將集合劃分為等價類的問題。問題可描述為:若月是集合S上的一個等價關(guān)系,則由阿可得到集合S的唯一劃分,即可以按R將S劃分為若干個不相交的子集S,S2,…,這些子集的并集等于S,子集S稱為s的R等價類實例四:N皇后問題N皇后問題要求在一個MN格的棋盤上放置N個皇后,使其互不攻擊。按規(guī)則,互不攻擊的約束條件為:任意兩個皇后不能處于同一行、同一列或同一對角線上,現(xiàn)要求給出滿足約束條件的所有棋盤布局。第6章樹和二叉62樹的概念定義:數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R:若D為空集,則稱為空樹否則(1)在D中存在唯一的稱為根的數(shù)據(jù)元素roo(2)當(dāng)n>1時,其余結(jié)點可分為m(m>0個互不相交的有限集TT2…,Tm,其中每個子集本身又是一棵符合本定義的樹,稱為根root的子樹。第6章樹和二叉樹62樹的概念例如:A(BEF(K,L),C(G),D(H,I,J(M)))根T1第6章樹和二叉樹62樹的概念表示方法:①樹型表示defgh第6章樹和二叉樹62樹的概念表示方法:②文氏圖表示a第6章樹和二叉樹62樹的概念表示方法:③凹入表示