教案紙（首頁）第1頁第次課學(xué)時(shí)授課時(shí)間___________教學(xué)主題樹的基本定義和性質(zhì)；樹的遍歷方法和存儲(chǔ)結(jié)構(gòu)；教學(xué)要求1、掌握樹的定義及其邏輯結(jié)構(gòu)特性，數(shù)組抽象數(shù)據(jù)類型的描述方法。2、掌握樹的邏輯結(jié)構(gòu)表示方法和樹的性質(zhì)。3、掌握樹的遍歷方法和樹的存儲(chǔ)結(jié)構(gòu)。4、掌握棧在實(shí)際求解問題中的應(yīng)用方法。教學(xué)重點(diǎn)樹的遞歸特點(diǎn)；樹的性質(zhì)、樹的遍歷和樹的存儲(chǔ)結(jié)構(gòu)教學(xué)難點(diǎn)樹的性質(zhì)、樹的遍歷和樹的存儲(chǔ)結(jié)構(gòu)。教學(xué)方法講授教學(xué)手段多媒體、板書講授要點(diǎn)1、樹的邏輯結(jié)構(gòu)特性及樹抽象數(shù)據(jù)類型的描述。2、樹的邏輯表示方法及樹的基本術(shù)語。3、樹的性質(zhì)。4、樹的遍歷方法。5、樹的存儲(chǔ)結(jié)構(gòu)。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記7.1樹的概念樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)，正如在課前思考題所看到的，樹型結(jié)構(gòu)廣泛用于描述家族譜系以及其它社會(huì)組織結(jié)構(gòu)。在計(jì)算機(jī)領(lǐng)域中，如編譯程序中的語法結(jié)構(gòu)和數(shù)據(jù)庫中的信息組織也都需要借用樹來描述。本章將討論樹和二叉樹兩種樹型結(jié)構(gòu)。1、樹的定義樹：T={D，R}。D是包含n個(gè)結(jié)點(diǎn)的有限集合（n≥0）。當(dāng)n=0時(shí)為空樹，否則關(guān)系R滿足以下條件:有且僅有一個(gè)結(jié)點(diǎn)d0∈D，它對(duì)于關(guān)系R來說沒有前驅(qū)結(jié)點(diǎn)，結(jié)點(diǎn)d0稱作樹的根結(jié)點(diǎn)。除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。D中每個(gè)結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。2、樹的邏輯表示屬性表示法文氏圖表示法凹入表示法括號(hào)表示法3、樹的基本術(shù)語結(jié)點(diǎn)的度與樹的度：樹中一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。樹中各結(jié)點(diǎn)的度的最大值稱為樹的度，通常將度為m的樹稱為m次樹或者m叉樹。分支結(jié)點(diǎn)與葉結(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)或葉結(jié)點(diǎn)（或葉子結(jié)點(diǎn)）。度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)，又叫分支結(jié)點(diǎn)。度為1的結(jié)點(diǎn)稱為單分支結(jié)點(diǎn)；度為2的結(jié)點(diǎn)稱為雙分支結(jié)點(diǎn)，依此類推。路徑與路徑長度：兩個(gè)結(jié)點(diǎn)di和dj的結(jié)點(diǎn)序列（di，di1，di2，…，dj）稱為路徑。其中<dx，dy>是分支。路徑長度等于路徑所通過的結(jié)點(diǎn)數(shù)目減1（即路徑上分支數(shù)目或邊的數(shù)目）。孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)：在一棵樹中，每個(gè)結(jié)點(diǎn)的后繼，被稱作該結(jié)點(diǎn)的孩子結(jié)點(diǎn)（或子女結(jié)點(diǎn)）。相應(yīng)地，該結(jié)點(diǎn)被稱作孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)（或父母結(jié)點(diǎn)）。具有同一雙親的孩子結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。子孫結(jié)點(diǎn)和祖先結(jié)點(diǎn)：在一棵樹中，一個(gè)結(jié)點(diǎn)的所有子樹中的結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。從根結(jié)點(diǎn)到達(dá)一個(gè)結(jié)點(diǎn)的路徑上經(jīng)過的所有結(jié)點(diǎn)被稱作該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。結(jié)點(diǎn)的層次和樹的高度：樹中的每個(gè)結(jié)點(diǎn)都處在一個(gè)層次上。結(jié)點(diǎn)的層次從樹根開始定義，根結(jié)點(diǎn)為第1層，它的孩子結(jié)點(diǎn)為第2層，以此類推，一個(gè)結(jié)點(diǎn)所在的層次為其雙親結(jié)點(diǎn)所在的層次加1。樹中結(jié)點(diǎn)的最大層次稱為樹的高度（或樹的深度）。有序樹和無序樹：若樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，且相對(duì)次序是不能隨意變換的，則稱為有序樹，否則稱為無序樹。有序樹和無序樹：若樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，且相對(duì)次序是不能隨意變換的，則稱為有序樹，否則稱為無序樹。4、樹的性質(zhì)性質(zhì)1樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)之和加1。性質(zhì)2度為m的樹中第i層上至多有mi-1個(gè)結(jié)點(diǎn)（i≥1）。性質(zhì)3高度為h的m次樹至多有個(gè)結(jié)點(diǎn)。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的m次樹的最小高度為logm(n(m-1)+1)。5、樹的基本運(yùn)算樹的運(yùn)算主要分為三大類：查找滿足某種特定關(guān)系的結(jié)點(diǎn)，如查找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等。插入或刪除某個(gè)結(jié)點(diǎn)，如在樹的當(dāng)前結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)等。遍歷樹中每個(gè)結(jié)點(diǎn)。6、樹的遍歷樹的遍歷運(yùn)算是指按某種方式訪問樹中的每一個(gè)結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)只被訪問一次。主要遍歷方法：先根遍歷，若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。后跟遍歷，若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。層次遍歷，若樹不空，則自上而下、自左至右訪問樹中每個(gè)結(jié)點(diǎn)。7、樹的存儲(chǔ)結(jié)構(gòu)雙親存儲(chǔ)typedefstruct{ElemTypedata; //結(jié)點(diǎn)的值intparent; //指向雙親的位置}PTree[MaxSize];孩子鏈存儲(chǔ)結(jié)構(gòu)typedefstructnode{ElemTypedata; //結(jié)點(diǎn)的值structnode*sons[MaxSons]; //指向孩子結(jié)點(diǎn)}TSonNode;孩子兄弟鏈存儲(chǔ)typedefstructtnode{ElemTypedata; //結(jié)點(diǎn)的值structtnode*hp; //指向兄弟structtnode*vp; //指向孩子結(jié)點(diǎn)}TSBNode;教學(xué)總結(jié)：本章節(jié)介紹了樹的基本定義，樹的邏輯結(jié)構(gòu)，樹的性質(zhì)以及樹的存儲(chǔ)結(jié)構(gòu)。

第次課學(xué)時(shí)授課時(shí)間__________教學(xué)主題二叉樹教學(xué)要求1、掌握二叉樹的定義及其性質(zhì)。2、掌握二叉樹與樹、森林之間的轉(zhuǎn)換。教學(xué)重點(diǎn)二叉樹與樹、森林之間的轉(zhuǎn)換方法；二叉樹的遞歸特點(diǎn)、二叉樹的性質(zhì)和二叉樹的兩種存儲(chǔ)結(jié)構(gòu)。教學(xué)難點(diǎn)二叉樹與樹、森林之間的轉(zhuǎn)換方法；二叉樹的遞歸特點(diǎn)、二叉樹的性質(zhì)和二叉樹的兩種存儲(chǔ)結(jié)構(gòu)。5、完全二叉樹和滿二叉樹的特點(diǎn)。教學(xué)方法講授教學(xué)手段多媒體、板書講授要點(diǎn)1、二叉樹的遞歸定義和二叉樹的性質(zhì)。2、完全二叉樹和滿二叉樹的特點(diǎn)。3、二叉樹與樹、森林之間的轉(zhuǎn)換方法。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記7.2二叉樹的概念和性質(zhì)二叉樹的定義二叉樹是有限的結(jié)點(diǎn)集合。這個(gè)集合或者是空(稱為空二叉樹)?；蛘哂梢粋€(gè)根結(jié)點(diǎn)和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。二叉樹的結(jié)構(gòu)特點(diǎn)：每個(gè)結(jié)點(diǎn)最多只有兩棵子樹，即結(jié)點(diǎn)的度不大于2子樹有左右之分，子樹的次序(位置)不能顛倒即使結(jié)點(diǎn)只有一顆子樹，也有左右之分兩種特殊的二叉樹滿二叉樹:若二叉樹中所有的分支結(jié)點(diǎn)的度數(shù)都為2，且葉子結(jié)點(diǎn)都在同一層次上，則稱這類二叉樹為滿二叉樹。完全二叉樹:假如一棵包含n個(gè)結(jié)點(diǎn)的二叉樹中每個(gè)結(jié)點(diǎn)都可以和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一、一對(duì)應(yīng)，則稱這類二叉樹為完全二叉樹。3、二叉樹的性質(zhì)性質(zhì)1非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。即：n0=n2+1。性質(zhì)2非空二叉樹上第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。性質(zhì)3高度為h的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)（h≥1）。性質(zhì)4完全二叉樹性質(zhì)（含n個(gè)結(jié)點(diǎn)）：n1=0或者n1=1。n1可由n的奇偶性確定。若i≤n/2，則編號(hào)為i的結(jié)點(diǎn)為分支結(jié)點(diǎn)，否則為葉結(jié)點(diǎn)。4、二叉樹與樹、森林之間的轉(zhuǎn)換森林、樹轉(zhuǎn)換成二叉樹二叉樹還原為森林、樹教學(xué)總結(jié)：本章節(jié)主要介紹了二叉樹的定義，二叉樹的性質(zhì)，兩種特殊的二叉樹以及二叉樹與樹、森林之間的轉(zhuǎn)換。第次課學(xué)時(shí)授課時(shí)間___________教學(xué)主題二叉樹的兩種存儲(chǔ)結(jié)構(gòu)；二叉樹的基本運(yùn)算算法設(shè)計(jì)教學(xué)要求1、掌握二叉樹的兩種存儲(chǔ)結(jié)構(gòu)。2、掌握二叉樹的基本運(yùn)算算法設(shè)計(jì)。教學(xué)重點(diǎn)二叉樹的兩種存儲(chǔ)結(jié)構(gòu)；二叉樹的基本運(yùn)算算法教學(xué)難點(diǎn)二叉樹的存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)；二叉樹的基本運(yùn)算算法教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、上機(jī)實(shí)操講授要點(diǎn)1、二叉樹的兩種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。2、二叉樹的基本運(yùn)算算法設(shè)計(jì)方法。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記二叉樹的存儲(chǔ)結(jié)構(gòu)1、二叉樹的順序存儲(chǔ)結(jié)構(gòu)用數(shù)組實(shí)現(xiàn)特點(diǎn)：對(duì)于完全二叉樹來說，其順序存儲(chǔ)是十分合適的。在順序存儲(chǔ)結(jié)構(gòu)中，找一個(gè)結(jié)點(diǎn)的雙親和孩子都很容易。2、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用二叉鏈表實(shí)現(xiàn)特點(diǎn)：除了指針外，二叉鏈比較節(jié)省存儲(chǔ)空間。在二叉鏈中，找一個(gè)結(jié)點(diǎn)的孩子很容易，但找其雙親不方便。二叉樹的基本運(yùn)算及其實(shí)現(xiàn)1、二叉樹的基本運(yùn)算創(chuàng)建二叉樹CreateBTree(*b，*str)：根據(jù)二叉樹括號(hào)表示法字符串str生成對(duì)應(yīng)的二叉鏈存儲(chǔ)結(jié)構(gòu)b。銷毀二叉鏈存儲(chǔ)結(jié)構(gòu)DestroyBTree(*b)：銷毀二叉鏈b并釋放空間。查找結(jié)點(diǎn)FindNode(*b，x)：在二叉樹b中尋找data域值為x的結(jié)點(diǎn)，并返回指向該結(jié)點(diǎn)的指針。找孩子結(jié)點(diǎn)LchildNode(p)和RchildNode(p)：分別求二叉樹中結(jié)點(diǎn)p的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。求高度BTHeight(*b)：求二叉樹b的高度。若二叉樹為空，則其高度為0；否則，其高度等于左子樹與右子樹中的最大高度加l。輸出二叉樹DispBTree(*b)：以括號(hào)表示法輸出一棵二叉樹。2、二叉樹的基本運(yùn)算的實(shí)現(xiàn)通過例子具體講解采用二叉鏈表的存儲(chǔ)方式對(duì)二叉樹的基本運(yùn)算算法設(shè)計(jì)實(shí)現(xiàn)。例子：將二叉樹的二叉鏈結(jié)點(diǎn)類型及其基本運(yùn)算函數(shù)存儲(chǔ)在btree.cpp文件中。#include"btree.cpp" //包含二叉樹的基本運(yùn)算函數(shù)voidmain(){BTNode*b,*p;CreateBTree(b,"A(B(D(,G)),C(E,F))");printf("b:");DispBTree(b);printf("\n");printf("b的高度:%d\n",BTHeight(b));p=FindNode(b,'F');if(p!=NULL)printf("b中存在F結(jié)點(diǎn)\n");elseprintf("b中不存在F結(jié)點(diǎn)\n");DestroyBTree(b);}第次課學(xué)時(shí)授課時(shí)間___________教學(xué)主題二叉樹的遍歷教學(xué)要求1、掌握二叉樹的遍歷過程。2、掌握遍歷二叉樹的算法設(shè)計(jì)及其應(yīng)用。教學(xué)重點(diǎn)二叉樹的遍歷過程；遍歷二叉樹的算法及其應(yīng)用教學(xué)難點(diǎn)遍歷二叉樹的算法和對(duì)遞歸的理解教學(xué)方法講授+練習(xí)教學(xué)手段多媒體、上機(jī)實(shí)操講授要點(diǎn)1、二叉樹的遍歷過程。2、二叉樹的先序、中序和后序遍歷遞歸和非遞歸算法設(shè)計(jì)及其應(yīng)用。3、二叉樹的層次遍歷算法設(shè)計(jì)及其應(yīng)用。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記二叉樹的遍歷"遍歷"的含義是對(duì)結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素都訪問一次且僅僅訪問一次。因此進(jìn)行遍歷應(yīng)該確定一條搜索路徑，使得結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素都出現(xiàn)在這條搜索路徑上，才能確保每個(gè)數(shù)據(jù)元素都被訪問到。由于二叉樹中每個(gè)結(jié)點(diǎn)都有兩個(gè)后繼，則可以有三條搜索路徑：

