教案課程名稱數據結構與算法設計課程代碼總學時64課程負責人任課教師

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

W={0.12,0.40,0.15,0.08,0.25}教學重點哈夫曼算法教學難點哈夫曼樹的應用教學流程教學環節教師活動學生活動考勤（5分鐘）1.考勤1.考勤講授（65分鐘）1.哈夫曼樹的概念（10分鐘）2.哈夫曼算法（20分鐘）3.哈夫曼樹的應用（35分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內容3.積極參與課堂的討論和互動課堂練習（15分鐘）1.哈夫曼樹的構造與相關計算（15分鐘）1.認真思考2.積極回答問題總結與發布課后任務（5分鐘）1.總結本次課程內容；2.布置課后任務1.思考教師總結，2.記錄教師的任務要求并在課后完成。教學效果與反思根