數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 教案 -單元5樹

教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程代碼總學(xué)時(shí)64課程負(fù)責(zé)人任課教師

單元教案授課日期年月日—月日授課地點(diǎn)授課班級(jí)班級(jí)人數(shù)教學(xué)單元單元5樹教學(xué)時(shí)數(shù)10教學(xué)目標(biāo)AOB1:掌握計(jì)算機(jī)程序設(shè)計(jì)中的線性表、棧、隊(duì)列、樹和圖的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB2:掌握計(jì)算機(jī)程序設(shè)計(jì)中的線性表、棧、隊(duì)列、樹、圖的數(shù)據(jù)增、刪、改、查操作運(yùn)算。了解遞歸的處理算法。掌握選擇與排序處理算法；AOB3:掌握對(duì)算法的科學(xué)分析方法。BOB1:能根據(jù)實(shí)際問題中的數(shù)據(jù)特性選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；BOB2:設(shè)計(jì)出適當(dāng)?shù)乃惴ê统绦?。EOB1:掌握使用搜索引擎、論壇、幫助文檔、課外書籍等方法解決學(xué)習(xí)中出現(xiàn)的問題；EOB2:能主動(dòng)閱讀書后拓展知識(shí)并進(jìn)行實(shí)驗(yàn)驗(yàn)證；EOB3:能獨(dú)立分析解決問題，能把自己的想法用代碼實(shí)現(xiàn)。教學(xué)方式混合式教學(xué)評(píng)價(jià)方式課堂考勤（20%），課堂活動(dòng)參與程度（20%）線上單元測(cè)試（40%）線下課堂教學(xué)參與程度（20%）教學(xué)資源1.算法與數(shù)據(jù)結(jié)構(gòu)（Java語言描述），陳媛，清華大學(xué)大學(xué)出版社2.電腦50臺(tái)（含eclips）;3.網(wǎng)絡(luò)學(xué)習(xí)資源：/forums/ST_Arithmetic：課程平臺(tái)網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學(xué)設(shè)計(jì)第一次課（2學(xué)時(shí)）教學(xué)內(nèi)容5.1普通樹定義：樹是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合，當(dāng)n＝0時(shí)稱為空樹；否則，在任一非空樹中必有一個(gè)稱為根的結(jié)點(diǎn)；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm；其中每一個(gè)集合本身又是一棵樹，稱為根的子樹特點(diǎn)：非空樹中至少有一個(gè)根結(jié)點(diǎn)；樹中各子樹是互不相交的集合樹的表示樹的基本術(shù)語結(jié)點(diǎn)：樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向子樹的分支結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)葉子：度為0的結(jié)點(diǎn)，也叫終端結(jié)點(diǎn)分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)：除根結(jié)點(diǎn)之外，分支結(jié)點(diǎn)也稱為內(nèi)部結(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)度數(shù)結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……堂兄弟：其雙親在同一層的結(jié)點(diǎn)互稱為堂兄弟深度：樹中結(jié)點(diǎn)的最大層次數(shù)有序樹：樹中結(jié)點(diǎn)的各子樹從左至右是有序的，最左邊的子樹的根稱為第一個(gè)孩子，最右邊的稱為最后一個(gè)孩子森林：m棵互不相交的樹的集合樹的邏輯特征縱向關(guān)系：祖先與子孫是縱向次序；任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼結(jié)點(diǎn)；但至多只有一個(gè)直接前趨結(jié)點(diǎn)；葉結(jié)點(diǎn)無后繼；根結(jié)點(diǎn)無前趨橫向關(guān)系有序樹中，若k1和k2是兄弟，且k1在k2的左邊，則k1的任一子孫都在k2的任一子孫的左邊教學(xué)重點(diǎn)樹的基本術(shù)語教學(xué)難點(diǎn)無教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)講評(píng)和考勤（5分鐘）1.平臺(tái)發(fā)布任務(wù)2.考勤1.考勤講授（60分鐘）1.樹的定義（10分鐘）2.樹的表示（10分鐘）3.樹的基本術(shù)語（30分鐘）4.樹的邏輯特征（10分鐘）1.積極回答教師提問2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)課堂練習(xí)（20分鐘）1.樹形結(jié)構(gòu)（5分鐘）2.樹的基本術(shù)語（15分鐘）1.認(rèn)真思考2.積極回答問題總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習(xí)過程中出現(xiàn)的，問題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)第二次課（2學(xué)時(shí)）教學(xué)內(nèi)容二叉樹定義：二叉樹是結(jié)點(diǎn)的有限集合，或者是空樹，或者由一個(gè)根結(jié)點(diǎn)和兩棵二叉子樹構(gòu)成。左子樹，右子樹，子樹不相交特點(diǎn)：每個(gè)結(jié)點(diǎn)至多有二棵子樹；不存在度大于2的結(jié)點(diǎn)；子樹有左、右之分，次序不能任意顛倒?jié)M二叉樹深度為k的滿二叉樹，有2k-1個(gè)結(jié)點(diǎn)；2k-1是深度為K的二叉樹所具有的最大結(jié)點(diǎn)個(gè)數(shù)特點(diǎn)：每層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值；只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)均有兩棵高度相同的子樹；葉子結(jié)點(diǎn)都在樹的最下面一層上完全二叉樹葉子結(jié)點(diǎn)只出現(xiàn)在最低兩層上；對(duì)任意結(jié)點(diǎn)，若其右分支下的子孫最大層次為L(zhǎng)，則其左分支下的子孫的最大層次為L(zhǎng)或L+1；除最低層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最低層上只缺少右邊的若干結(jié)點(diǎn)(也可不缺)。二叉樹的性質(zhì)性質(zhì)1：在二叉樹第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)證明：當(dāng)i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)。顯然，2i-1＝20＝１是對(duì)的。假設(shè)對(duì)所有的j(1≤j﹤i)，命題成立。即第j層上至多有2j-1個(gè)結(jié)點(diǎn)，那么可以證明j=i時(shí)命題成立。歸納假設(shè)：第i-1層上至多有2i-2個(gè)結(jié)點(diǎn)。由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為2，故在第i層上的最大結(jié)點(diǎn)數(shù)為第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍，即2*2i-2＝2i-1。性質(zhì)2：深度為k的二叉樹至多有2k-１個(gè)結(jié)點(diǎn)(k≥1)證明：由性質(zhì)１可見，深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為：性質(zhì)3：對(duì)任意二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。證明：二叉樹中結(jié)點(diǎn)總數(shù)為：n=n0+n1+n2 (5-1)二叉樹的分支數(shù)為：n1+2*n2 (5-2)因此，結(jié)點(diǎn)總數(shù)為：n=n1+2*n2+1由(5-1)、(5-2)兩式可得：n0=n2+1性質(zhì)5：對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序號(hào)編號(hào)(從第1層到log2n+1層，每層從左到右)，則對(duì)任一結(jié)點(diǎn)i(1≤i≤n)，有：如果i=1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙親，否則，其雙親結(jié)點(diǎn)為：i/2如果2i>n，則結(jié)點(diǎn)i無左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn));否則其左孩子是結(jié)點(diǎn)2i如果2i+1>n，則結(jié)點(diǎn)i無右孩子；否則其右孩子是結(jié)點(diǎn)2i+1二叉樹的存儲(chǔ)順序存儲(chǔ)：將任意二叉樹“修補(bǔ)”成完全二叉樹；利用順序表對(duì)數(shù)據(jù)元素進(jìn)行存儲(chǔ)；原二叉樹中空缺的結(jié)點(diǎn)在數(shù)組中相應(yīng)單元置空。鏈?zhǔn)酱鎯?chǔ)：二叉鏈表：結(jié)點(diǎn)包含3個(gè)域：數(shù)據(jù)域和指向左、右子樹的指針域二叉樹的遍歷遍歷：按一定的規(guī)則和次序走遍二叉樹的所有結(jié)點(diǎn)；使每個(gè)結(jié)點(diǎn)都被訪問一次，且只被訪問一次，對(duì)結(jié)點(diǎn)進(jìn)行各種操作遍歷二叉樹的目的：遍歷是對(duì)數(shù)據(jù)進(jìn)行操作的基礎(chǔ)；得到二叉樹中各結(jié)點(diǎn)的一種線性順序；使非線性的二叉樹線性化，簡(jiǎn)化有關(guān)的運(yùn)算和處理先序遍歷，中序遍歷，后序遍歷線索二叉樹線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針稱為線索線索二叉樹：加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹教學(xué)重點(diǎn)二叉樹的遍歷教學(xué)難點(diǎn)二叉樹的性質(zhì)教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)考勤（5分鐘）1.考勤1.考勤講授（60分鐘）1.二叉樹樹的定義（10分鐘）2.二叉樹的性質(zhì)（20分鐘）3.二叉樹的存儲(chǔ)（10分鐘）4.二叉樹的遍歷（20分鐘）1.積極回答教師提問2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)課堂練習(xí)（20分鐘）1.完全二叉樹（5分鐘）2.二叉樹的遍歷（15分鐘）1.認(rèn)真思考2.積極回答問題總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務(wù)1.思考教師總結(jié)，2.記錄教師的任務(wù)要求并在課后完成。第三次課（2學(xué)時(shí)）教學(xué)內(nèi)容技能訓(xùn)練-二叉樹遍歷1.創(chuàng)建二叉樹結(jié)點(diǎn)類2.建立鏈?zhǔn)酱鎯?chǔ)二叉樹，結(jié)構(gòu)如圖。3.實(shí)現(xiàn)先序遍歷方法。4.實(shí)現(xiàn)中序遍歷方法。5.實(shí)現(xiàn)后序遍歷方法。6.測(cè)試代碼，核驗(yàn)結(jié)果。教學(xué)重點(diǎn)二叉樹遍歷的代碼實(shí)現(xiàn)教學(xué)難點(diǎn)二叉樹遍歷的代碼實(shí)現(xiàn)教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)考勤（5分鐘）1.考勤1.考勤技能訓(xùn)練（80分鐘）1.布置技能訓(xùn)練任務(wù)（5分鐘）2.在技能訓(xùn)練過程中巡視并啟發(fā)學(xué)生解決遇到的問題。1.獨(dú)立完成老師下發(fā)的課堂練習(xí)2.在遇到問題時(shí)與同學(xué)討論?？偨Y(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務(wù)1.思考教師總結(jié)，2.記錄教師的任務(wù)要求并在課后完成。第四次課（2學(xué)時(shí)）教學(xué)內(nèi)容5.3樹與二叉樹樹的存儲(chǔ)結(jié)構(gòu)二叉樹與樹的相互轉(zhuǎn)換樹轉(zhuǎn)二叉樹①加線：在兄弟之間加一連線②抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其第一孩子外，去除其與其余孩子之間的關(guān)系③旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針轉(zhuǎn)45°二叉樹轉(zhuǎn)樹①加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來②抹線：抹掉原二叉樹中雙親與右孩子之間的連線③調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)森林轉(zhuǎn)二叉樹①將各棵樹分別轉(zhuǎn)換成二叉樹②將每棵樹的根結(jié)點(diǎn)用線相連③以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)二叉樹轉(zhuǎn)森林①抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹②還原：將孤立的二叉樹還原成樹樹的遍歷先序遍歷(與對(duì)應(yīng)的二叉樹先序遍歷序列一致)。若樹非空，則：訪問根結(jié)點(diǎn)；依次先序遍歷根的各個(gè)子樹。后序遍歷(與對(duì)應(yīng)的二叉樹中序遍歷序列一致)。若樹非空，則：依次后序遍歷根的各個(gè)子樹；訪問根結(jié)點(diǎn)層次遍歷：若樹非空，訪問根結(jié)點(diǎn)。若第1，…i(i≥1)層結(jié)點(diǎn)已被訪問，且第i+1層結(jié)點(diǎn)尚未訪問，則從左到右依次訪問第i+1層。教學(xué)重點(diǎn)樹與二叉樹轉(zhuǎn)換，二叉樹與森林轉(zhuǎn)換教學(xué)難點(diǎn)樹與二叉樹轉(zhuǎn)換，二叉樹與森林轉(zhuǎn)換教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)考勤（5分鐘）1.考勤1.考勤講授（60分鐘）1.樹的存儲(chǔ)結(jié)構(gòu)（10分鐘）2.樹與二叉樹轉(zhuǎn)換（15分鐘）3.二叉樹與森林轉(zhuǎn)換（20分鐘）4.樹的遍歷（10分鐘）1.積極回答教師提問2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)課堂練習(xí)（25分鐘）1.樹轉(zhuǎn)二叉樹（5分鐘）2.二叉樹轉(zhuǎn)森林（5分鐘）3.森林轉(zhuǎn)二叉樹（5分鐘）4.樹的遍歷（10分鐘）1.認(rèn)真思考2.積極回答問題總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務(wù)1.思考教師總結(jié)，2.記錄教師的任務(wù)要求并在課后完成。第五次課（2學(xué)時(shí)）教學(xué)內(nèi)容5.4哈夫曼樹哈夫曼樹相關(guān)概念路徑：若樹中存在某個(gè)結(jié)點(diǎn)序列k1,k2,…,kj，滿足Ki是ki+1的雙親，則該結(jié)點(diǎn)序列是樹上的一條路徑，路徑自上而下地經(jīng)過了樹上的每一條邊路徑長(zhǎng)度：路徑經(jīng)過的邊數(shù)，稱為路徑長(zhǎng)度樹的路徑長(zhǎng)度：從樹根到樹中每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和，完全二叉樹的路徑長(zhǎng)度最短結(jié)點(diǎn)的權(quán)：給樹的結(jié)點(diǎn)賦以一定意義的數(shù)值，稱為結(jié)點(diǎn)的權(quán)結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從樹根到某結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的積樹的帶權(quán)路徑長(zhǎng)度（WPL）：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和哈夫曼樹：由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的二叉樹具有不同形態(tài)，其中帶權(quán)路徑長(zhǎng)度（WPL）最小的二叉樹，又叫最優(yōu)二叉樹或最佳判定樹構(gòu)造哈夫曼樹的方法，哈夫曼算法：根據(jù)給定的n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹，令其權(quán)值為分別wj；在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹；置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和；在森林中刪除這兩棵樹，并將新得到的二叉樹加入森林中；重復(fù)上述步驟，直到只含一棵樹為止，這棵樹即哈夫曼樹。哈夫曼樹的應(yīng)用最佳判定樹哈夫曼編碼電報(bào)通訊中，電文以二進(jìn)制的0,1序列傳送，發(fā)送端將電文中的字符轉(zhuǎn)換成0,1的二進(jìn)制序列，接收端將收到的0,1序列轉(zhuǎn)換成對(duì)應(yīng)的字符序列(譯碼)假定電文是英文，電文字符串由26個(gè)英文字母組成，需要編碼的字符集是{A,B,C,D,…,Z}方法一：等長(zhǎng)的二進(jìn)制編碼方法二：不等長(zhǎng)的二進(jìn)制編碼前綴碼：任一字符的編碼，不能是其他字符的前綴。假設(shè)字符集D={d1,d2,d3,…,dn}，每個(gè)字符di的編碼長(zhǎng)度為li，每個(gè)字符di在電文中出現(xiàn)的次數(shù)是ci，則電文的總長(zhǎng)度為:∑ci*li。每個(gè)字符di在電文中出現(xiàn)頻度的概率是wi，每個(gè)字符di的編碼長(zhǎng)度為li，則電文的平均總長(zhǎng)度為:∑wi*li尋找最優(yōu)前綴碼的方法用d1,d2,d3,…,dn作為葉子結(jié)點(diǎn)，用w1,w2,w3,…,wn作為葉子結(jié)點(diǎn)的權(quán)，構(gòu)造最優(yōu)二叉樹，將樹中每個(gè)結(jié)點(diǎn)的左分支置為0，右分支置為1，從根到葉子結(jié)點(diǎn)的一個(gè)標(biāo)號(hào)序列，就是該葉子結(jié)點(diǎn)的編碼。例：設(shè)組成電文的字符集D及其概率分布如下：D={a,b,c,d,e}

W={0.12,0.40,0.15,0.08,0.25}教學(xué)重點(diǎn)哈夫曼算法教學(xué)難點(diǎn)哈夫曼樹的應(yīng)用教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)考勤（5分鐘）1.考勤1.考勤講授（65分鐘）1.哈夫曼樹的概念（10分鐘）2.哈夫曼算法（20分鐘）3.哈夫曼樹的應(yīng)用（35分鐘）1.積極回答教師提問2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)課堂練習(xí)（15分鐘）1.哈夫曼樹的構(gòu)造與相關(guān)計(jì)算（15分鐘）1.認(rèn)真思考2.積極回答問題總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務(wù)1.思考教師總結(jié)，2.記錄教師的任務(wù)要求并在課后完成。教學(xué)效果與反思根