1)先左(子樹)后右(子樹)；

2)先右(子樹)后左(子樹)；

3)按層次從上到下。

按層次從上到下的遍歷比較簡單，先訪問第一層的結(jié)點(diǎn)(即根結(jié)點(diǎn))，再訪問第二層，第三層，…，直到最后一層，對(duì)每一層的結(jié)點(diǎn)則從左到右，即"先被訪問的父結(jié)點(diǎn)的孩子結(jié)點(diǎn)"先于"后被訪問的父結(jié)點(diǎn)的孩子結(jié)點(diǎn)"進(jìn)行訪問。例如，下列所示二叉樹進(jìn)行"按層次遍歷"時(shí)，對(duì)結(jié)點(diǎn)訪問的先后次序?yàn)椋篈BCDEFGHIJ。

1)和2)兩條搜索路徑相互對(duì)稱，故以下重點(diǎn)討論先左后右的遍歷。先左后右的遍歷從二叉樹的結(jié)構(gòu)定義得知，二叉樹是由"根結(jié)點(diǎn)"、"左子樹"和"右子樹"三部分構(gòu)成，則遍歷二叉樹的操作可分解為"訪問根結(jié)點(diǎn)"、"遍歷左子樹"和"遍歷右子樹"三個(gè)子操作，并且由二叉樹的遞歸定義可知，遍歷左子樹和遍歷右子樹可如同遍歷二叉樹一樣"遞歸"進(jìn)行。因此整個(gè)遍歷的操作只要在一條搜索路徑上一次完成這三個(gè)子操作即可。

