《測樹學(xué)第三章》課件

《測樹學(xué)第三章》PPT課件樹是計(jì)算機(jī)科學(xué)中一種重要的數(shù)據(jù)結(jié)構(gòu)，本章將深入討論樹及其應(yīng)用。學(xué)習(xí)樹的定義、二叉樹的遍歷、線索二叉樹等內(nèi)容，為構(gòu)建更高效的算法奠定基礎(chǔ)。樹的定義層次遍歷從樹的根節(jié)點(diǎn)開始逐層遍歷樹的節(jié)點(diǎn)。廣泛應(yīng)用于分層搜索等算法。先序遍歷先訪問根節(jié)點(diǎn)，然后遞歸地先序遍歷左子樹和右子樹。可用于復(fù)雜表達(dá)式的求值。中序遍歷先遞歸地中序遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遞歸地中序遍歷右子樹?？捎糜趯Χ嫠阉鳂溥M(jìn)行排序。后序遍歷先遞歸地后序遍歷左子樹和右子樹，最后訪問根節(jié)點(diǎn)?？捎糜谟?jì)算表達(dá)式的后綴表達(dá)式。二叉樹的定義滿二叉樹每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，除了葉子節(jié)點(diǎn)外，所有節(jié)點(diǎn)的度都是2。完全二叉樹除最后一層外，所有層的節(jié)點(diǎn)數(shù)都達(dá)到最大；在最后一層上沒有空缺。平衡二叉樹左子樹和右子樹的高度差不超過1，以提高查找、插入和刪除操作的效率。線索二叉樹1中序線索二叉樹在中序遍歷時(shí)，將二叉樹的空指針域改為指向該節(jié)點(diǎn)的中序遍歷的前驅(qū)和后繼。2先序線索二叉樹在先序遍歷時(shí)，將二叉樹的空指針域改為指向該節(jié)點(diǎn)的先序遍歷的前驅(qū)和后繼。3后序線索二叉樹在后序遍歷時(shí)，將二叉樹的空指針域改為指向該節(jié)點(diǎn)的后序遍歷的前驅(qū)和后繼。樹的表示1雙親表示法通過數(shù)組來表示每個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)的位置。2孩子表示法用數(shù)組表示每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)集合。3孩子兄弟表示法每個(gè)節(jié)點(diǎn)包括一個(gè)子節(jié)點(diǎn)和一個(gè)兄弟節(jié)點(diǎn)指針。森林的定義森林的概念由多個(gè)不相交的樹組成，每個(gè)樹稱為一棵樹。森林的表示可使用孩子兄弟表示法表示森林。常見應(yīng)用森林廣泛應(yīng)用于圖算法中，如最小生成樹和最短路徑樹的生成。并查集定義并查集是一種用于管理不相交集合的數(shù)據(jù)結(jié)構(gòu)，支持合并和查找操作。應(yīng)用并查集常用于判斷無向圖中是否存在環(huán)，等價(jià)關(guān)系的判斷等場景。操作復(fù)雜度并查集的合并和查找操作的時(shí)間復(fù)雜度均為O(α(n))，其中α(n)為阿克曼函數(shù)的反函數(shù)。哈弗曼樹1哈弗曼樹的構(gòu)建通過貪心算法逐步選擇權(quán)值最小的節(jié)點(diǎn)進(jìn)行構(gòu)建。2哈弗曼編碼將字符編碼成不等長的二進(jìn)制串，使得前綴碼不存在互相是其它碼字前綴的情況。3應(yīng)用哈弗曼樹廣泛用于數(shù)據(jù)壓縮和加密算法中。平衡二叉樹AVL樹一種高度平衡的二叉搜索樹，保證任何節(jié)點(diǎn)的左子樹和右子樹的高度差不超過1。紅黑樹具有自平衡性質(zhì)的二叉搜索樹，保證任何節(jié)點(diǎn)的左子樹和右子樹的黑色節(jié)點(diǎn)數(shù)目相等。B樹和B+樹適用于磁盤和數(shù)據(jù)庫存儲(chǔ)的平衡搜索樹，每個(gè)節(jié)點(diǎn)可包含多個(gè)鍵。Trie樹1定義一種樹形結(jié)構(gòu)，常用于字符串的存儲(chǔ)與搜索。2實(shí)現(xiàn)方法通過將字符串的字符逐層存儲(chǔ)在樹的節(jié)點(diǎn)上實(shí)現(xiàn)。3應(yīng)用舉例Trie樹可用于搜索引擎中的關(guān)鍵詞提示功能、自動(dòng)補(bǔ)全等場景。前綴樹和后綴樹1前綴樹用于查找字符串的前綴，通過將字符串的字符逐層存儲(chǔ)在樹的節(jié)點(diǎn)上實(shí)現(xiàn)。2后綴樹用于查找字符串的后綴，通過將字符串的后綴逐層存儲(chǔ)在樹的節(jié)點(diǎn)上實(shí)現(xiàn)。3常見應(yīng)用前綴樹和后綴樹主要用于字符串匹配和文本處理領(lǐng)域中的算法。最小生成樹Prim算法從一個(gè)頂點(diǎn)開始，逐步選擇與當(dāng)前生成樹連接的最小權(quán)值邊。Kr