數據結構教案第六章

1、課程名稱數據結構教學對象新華軟工教 材數據結構（C語言）授課內容第六章 樹和二叉樹課 時2教學目的與要求了解樹、森林的定義；掌握二叉樹的定義、性質、存儲結構；掌握二叉樹的遍歷、樹和森林的存儲，哈夫曼樹的應用重點、難點重點：二叉樹相關操作難點：二叉樹的三種遍歷課 型電腦理論教學方法投影、討論、板書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務一、樹的有關概念前言： 樹型結構是一類重要的非線性數據結構。其中以樹和二叉樹最為常用；樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象的表示出來等等。一、樹的概念 樹形結構是一種重要的非線性結構，討論的是層次和

2、分支關系。樹是n個結點的有限集合，在任一棵非空樹中：（1）有且僅有一個稱為根的結點。（2）其余結點可分為個互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹，稱為根的子樹。安徽新華電腦專修學院課堂教學教案（電腦應用課使用）2 / 46教學過程設計(續(xù)表)JIACBDHGFEKLM 樹是遞歸結構，在樹的定義中又用到了樹的概念例：上面的圖是一棵樹T=A, B, C, D, E, F, G, H, I, J，K，L，MA是根，其余結點可以劃分為3個互不相交的集合： T1=B, E, F，K，L , T2=C, G , T3=D, H, I, J，M這些集合中的每一集合都本身又是一棵樹，它們是A

3、的子樹。 例如 對于 T11，B是根，其余結點可以劃分為2個互不相交的集合： T11=E，K，L，T12=F，T11,T12 是B 的子樹。從邏輯結構看：1）樹中只有根結點沒有前趨；2）除根外，其余結點都有且僅一個前趨；3）樹的結點，可以有零個或多個后繼；4）除根外的其他結點，都存在唯一條從根到該結點的路徑；5）樹是一種分枝結構 （除了一個稱為根的結點外）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼。二、樹的應用1、樹可表示具有分枝結構關系的對象例1家族族譜例2單位行政機構的組織關系2、樹是常用的數據組織形式有些應用中數據元素之間并不存在間分支結構關系，但是為了便于管理和使用數據

4、，將它們用樹的形式來組織。例3 計算機的文件系統 不論是DOS文件系統還是window文件系統，所有的文件是用樹的形式來組織的。教學過程設計(續(xù)表) 三、樹的表示1）圖示表示 2）二元組表示3）嵌套集合表示 4）凹入表示法（類似書的目錄）四、樹的 基本術語樹的結點：包含一個數據元素及若干指向子樹的分支；孩子結點：結點的子樹的根稱為該結點的孩子；雙親結點：B 結點是A 結點的孩子，則A結點是B 結點的雙親；兄弟結點：同一雙親的孩子結點；堂兄結點：同一層上結點；祖先結點: 從根到該結點的所經分支上的所有結點 子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫結點層：根結點的層定義為1；根的孩

5、子為第二層結點，依此類推；樹的深度：樹中最大的結點層結點的度：結點子樹的個數樹的度： 樹中最大的結點度。葉子結點：也叫終端結點，是度為 0 的結點；分枝結點：度不為0的結點；有序樹：子樹有序的樹，如：家族樹；無序樹：不考慮子樹的順序；森林；互不相交的樹集合；森林和樹之間的聯系是：一棵樹去掉根 ，其子樹構成一個森林；一個森林增加一個根結點成為樹。復習思考題作 業(yè)上機任務案例分析： 例1家族族譜例2單位行政機構的組織關系參考文獻課后記（或歸納小結） 本章主要介紹樹的定義，日常應用，樹的概念 ；為以后的二叉樹學習帶來好的理解課程名稱數據結構教學對象新華軟工教 材數據結構（C語言）授課內容第六章 樹和

