數(shù)據(jù)結(jié)構(gòu)教案第六章

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、歷 復(fù)習(xí)上一次的內(nèi)容，然后提問學(xué)生，接著從上一次內(nèi)容進(jìn)入今天新的課程，讓課程內(nèi)容的完整性一、遍歷的遞歸算法先序遍歷（T L R）的定義：若二叉樹非空 （1）訪問根結(jié)點(diǎn)； （2）先序遍歷左子樹 （3）先序遍歷右子樹；上面先序遍歷的定義等價(jià)于：若二叉樹為空，結(jié)束 基本項(xiàng)（也叫終止項(xiàng)）若二叉樹非空 遞歸項(xiàng)安徽新華電腦專修學(xué)院課堂教學(xué)教案（電腦應(yīng)用課使用）教學(xué)過程設(shè)計(jì)(續(xù)表) （1）訪問根結(jié)點(diǎn)； （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稱為前綴表達(dá)式2、中序遍歷遞歸算法 void mid (NODE *root) if (root!=NULL) prev(root->lch); printf(“%d,”, root->data)； prev(root->rch); 中序序列為 a * b c+ d / e稱為中綴表達(dá)式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 / + 稱為后綴表達(dá)式教學(xué)過程設(shè)計(jì)(續(xù)表)三、 二叉樹遍歷的非遞歸算法遞歸算法邏輯清晰、易懂，但在實(shí)現(xiàn)時(shí)，由于函數(shù)調(diào)用棧層層疊加，效率不高，故有時(shí)考慮非遞歸算法。 1、先序遍歷（T L R）的非遞歸算法。 對(duì)每個(gè)結(jié)點(diǎn)，在訪問完后，沿其左鏈一直訪問下來，直到左鏈為空，這時(shí)，所有已被訪問過的結(jié)點(diǎn)進(jìn)棧。然后結(jié)點(diǎn)出棧，對(duì)于每個(gè)出棧結(jié)點(diǎn)，即表示該結(jié)點(diǎn)和其左子樹已被訪問結(jié)束，應(yīng)該訪問該結(jié)點(diǎn)的右子樹。（1）當(dāng)前指針指向根結(jié)點(diǎn)。（2）打印當(dāng)前結(jié)點(diǎn)，當(dāng)前指針指向其左孩子并進(jìn)棧，重復(fù)

21、（2），直到左孩子為NULL（3）依次退棧，將當(dāng)前指針指向右孩子（4）若棧非空或當(dāng)前指針非NULL，執(zhí)行（2）；否則結(jié)束。先序遍歷的非遞歸算法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); 復(fù)習(xí)思考題作 業(yè)上機(jī)任務(wù)案例分析： 例：畫遞歸圖，例見筆記參考文獻(xiàn)課后記（或歸納小結(jié)） 本章主要介紹二叉樹三種遍歷方法，先序、中序、后序的遞歸的算法和非遞

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

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

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

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

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

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

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

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

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

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