下圖所示為對(duì)二叉樹進(jìn)行遍歷的先左后右的搜索路徑。從圖可得知兩個(gè)結(jié)論：1)由于左右子樹互不相交，因此對(duì)左子樹的遍歷一定不會(huì)訪問到右子樹上的結(jié)點(diǎn)，反之對(duì)右子樹的遍歷也一定不會(huì)訪問到左子樹，因此沿這條搜索路徑必可實(shí)現(xiàn)對(duì)二叉樹中每個(gè)結(jié)點(diǎn)都訪問到且只訪問一次；2)也正由于左右子樹不相交，因此在遍歷了左子樹之后必須回到根結(jié)點(diǎn)才能繼續(xù)遍歷右子樹。由此可見，在這條搜索路徑上從進(jìn)入二叉樹到離開二叉樹，一共三次遇到根結(jié)點(diǎn)，因此訪問根結(jié)點(diǎn)的操作可在任意一次也只能在其中一次進(jìn)行。由此得到以下三個(gè)遍歷二叉樹的算法：

先序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹若二叉樹為空，則空操作；

否則

(1)訪問根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)中序遍歷左子樹；

(2)訪問根結(jié)點(diǎn)；

(3)中序遍歷右子樹。若二叉樹為空，則空操作；

否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。按照遍歷過程中先后訪問的次序?qū)⒍鏄渲械慕Y(jié)點(diǎn)排列起來分別得到二叉樹的先序序列、中序序列和后序序列。由以上遍歷算法的定義很容易寫出對(duì)應(yīng)的遞歸算法。voidPreorder(BiTreeT，void(*visit)(BiTree))

