資源簡介

教學設計
課程基本信息
課題 樹與二叉樹
教學目標
1.了解樹、子樹、樹的度、樹的深度等概念。 2.了解二叉樹、滿二叉樹、完全二叉樹等概念。
教學內容
教學重點： 1.樹、二叉樹的概念。
2.樹、二叉樹的特點和性質。 教學難點： 1.樹的特點。 2.二叉樹的兩種分類和三種性質。
教學過程
問題導入：生活中的樹可以抽象成邏輯上的樹 在日常生活中，常見的樹形結構有：1.公司組織架構 2.知識點匯總 3.動物分類等，這些樹形結構的共同特征是：都呈現一對多的非線性關系 樹的概念與特點 1.樹的定義：樹是一種非線性數據結構，是有 n（n>=0）個節點的有限集合 2.空樹：n=0 的樹稱為空樹 3.當n>0時，n個節點的樹有n-1條邊 4.子樹：樹中某個節點下面的所有節點所構成的樹 5.度：節點的度：節點所擁有的子樹個數 樹的度：最大的節點的度（樹的寬度） 6.高度：（或深度）樹中節點的最大層數 7.節點：根節點：（開始節點）沒有前驅的節點 葉子節點：（終端節點）沒有后繼，度為0的節點 分支節點：度不為0的節點 內部節點：除根節點外的分支節點 父節點：兩個以邊直接連接的節點，上端節點是下端節點的父節點或雙親節點 孩子節點：下端節點是上端節點的孩子節點 兄弟節點: 擁有同一個父節點的同層節點 【學習任務一】 填一填：
1.該樹有___個節點，____條邊，該樹的度是_____,高度是_____ 2.該樹的葉子節點是___________________,內部節點是_____________________ 3.度為1的節點數有_____個，B的孩子節點是_______,Q的兄弟節點是_____ 答案：1. 12 11 3 6 2.E F Z P C H B G R Q D 3. 3 E F G P 猜數游戲：小明寫了一個100以內的正整數，讓小紅猜；小紅每猜一次，小明會告訴她“猜大了”還是“猜小了”，直到猜出正確的結果。請問小紅采用什么方法，能用最少的次數猜出正確結果？ 答：用折半猜數法，猜數過程如下，進一步引入二叉樹 二叉樹的概念 二叉樹是一個具有 n（n>=0）個節點的有限集合。當 n=0時，二叉樹是一棵空樹； 當 n>0時，則是由根節點、左子樹和右子樹組成；由于左、右子樹也是二叉樹，因此子樹也可以是空樹。二叉樹的特征：所有節點的度都小于等于2。二叉樹的5種不同形態如下圖： 【學習任務二】 畫一畫：有3個節點的二叉樹有幾種不同的形態？（答：共5種，如下所示：） 二叉樹的分類 1.滿二叉樹 請學生觀察以下3個二叉樹的共同特點是？ 答:以上3個二叉樹的所有的葉子節點都在最底層，除了葉子節點外，每個結點的度是2 這類二叉樹稱為：滿二叉樹 2.完全二叉樹 請學生觀察以下3個二叉樹的共同特點是？ 答：以上3個二叉樹至多只有最下兩層中的節點的度數小于2，且最后一層的葉子結點都依次從左到右分布，這類二叉樹稱為：完全二叉樹 【學習任務三】 判一判：下列4個圖是否為完全二叉樹？ （答案：D） 3.滿二叉樹 VS 完全二叉樹 ①滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹 ②滿二叉樹在最后一層從最后一個節點開始，從右向左連續去掉幾個節點，即為完全二叉樹 【學習任務四】 選一選：下列哪些是滿二叉樹，哪些是完全二叉樹？ （②是滿二叉樹 ⑤是完全二叉樹） 二叉樹的性質 因為滿二叉樹在同層二叉樹中，擁有的節點數最多，我們以滿二叉樹為例來探究下 性質1：二叉樹的第k層上最多有2k-1個節點 性質2：深度為k的二叉樹最多有2k-1個節點 性質3：在任意一顆二叉樹中，度為2的節點數n2和度為0的節點數n0的關系是：n0=n2+1 【學習任務五】 請探究證明：在任意一顆二叉樹中，都滿足 n0=n2+1 推導過程如下： 節點數n滿足等式： n=n0+n1+n2 ① 邊數B滿足等式： B=n-1 ② B=n0*0+n1*1+n2*2 ③ 由①②③可推導出 n0=n2+1 課堂小結 思考與探究 已知數組a=[7,9,12,23,34,40,66]，若要查找66，請參考“折半猜數法”，用二叉樹畫出查找的過程。（參考如下：）
教學反思
通過前三章的學習，學生已全面了解了線性數據結構中的數組、鏈表、字符串、隊列和棧，對于蘊含線性結構的生活實例，可以用線性結構來存儲數據、組織數據等。但對于非線性結構的生活實例，學生僅接觸過，但并不能用樹結構描述出數據的邏輯關系。本節課的重點是了解樹、子樹、樹的度、樹的深度、二叉樹、滿二叉樹、完全二叉樹等概念，以及二叉樹的性質。大部分內容是概念性的知識，因此我結合了生活實例如公司組織架構、知識點匯總、動物分類等進行導入，輔以圖的形式，讓學生更加清晰的學習各種概念及性質。本節課的優點是概念清晰明了，教學環節緊緊相扣，教學語言自然流暢，不足之處是關于二叉樹的生活實例列舉較少。

展開更多......

收起↑