北京信息科技大學(xué)數(shù)據(jù)機(jī)構(gòu)課件第7章

北京信息科技大學(xué)數(shù)據(jù)機(jī)構(gòu)課件第7章本章主要介紹樹(shù)和圖的相關(guān)概念和算法。內(nèi)容包括樹(shù)的存儲(chǔ)結(jié)構(gòu)、二叉樹(shù)的遍歷、線索二叉樹(shù)、二叉搜索樹(shù)以及平衡二叉樹(shù)等。樹(shù)的基本念和術(shù)語(yǔ)節(jié)點(diǎn)樹(shù)的基本單元，包含數(shù)據(jù)和指向其他節(jié)點(diǎn)的指針。根節(jié)點(diǎn)樹(shù)的頂端節(jié)點(diǎn)，沒(méi)有父節(jié)點(diǎn)。葉節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。子節(jié)點(diǎn)直接連接到父節(jié)點(diǎn)的節(jié)點(diǎn)。樹(shù)的存儲(chǔ)結(jié)構(gòu)：數(shù)組和鏈表數(shù)組使用數(shù)組來(lái)存儲(chǔ)樹(shù)的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向子節(jié)點(diǎn)的索引。鏈表使用鏈表來(lái)存儲(chǔ)樹(shù)的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向子節(jié)點(diǎn)的指針。二叉樹(shù)及其性質(zhì)1性質(zhì)一每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。2性質(zhì)二左子樹(shù)和右子樹(shù)是有序的。3性質(zhì)三二叉樹(shù)的深度不超過(guò)節(jié)點(diǎn)數(shù)減一。二叉樹(shù)的遍歷：前序、中序、后序1前序遍歷先訪問(wèn)根節(jié)點(diǎn)，然后遞歸遍歷左子樹(shù)和右子樹(shù)。2中序遍歷先遞歸遍歷左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后遞歸遍歷右子樹(shù)。3后序遍歷先遞歸遍歷左子樹(shù)和右子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)。線索二叉樹(shù)及其遍歷線索化通過(guò)改變二叉樹(shù)的空指針，存儲(chǔ)前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)的信息。中序遍歷利用線索二叉樹(shù)的線索信息，按照節(jié)點(diǎn)之間的前驅(qū)關(guān)系進(jìn)行遍歷。樹(shù)的深度和高度深度節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長(zhǎng)度。高度樹(shù)中節(jié)點(diǎn)的最大深度。二叉搜索樹(shù)特性左子樹(shù)的所有節(jié)點(diǎn)小于根節(jié)點(diǎn)，右子樹(shù)的所有節(jié)點(diǎn)大于根節(jié)點(diǎn)。查找和插入利用二叉搜索樹(shù)的有序性，快速實(shí)現(xiàn)查找和插入操作。平衡二叉樹(shù)：AVL樹(shù)和紅黑樹(shù)AVL樹(shù)通過(guò)左旋和右旋操作，保持樹(shù)的高度平衡。紅黑樹(shù)通過(guò)顏色標(biāo)記和旋轉(zhuǎn)操作，保持樹(shù)的高度平衡和節(jié)點(diǎn)的有序性。堆和堆排序堆一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，可以快速找到最值。堆排序利用堆的特性進(jìn)行排序，時(shí)間復(fù)雜度為O(nlogn)。赫夫曼樹(shù)和赫夫曼編碼1赫夫曼樹(shù)一種特殊的二叉樹(shù)，用于有效編碼。2赫夫曼編碼根據(jù)字符出現(xiàn)的頻率，生成唯一的編碼。3壓縮算法利用赫夫曼編碼，實(shí)現(xiàn)大規(guī)模文件的壓縮和解壓縮。圖的基本概念和術(shù)語(yǔ)1頂點(diǎn)圖中的節(jié)點(diǎn)，可以表示實(shí)體或位置。2邊連接兩個(gè)頂點(diǎn)的線段，表示頂點(diǎn)之間的關(guān)系。3有向圖邊有方向的圖，表示頂點(diǎn)之間的單向關(guān)系。4無(wú)向圖邊沒(méi)有方向的圖，表示頂點(diǎn)之間的雙向關(guān)系。圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表鄰接矩陣使用二維數(shù)組表示圖的鄰接關(guān)系。鄰接表使用鏈表數(shù)組表示圖的鄰接關(guān)系。圖的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索1深度優(yōu)先搜索從起始節(jié)點(diǎn)出發(fā)，沿著一條路徑遍歷到底，然后回溯繼續(xù)遍歷其他路徑。2廣度優(yōu)先搜索從起始節(jié)點(diǎn)出發(fā)，先訪問(wèn)所有鄰接節(jié)點(diǎn)，然后依次訪問(wèn)它們的鄰接節(jié)點(diǎn)。最小生成樹(shù)：Prim法和Kruskal算法Prim法從某個(gè)節(jié)