6、二叉樹課 時2教學目的與要求了解樹、森林的定義；掌握二叉樹的定義、性質、存儲結構；掌握二叉樹的遍歷、樹和森林的存儲，哈夫曼樹的應用重點、難點重點：二叉樹相關操作難點：二叉樹的三種遍歷課 型電腦理論教學方法投影、討論、板書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務一、樹的有關概念（續(xù)） 復習上一次的內容，然后提出問學生，接著從上一次內容進入今天新的課程，讓課程內容的完整性五、樹的基本操作樹的應用很廣，應用不同基本操作也不同。下面列舉了樹的一些基本操作：1）initiate (T); T 樹的初始化，包括建樹。2） root (T); 求T 樹的根。3）parent (T

7、 , x ): 求T 樹中 x 結點的雙親結點。4）Child (T, x, i )： 求 T 樹中 x 結點的第 i 個孩子結點。安徽新華電腦專修學院課堂教學教案（電腦應用課使用）教學過程設計(續(xù)表) 5）right_sibling (T, x ): 求T 樹中 x 結點的右兄弟6）insert_Child (y, i, x ): 將根為 x 的子樹置為 y 結點的第 i 個孩子7） del_child (x, i); 刪除 x 結點的第i 個孩子 8）traverse (T); 遍歷T樹。按某個次序依次訪問樹中每一個結點，并使每個結點都被訪問且只被訪問一次。9）clear (T); 置空T

8、 樹任務二、二 叉 樹 樹是一種分枝結構的對象，在樹的概念中，對每一個結點孩子的個數沒有限制，因此樹的形態(tài)多種多樣，本章我們主要討論一種最簡單的樹二叉樹一、二叉樹的概念 A F G E D C B二叉樹： 或為空樹，或由根及兩顆不相交的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹。說明1）二叉樹中每個結點最多有兩顆子樹；二叉樹每個結點度小于等于2;2）左、右子樹不能顛倒有序樹;3）二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念;二、二叉樹的基本形態(tài)(a) 空樹(b) 僅有根(c) 右子樹空(d) 左、右子樹均在(e) 左子樹空三、應用舉例 教學過程設計(續(xù)表)例1 可以用二叉樹表示

9、表達式 a+b*(c-d)-e/f例2 雙人比賽的所有可能的結局 開局連贏兩局或五局三勝四、 二叉樹性質性質1 在二叉樹的第i 層上最多有2i-1個結點性質2 深度為k的二叉樹最多有 2k-1 個結點性質3 設二叉樹葉子結點數為n0，度為2的結點n2，則n0 = n2 +1 此三個性質是對任何一棵二叉樹都實用的復習思考題作 業(yè)上機任務案例分析： 例1 ：已知二叉樹有50個葉子結點，則該二叉樹的總結點數是多少（99） 例2：已知完全二叉樹的第七層有8個結點，則其葉子結點數是（36）參考文獻課后記（或歸納小結） 本章主要介紹二叉樹的定義，二叉樹的五種形態(tài)、還有它的性質，并舉例說明這些性質課程名稱數

10、據結構教學對象新華軟工教 材數據結構（C語言）授課內容第六章 樹和二叉樹課 時2教學目的與要求了解樹、森林的定義；掌握二叉樹的定義、性質、存儲結構；掌握二叉樹的遍歷、樹和森林的存儲，哈夫曼樹的應用重點、難點重點：二叉樹相關操作難點：二叉樹的三種遍歷課 型電腦理論教學方法投影、討論、板書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務二、二 叉 樹（續(xù)） 復習上一次的內容，然后提問學生，接著從上一次內容進入今天新的課程，讓課程內容的完整性滿二叉樹：如果深度為k的二叉樹，有2k-1個結點則稱為滿二叉樹。完全二叉樹：如果深度為k的二叉樹，有2k-1個結點則稱為滿二叉樹；對其中的結

11、點的編號：根的號為1，從上到下，從左到右每個結點依次加1為其編號且一一對應，稱之為完全二叉樹。下面是兩個關于完全二叉樹的性質：性質4 ：具有n個結點的完全二叉樹的深度為：trunc(log2 n)+1. trunc(x)為取整函數。安徽新華電腦專修學院課堂教學教案（電腦應用課使用）教學過程設計(續(xù)表) 對完全二叉樹的結點編號：從上到下，每一層從左到右性質5：在完全二叉樹中編號為i的結點1）若有左孩子，則左孩編號為2i2）若有右孩子，則右孩子結點編號為2i+13）若有雙親，則雙親結點編號為trunc(i/2)三二叉樹存貯結構1、二叉樹的順序結構滿二叉樹或完全二叉樹的順序結構：用一組連續(xù)的內存單元

