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

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