【正文】 序遍歷 、 中序遍歷 和 后序遍歷 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 72/82 先序遍歷 √訪問根結(jié)點(diǎn) √先序遍歷左子樹 √先序遍歷右子樹 A T X C Z Y B P 深度為 4的二叉樹 A 遍歷結(jié)果： T B Z X C P Y 因?yàn)樽笞訕淇眨时闅v右子樹 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 73/82 中序 遍歷 √中序遍歷左子樹 √訪問根結(jié)點(diǎn) √中序遍歷右子樹 A T X C Z Y B P 深度為 4的二叉樹 A T Z B C X Y P 因?yàn)樽笞訕淇? 遍歷結(jié)果： 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 74/82 √后序遍歷左子樹 √后序遍歷右子樹 √訪問根結(jié)點(diǎn) 后序 遍歷 A T X C Z Y B P 深度為 4的二叉樹 遍歷結(jié)果： 的二叉樹A T Z B C X Y P 因?yàn)樽笞訕淇眨时闅v右子樹 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 75/82 典型算法 對(duì)非數(shù)值型數(shù)據(jù)通常有插入 、 刪除 、 查找和排序等操作 。 其中 查找 和排序 是數(shù)據(jù)處理中比較重要的算法 。 查找 又稱 檢索 ， 是指在數(shù)據(jù)集合中查找某個(gè)數(shù)據(jù)元素的過程 。 若存在這樣數(shù)據(jù)元素 ,則查找成功；否則 ， 查找失敗 。 查找 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 76/82 1 順序查找 適用于線性表，其基本方法是 ： ? 從線性表中第一個(gè)元素開始 ， 依次將線性表中的元素與給定值進(jìn)行比較 。 ? 若相等 ， 則查找成功； ? 若直到最后一個(gè)元素 ， 還沒找到與給定值相等的元素 ， 則查找失敗 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 77/82 例如： 在順序表 ( 88, 15, 23, 80, 63, 8, 86, 46, 71, 101 )中 , 查找 值為 71的數(shù)據(jù)元素 。 ?從線性表中第一個(gè)元素 88開始 , 依次將 線性表中元素與 71進(jìn)行比較 。 ?直到第九個(gè)元素為 71, 查找成功。 特點(diǎn)：順序查找算法簡(jiǎn)單 ,但是執(zhí)行效率較低 在下列兩種情況下 ,只能使用順序查找法： ① 線性表是線性鏈表。 ② 線性表是順序表，但表中元素?zé)o序排列。 此題比較了 9次 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 78/82 2 二分查找 又稱 折半查找 , 要求 被查找的表采用順序存儲(chǔ)結(jié)構(gòu)且數(shù)據(jù)元素按數(shù)據(jù)值升序或降序排列 , 即二分查找法只適用于 有序表 。 基本思想是 (設(shè)順序表升序排列 )： ?將給定值與 中間位臵 元素比較 ,若相等 ,則 查找成功； ?若給定值小于元素值 ,則繼續(xù)對(duì)前半部分 再進(jìn)行折半查找； ?若給定值大于中間位臵元素值 ,則繼續(xù)對(duì)后半部分再進(jìn)行折半查找 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 79/82 例：在 有序順序表 (8， 15， 23， 46， 63， 71，80， 86， 88， 101)中 ， 用折半查找法查找值為 71 的數(shù)據(jù)元素 。 key=71 8 15 23 46 63 71 80 86 88 101 1 2 3 4 5 6 7 8 9 10 第一次查找 mid=5 第二次查找 mid=8 第三次查找 mid=6 71 80 86 88 101 6 7 8 9 10 6371,故在后半部分進(jìn)行折半查找 8671,故在前半部分進(jìn)行折半查找 71 80 6 7 71=71,查找成功 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 80/82 排序是將一組無序數(shù)據(jù)按值遞增(或遞減 )進(jìn)行重新排列。 三 類基本排序方法 交換排序法 選擇排序法 插入排序法 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 81/82 1交換排序法 在排序過程中 , 通過數(shù)據(jù)元素之間不斷地進(jìn)行 比較 與 交換 , 最終達(dá)到排序目的。 冒泡排序法 的基本思想是： 對(duì)所有 相鄰 元素進(jìn)行比較，若 逆順 ，則將其交換，最終達(dá)到有序化。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 82/82 交換排序法 原序列： 42 23 16 47 11 45 13 49 42 23 16 47 11 45 13 49 第 1 遍 第 2遍 第 3遍 第 4遍 第 5遍 第 6遍 23 16 42 11 45 47 13 49 16 23 11 42 45 13 47 49 16 23 11 42 45 13 47 49 11 23 16 13 45 42 47 49 11 13 16 23 45 42 47 49 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 83/82 2選擇排序法 簡(jiǎn)單選擇排序法 的基本思想是： 1掃描整個(gè)序列 ， 從中選出最小元素 ， 將它 交換到最前面； 2再從剩余子序列中 ， 選出最小元素 ， 交換 到子序列最前面 。 3依次類推 ， 直到子序列長(zhǎng)度為 1為止 。 每次從 待 排序數(shù)據(jù)序列中 ， 選擇出 最小 元素并定位到待排序 (升序 )序列最前面 。 由于每遍掃描只能確定一個(gè)元素位臵 ， 所以對(duì)于長(zhǎng)度為 n的序列 ， 需要掃描 n1遍才能將每個(gè)元素位臵確定下來 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 84/82 原序列： 42 23 16 27 11 45 13 49 選擇排序法 第 1遍選擇 42 23 16 27 11 45 13 49 11 23 16 27 42 45 13 49 第 2遍選擇 11 13 16 27 42 45 23 49 第 3遍選擇 11 13 16 27 42 45 23 49 第 4遍選擇 11 13 16 23 42 45 27 49 第 5遍選擇 11 13 16 23 27 45 42 49 第 6遍選擇 11 13 16 23 27 42 45 49 第 7遍選擇 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 85/82 3插入排序法 插入排序是不斷地將待排序的元素插入到前面的有序序列中 , 直至所有元素都進(jìn)入有序序列 。 簡(jiǎn)單插入排序 又稱 直接 插入排序 ,基本思想是：將由 n個(gè)元素組成的序列分成前后兩個(gè)子序列 , 前者為 有序序列 , 后者為 無序序列 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 86/82 ① 將待排序序列中第一個(gè)元素作為有序序列 ， 將第二個(gè)元素插入到有序序列中 ，形成由兩個(gè)元素組成的有序序列 。 ② 再將第三個(gè)元素插入到有序序列中 。 依此類推 ， 直到最后一個(gè)元素插入到有序序列中 ， 形成 n個(gè)元素組成的有序序列 。 簡(jiǎn)單插入排序的步驟： 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 吉林大學(xué)公共計(jì)算機(jī)教學(xué)與研究中心制作 87/82 插入排序法 原序列： 42 23 16 27 11 45 13 49 第 1遍 23 42 16 27 11 45 13 49 第 2遍 16 23 42 27 11 45 13 49 第 3遍 16 23 27 42 11 45 13 49 第 4遍 11 16 23 27 42 45 13 49 第 5遍 11 16 23 27 42 45 13 49 第 6遍 11 16 23 27 42 45 49 13 第 7遍 13 16 23 27 42 45 49 11