12、，按編號順序依次存儲完全二叉樹的元素.例如，用一維數組bt 存放一棵完全二叉樹，將標號為 i 的結點的數據元素存放在分量 bti-1中。存儲位置隱含了樹中的關系，樹中的關系是通過完全二叉樹的性質實現的。例如，bt5（i=6)的雙親結點標號是k=trunc(i/2)=3,雙親結點所對應的數組分量btk-1=bt2非完全二叉樹的順序結構：按完全二叉樹的形式補齊二叉樹所缺少的那些結點，對二叉樹結點編號,將二叉樹原有的結點按編號存儲到內存單元“相應”的位置上。但這種方式對于畸形二叉樹，浪費較大空間。2、 二叉鏈表二叉鏈表中每個結點包含三個域：數據域、左指針域、右指針域 ；圖見課件 Struct nod

13、e int data; struct node *lch,*rch;注：在含有n個結點的二叉鏈表中有n+1個空鏈域，這在線索二叉樹中將利用到這些空的鏈域3、三叉鏈表三叉鏈表中每個結點包含四個域：數據域、雙親指針域、左指針域、右指針域 Struct node int data; struct node *lch,*rch,*parent;見課件和筆記復習思考題作 業(yè)上機任務案例分析： 例：給一個二叉樹畫這棵樹的順序存儲和二叉鏈表的存儲形式，另給一個順序的存儲形式來畫出這棵二叉樹參考文獻課后記（或歸納小結） 本章主要介紹完全二叉樹和滿二叉樹的定義，還有它的兩個性質；然后介紹二叉樹的存儲形式：順序，

14、二叉鏈表，三叉鏈表的形式課程名稱數據結構教學對象新華軟工教 材數據結構（C語言）授課內容第六章 樹和二叉樹課 時2教學目的與要求了解樹、森林的定義；掌握二叉樹的定義、性質、存儲結構；掌握二叉樹的遍歷、樹和森林的存儲，哈夫曼樹的應用重點、難點重點：二叉樹相關操作難點：二叉樹的三種遍歷課 型電腦理論教學方法投影、討論、板書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務三、二叉樹的遍歷 復習上一次的內容，然后提問學生，接著從上一次內容進入今天新的課程，讓課程內容的完整性一、二叉樹的遍歷方法遍歷：按某種搜索路徑訪問二叉樹的每個結點，而且每個結點僅被訪問一次。訪問：含義很廣，可以是

15、對結點的各種處理，如修改結點數據、輸出結點數據。 遍歷是各種數據結構最基本的操作，許多其他的操作可以在遍歷基礎上實現。 二叉樹由根、左子樹、右子樹三部分組成 二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹安徽新華電腦專修學院課堂教學教案（電腦應用課使用）教學過程設計(續(xù)表) 令：L：遍歷左子樹 T：訪問根結點 R：遍歷右子樹 有六種遍歷方法： T L R，L T R，L R T， T R L，R T L，R L T先序遍歷（T L R） 若二叉樹非空 （1）訪問根結點； （2）先序遍歷左子樹； （3）先序遍歷右子樹；例：先序遍歷右圖所示的二叉樹 （1）訪問根結點A （2）先序遍歷左子樹

16、：即按 T L R 的順序遍歷左子樹（3）先序遍歷右子樹：即按 T L R 的順序遍歷右子樹中序遍歷（L T R）若二叉樹非空（1）中序遍歷左子樹（2）訪問根結點（3）中序遍歷右子樹例：中序遍歷右圖所示的二叉樹 （1）中序遍歷左子樹：即按 L T R 的順序遍歷左子樹 （2）訪問根結點A （3）中序遍歷右子樹：即按 L T R 的順序遍歷右子樹后序遍歷（L R T）若二叉樹非空（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問根結點例：后序遍歷右圖所示的二叉樹 （1）后序遍歷左子樹：即按 L R T 的順序遍歷左子樹 （2）后序遍歷右子樹：即按 L R T 的順序遍歷右子樹 （3）訪問根結點A

