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