數(shù)據(jù)結構與算法chapter6樹和二叉樹教學課件

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