17、畫一個二叉樹然后寫出它的先序遍歷，中序遍歷，后序遍歷復習思考題作 業(yè)上機任務案例分析： 例：畫一個二叉樹然后寫出它的先序遍歷，中序遍歷，后序遍歷參考文獻課后記（或歸納小結） 本章主要介紹二叉樹三種遍歷方法，先序、中序、后序課程名稱數據結構教學對象新華軟工教 材數據結構（C語言）授課內容第六章 樹和二叉樹課 時2教學目的與要求了解樹、森林的定義；掌握二叉樹的定義、性質、存儲結構；掌握二叉樹的遍歷、樹和森林的存儲，哈夫曼樹的應用重點、難點重點：二叉樹相關操作難點：二叉樹的三種遍歷課 型電腦理論教學方法投影、討論、板書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務三、二叉樹的遍

18、歷 復習上一次的內容，然后提問學生，接著從上一次內容進入今天新的課程，讓課程內容的完整性一、遍歷的遞歸算法先序遍歷（T L R）的定義：若二叉樹非空 （1）訪問根結點； （2）先序遍歷左子樹 （3）先序遍歷右子樹；上面先序遍歷的定義等價于：若二叉樹為空，結束 基本項（也叫終止項）若二叉樹非空 遞歸項安徽新華電腦專修學院課堂教學教案（電腦應用課使用）教學過程設計(續(xù)表) （1）訪問根結點； （2）先序遍歷左子樹（3）先序遍歷右子樹；1、先序遍歷遞歸算法  void prev (NODE *root) if (root!=NULL) printf(“%d,”, root->data

19、)； prev(root->lch); prev(root->rch); 先序序列為 + * a b c / d e稱為前綴表達式2、中序遍歷遞歸算法 void mid (NODE *root) if (root!=NULL) prev(root->lch); printf(“%d,”, root->data)； prev(root->rch); 中序序列為 a * b c+ d / e稱為中綴表達式3、 后序遍歷遞歸算法 void prev (NODE *root) if (root!=NULL) prev(root->lch); pr

20、ev(root->rch); printf(“%d,”, root->data)； 后序序列為 a b c * d e / + 稱為后綴表達式教學過程設計(續(xù)表)三、 二叉樹遍歷的非遞歸算法遞歸算法邏輯清晰、易懂，但在實現時，由于函數調用棧層層疊加，效率不高，故有時考慮非遞歸算法。 1、先序遍歷（T L R）的非遞歸算法。 對每個結點，在訪問完后，沿其左鏈一直訪問下來，直到左鏈為空，這時，所有已被訪問過的結點進棧。然后結點出棧，對于每個出棧結點，即表示該結點和其左子樹已被訪問結束，應該訪問該結點的右子樹。（1）當前指針指向根結點。（2）打印當前結點，當前指針指向其左孩子并進棧，重復

21、（2），直到左孩子為NULL（3）依次退棧，將當前指針指向右孩子（4）若棧非空或當前指針非NULL，執(zhí)行（2）；否則結束。先序遍歷的非遞歸算法void prev (NODE *root) NODE *p, *nodeMAX; int top=0; p=root; do while( p!=NULL) printf(“%d,”, root->data) ; nodetop=p;top+; p=p->lch; if (top>0) top - -; p=nodetop; p=p->rch; while(top>0|p!=NULL); 2、先序遍歷（T L R）的非遞歸

22、算法。中序遍歷的非遞歸算法void min (NODE *root) NODE *p, *nodeMAX; int top=0; p=root; do while( p!=NULL) nodetop=p;top+;p=p->lch; if (top>0) top - -; p=nodetop; printf(“%d,”, root->data) ; p=p->rch; while(top>0|p!=NULL); 復習思考題作 業(yè)上機任務案例分析： 例：畫遞歸圖，例見筆記參考文獻課后記（或歸納小結） 本章主要介紹二叉樹三種遍歷方法，先序、中序、后序的遞歸的算法和非遞

