數(shù)據(jù)結(jié)構(gòu)算法之樹的應(yīng)用(已修改)
2025-05-11 08:39 本頁(yè)面
【正文】 樹的應(yīng)用 二叉樹遍歷的應(yīng)用 ? ? 2. 求二叉樹的高度 ? 3. 求葉子結(jié)點(diǎn)數(shù) 設(shè)有 100個(gè)學(xué)生某門課程的考試成績(jī)的分布如下表所示： 一、問(wèn)題的提出 (判斷樹 ) 分?jǐn)?shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績(jī)數(shù)據(jù)分布情況表 *問(wèn)題： 現(xiàn)在要編寫程序依次根據(jù)每個(gè)學(xué)生的成績(jī)打印出該學(xué)生的成績(jī)等級(jí)。 分?jǐn)?shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績(jī)數(shù)據(jù)分布情況表 方法 1： a60 打印bad yes a70 no 打印pass yes a80 no 打印general yes a90 no 打印good yes 打印excellent no 5%的學(xué)生 15%的學(xué)生 40%的學(xué)生 30%的學(xué)生 10%的學(xué)生 共做 315次比較 讀取一個(gè)學(xué)生成績(jī) → a 循環(huán)一百次 分?jǐn)?shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績(jī)數(shù)據(jù)分布情況表 方法 2： a80 打印bad yes a90 no yes no a70 yes no a60 yes no 打印“ good 打印excellent 打印pass 打印general 5%的學(xué)生 15%的學(xué)生 40%的學(xué)生 30%的學(xué)生 10%的學(xué)生 共做 220次比較 讀取一個(gè)學(xué)生成績(jī)→ a 循環(huán)一百次 思考： 如何找到一棵 最優(yōu)的 判斷樹使得編寫出來(lái)的程序的運(yùn)行時(shí)間是最高效的？ 有關(guān)概念 ① 結(jié)點(diǎn)的路徑長(zhǎng)度： 從根結(jié)點(diǎn)沿某條路徑到某結(jié)點(diǎn)途中所經(jīng)歷的邊的條數(shù)稱為該結(jié)點(diǎn)的路徑長(zhǎng)度。 二、哈夫曼樹及其應(yīng)用 ② 樹的路徑長(zhǎng)度： 從根結(jié)點(diǎn)到每一個(gè) 葉子結(jié)點(diǎn) 的路徑長(zhǎng)度之和。 ④ 樹的帶權(quán)路徑長(zhǎng)度 (WPL)： 樹中所有 葉子結(jié)點(diǎn) 的 帶權(quán)路徑長(zhǎng)度 之和稱為樹的帶權(quán)路徑長(zhǎng)度。 ③ 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度： 某結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)上的權(quán)值的乘積稱為該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。 有關(guān)概念 二、哈夫曼樹及其應(yīng)用 實(shí)例 ： 已知某二叉樹的四個(gè)葉子結(jié)點(diǎn) a,b,c,d分別帶權(quán) 7， 5， 2， 4，則
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1