{

//先序遍歷以T為根指針的二叉樹

if(T){//T=NULL時(shí)，二叉樹為空樹，不做任何操作

visit(T);//通過函數(shù)指針*visit訪問根結(jié)點(diǎn)

Preorder(T->Lchild,visit);//先序遍歷左子樹

Preorder(T->Rchild,visit);//先序遍歷右子樹

}//}二叉樹遍歷算法的應(yīng)用例7-11統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)

容易想到，實(shí)現(xiàn)這個(gè)操作只要對(duì)二叉樹"遍歷"一遍，并在遍歷過程中對(duì)"葉子結(jié)點(diǎn)計(jì)數(shù)"即可。顯然這個(gè)遍歷的次序可以隨意，即先序或中序或后序均可，只是為了在遍歷的同時(shí)進(jìn)行計(jì)數(shù)，需要在算法的參數(shù)中設(shè)一個(gè)"計(jì)數(shù)器"。intNodes(BTNode*b){if(b==NULL)return0;elsereturnNodes(b->lchild)+Nodes(b->rchild)+1}例7-13假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法Level()求二叉樹b中值為x的結(jié)點(diǎn)的層次（假設(shè)所有結(jié)點(diǎn)值唯一）intLevel(BTNode*b，ElemTypex，inth)//找到p結(jié)點(diǎn)后h為其層次，否則為0{intL;if(b==NULL)return0; //空樹時(shí)返回0elseif(b->data==x)returnh; //找到結(jié)點(diǎn)時(shí)else{L=Level(b->lchild，x，h+1); //在左子樹中查找if(L==0) //左子樹中未找到時(shí)在右子樹中查找returnLevel(b->rchild，x，h+1); elsereturnL;}}

第次課學(xué)時(shí)授課時(shí)間___________教學(xué)主題哈夫曼樹和哈夫曼編碼的構(gòu)造過程及其特點(diǎn)教學(xué)要求1、掌握二叉樹的構(gòu)造過程。2、掌握哈夫曼樹和哈夫曼編碼的構(gòu)造過程。教學(xué)重點(diǎn)哈夫曼樹的特點(diǎn)、哈夫曼樹構(gòu)造過程；哈夫曼編碼的特點(diǎn)、哈夫曼編碼構(gòu)造過程教學(xué)難點(diǎn)哈夫曼樹構(gòu)造過程；哈夫曼編碼構(gòu)造過程教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、上機(jī)實(shí)操講授要點(diǎn)1、二叉樹的構(gòu)造過程。2、哈夫曼樹和哈夫曼編碼的構(gòu)造過程及其特點(diǎn)。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）教學(xué)內(nèi)容備注與后記哈夫曼樹和哈夫曼編碼最優(yōu)樹，又稱哈夫曼樹（HuffmanTree）是一類帶權(quán)路徑長度最短的樹，本節(jié)僅限于討論最優(yōu)二叉樹。

首先介紹路徑和路徑長度的概念。由從樹的根結(jié)點(diǎn)到其余結(jié)點(diǎn)的分支構(gòu)成一條路徑，路徑上的分支數(shù)目稱路徑長度。一般情況下，樹的路徑長度指的是從樹根到樹中其余每個(gè)結(jié)點(diǎn)的路徑長度之和。

結(jié)點(diǎn)的帶權(quán)路徑長度則定義為從樹根到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)上所帶權(quán)值的乘積。假設(shè)樹上有n個(gè)葉子結(jié)點(diǎn)，且每個(gè)葉子結(jié)點(diǎn)上帶有權(quán)值為Wk(k=1,2,…,n)，則樹的帶權(quán)路徑長度定義為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記作