23、歸的算法課程名稱數據結構教學對象新華軟工教 材數據結構（C語言）授課內容第六章 樹和二叉樹課 時2教學目的與要求了解樹、森林的定義；掌握二叉樹的定義、性質、存儲結構；掌握二叉樹的遍歷、樹和森林的存儲，哈夫曼樹的應用重點、難點重點：二叉樹相關操作難點：二叉樹的三種遍歷課 型電腦理論教學方法投影、討論、板書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務四、樹和森林（續(xù)）4、孩子兄弟表示法 用二叉鏈表作為樹的存貯結構。鏈表的兩個指針域分別指向該結點的第一個孩子結點和右邊下一個兄弟結點。struct node char data; struct node *son, * brot

24、her;這種形式的存儲和前面介紹的二叉鏈表存儲二叉樹的形式是一樣，所以在這里就可以通過這種存儲方法作為中間量，可以讓我們樹轉換二叉樹二、樹與二叉樹的轉換二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，可導出樹與安徽新華電腦專修學院課堂教學教案（電腦應用課使用）教學過程設計(續(xù)表) 二叉樹之間的轉換。樹與二叉樹轉換方法：二叉樹根結點 X 的左孩子結點 X 的右孩子樹根結點 X 的第一個孩子結點 X 緊鄰的右兄弟用例子說明： 如何把一棵樹轉換成二叉樹四、森林：樹的集合將森林中樹的根看成兄弟，可用樹孩子兄弟表示法存儲森林；用樹與二叉樹的轉換方法，進行森林與二叉樹轉換；從樹的二叉鏈表示的定義可知,任何

25、一棵和樹對應的二叉樹,其右子樹必為空。所以只要將森林中所有樹的根結點視為兄弟，即將各個樹轉換為二叉樹；再按森林中樹的次序，依次將后一個樹作為前一棵樹的右子樹，并將第一棵樹的根作為目標樹的根，就可以將森林轉換為二叉樹。轉換規(guī)則：若 F = T1，T2，T3，Tn 是森林，則 B（F）=root,LB,RB（1）若 F 為空，即 n=0，則 B(F)為空樹。（2）若 F 非空，則 B（F）的根是T1的根，其左子樹為LB，是從T1根結點的子樹森林F1=T11，T12，T1m轉換而成的二叉樹；其右子樹為RB，是從除T1外的森林F=T2，T3，Tn轉換而成的二叉樹；二叉樹還原為森林轉換規(guī)則：若 B（F）

26、=root,LB,RB是一棵二叉樹，則轉換為森林F = T1，T2，Tn 的規(guī)則為（1）若 B 為空，則 F 為空樹。（2）若 B 非空，則 F 第一棵樹T1的根是二叉樹的根，T1中根結點的子森林F1是由B的左子樹LB轉換而成的森林，F中除T1外其余樹組成的森林F=T2，T3，Tn是由B（F）的右子樹RB轉換轉換而成的；用例子說明如何把一棵樹轉換成二叉樹，再者如何把森林轉換成二叉樹，然后再來逆轉復習思考題作 業(yè)上機任務案例分析： 例：用例子說明如何把一棵樹轉換成二叉樹，再者如何把森林轉換成二叉樹，然后再來逆轉參考文獻課后記（或歸納小結） 本章主要介紹樹和二叉樹的轉換，森林和二叉樹的轉換等等課程

27、名稱數據結構教學對象新華軟工教 材數據結構（C語言）授課內容第六章 樹和二叉樹課 時2教學目的與要求了解樹、森林的定義；掌握二叉樹的定義、性質、存儲結構；掌握二叉樹的遍歷、樹和森林的存儲，哈夫曼樹的應用重點、難點重點：二叉樹相關操作難點：二叉樹的三種遍歷課 型電腦理論教學方法投影、討論、板書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務四、樹和森林（續(xù)）4、孩子兄弟表示法 用二叉鏈表作為樹的存貯結構。鏈表的兩個指針域分別指向該結點的第一個孩子結點和右邊下一個兄弟結點。struct node char data; struct node *son, * brother;這種

28、形式的存儲和前面介紹的二叉鏈表存儲二叉樹的形式是一樣，所以在這里就可以通過這種存儲方法作為中間量，可以讓我們樹轉換二叉樹二、樹與二叉樹的轉換二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，可導出樹與安徽新華電腦專修學院課堂教學教案（電腦應用課使用）教學過程設計(續(xù)表) 二叉樹之間的轉換。樹與二叉樹轉換方法：二叉樹根結點 X 的左孩子結點 X 的右孩子樹根結點 X 的第一個孩子結點 X 緊鄰的右兄弟用例子說明： 如何把一棵樹轉換成二叉樹四、森林：樹的集合將森林中樹的根看成兄弟，可用樹孩子兄弟表示法存儲森林；用樹與二叉樹的轉換方法，進行森林與二叉樹轉換；從樹的二叉鏈表示的定義可知,任何一棵和樹對應

29、的二叉樹,其右子樹必為空。所以只要將森林中所有樹的根結點視為兄弟，即將各個樹轉換為二叉樹；再按森林中樹的次序，依次將后一個樹作為前一棵樹的右子樹，并將第一棵樹的根作為目標樹的根，就可以將森林轉換為二叉樹。轉換規(guī)則：若 F = T1，T2，T3，Tn 是森林，則 B（F）=root,LB,RB（1）若 F 為空，即 n=0，則 B(F)為空樹。（2）若 F 非空，則 B（F）的根是T1的根，其左子樹為LB，是從T1根結點的子樹森林F1=T11，T12，T1m轉換而成的二叉樹；其右子樹為RB，是從除T1外的森林F=T2，T3，Tn轉換而成的二叉樹；二叉樹還原為森林轉換規(guī)則：若 B（F）=root,

30、LB,RB是一棵二叉樹，則轉換為森林F = T1，T2，Tn 的規(guī)則為（1）若 B 為空，則 F 為空樹。（2）若 B 非空，則 F 第一棵樹T1的根是二叉樹的根，T1中根結點的子森林F1是由B的左子樹LB轉換而成的森林，F中除T1外其余樹組成的森林F=T2，T3，Tn是由B（F）的右子樹RB轉換轉換而成的；用例子說明如何把一棵樹轉換成二叉樹，再者如何把森林轉換成二叉樹，然后再來逆轉復習思考題作 業(yè)上機任務案例分析： 例：用例子說明如何把一棵樹轉換成二叉樹，再者如何把森林轉換成二叉樹，然后再來逆轉參考文獻課后記（或歸納小結） 本章主要介紹樹和二叉樹的轉換，森林和二叉樹的轉換等等課程名稱數據結構

31、教學對象新華軟工教 材數據結構（C語言）授課內容第六章 樹和二叉樹課 時2教學目的與要求了解樹、森林的定義；掌握二叉樹的定義、性質、存儲結構；掌握二叉樹的遍歷、樹和森林的存儲，哈夫曼樹的應用重點、難點重點：二叉樹相關操作難點：二叉樹的三種遍歷課 型電腦理論教學方法投影、討論、板書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務五、樹的應用（哈夫曼樹以及應用）一、 哈夫曼樹的概念路徑：從一個結點到另一個結點之間的若干個分支路徑長度：路徑上的分支數目稱為路徑長度；結點的路徑長度：從根到該結點的路徑長度樹的路徑長度：樹中所有葉子結點的路徑長度之和；一般記為PL。在結點數相同的條件

32、下，完全二叉樹是路徑最短的二叉樹。結點的權：根據應用的需要可以給樹的結點賦權值；結點的帶權路徑長度：從根到該結點的路徑長度與該結點權的乘積；樹的帶權路徑長度=樹中所有葉子結點的帶權路徑之和；通常記作 WPL= å wi ´ Li 哈夫曼樹：假設有n個權值(w1 , w2 , , wn )，構造有n個葉子結點的嚴格二叉樹，每個葉子結點有一個 wi 作為它的權值。則帶權路徑長度最小的嚴格二叉樹稱為哈夫曼樹。用例子說明，哈夫曼樹優(yōu)點安徽新華電腦專修學院課堂教學教案（電腦應用課使用）教學過程設計(續(xù)表)二、 應用舉例在求得某些判定問題時，利用哈夫曼樹獲得最佳判定算法。例 編制一個將百分制轉換成五分制的程序。 最直觀的方法是利用if語句來的實現?？捎枚鏄涿枋雠卸ㄟ^程。設有10000個百分制分數要轉換，設學生成績在5個等級以上的分布如下059：0.05；6069：0.1