其中

lk為帶權(quán)Wk的葉子結(jié)點(diǎn)的帶權(quán)路徑長度。

假設(shè)有n個(gè)權(quán)值{w1，w2，…wn}，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi。顯然，這樣的二叉樹可以構(gòu)造出多棵，其中必存在一棵帶權(quán)路徑長度WPL取最小的二叉樹，稱該二叉樹為最優(yōu)二叉樹。例如，右圖中的四棵二叉樹，都有5個(gè)葉子結(jié)點(diǎn)且?guī)嗤瑱?quán)值5、6、2、9、7，它們的帶權(quán)路徑長度分別為

WPL=73+93+52+62+22=74(左上圖)

WPL=21+63+74+94+52=94(右上圖)

WPL=62+72+53+23+92=65(左下圖)

WPL=21+53+73+93+63=83(右下圖)

其中以左下圖中二叉樹的帶權(quán)路徑長度為最小?？梢则?yàn)證，它恰為最優(yōu)二叉樹，即在所有葉子結(jié)點(diǎn)帶權(quán)為5、6、2、9、7的二叉樹中，帶權(quán)路徑長度的最小值為65。最優(yōu)樹的構(gòu)造方法

哈夫曼最早給出了一個(gè)構(gòu)造最優(yōu)樹的帶有一般規(guī)律的算法，俗稱哈夫曼算法?，F(xiàn)以最優(yōu)二叉樹為例敘述如下：

(1)根據(jù)給定的n個(gè)權(quán)值{w1,w2,…wn}，構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}，