3.5二叉樹教學(xué)設(shè)計人教-中圖版高中信息技術(shù)選擇性必修1

第3章數(shù)據(jù)結(jié)構(gòu)基本類型3.5二叉樹教學(xué)設(shè)計教學(xué)背景信息科技是現(xiàn)代科學(xué)技術(shù)領(lǐng)域的重要部分，主要研究以數(shù)字形式表達的信息及其應(yīng)用中的科學(xué)原理、思維方法、處理過程和工程實現(xiàn)。當代高速發(fā)展的信息科技對全球經(jīng)濟、社會和文化發(fā)展起著越來越重要的作用。義務(wù)教育信息科技課程具有基礎(chǔ)性、實踐性和綜合性，為高中階段信息技術(shù)課程的學(xué)習(xí)奠定基礎(chǔ)。信息科技課程旨在培養(yǎng)科學(xué)精神和科技倫理，提升自主可控意識，培育社會主義核心價值觀，樹立總體國家安全觀，提升數(shù)字素養(yǎng)與技能。教材分析本節(jié)課的教學(xué)內(nèi)容選自人教/地圖出版社選擇性必修1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)第3章數(shù)據(jù)結(jié)構(gòu)基本類型3.5二叉樹。戲曲是中國傳統(tǒng)藝術(shù)瑰寶之一，在中華民族的歷史長河中綻放著奪目光彩。中國戲曲不但種類繁多有趣，表演形式也是集“唱、念、做、打”于一體，精彩絕倫。面對不同戲曲劇種及其發(fā)展歷程、藝術(shù)特色、戲曲行當和各式臉譜等紛繁復(fù)雜的要素，如何才能盡快抓住諸要素之間的關(guān)系并讀懂戲曲這門藝術(shù)呢？在計算機中，數(shù)據(jù)元素并不是孤立、雜亂無序的，而是相互之間存在著某種聯(lián)系。分析它們的特性及之間存在的關(guān)系，把數(shù)據(jù)組織為合理的結(jié)構(gòu)，正是學(xué)習(xí)與研究數(shù)據(jù)結(jié)構(gòu)的意義所在。數(shù)據(jù)結(jié)構(gòu)不但在計算機原理、操作系統(tǒng)、算法與程序設(shè)計中有著重要應(yīng)用，而且在現(xiàn)實社會的學(xué)習(xí)與生活中也隨處可見。學(xué)習(xí)應(yīng)用數(shù)據(jù)結(jié)構(gòu)，結(jié)合問題需求進行抽象，可以降低問題解決方案的復(fù)雜度。例如，在了解戲曲藝術(shù)時，分析、挖掘戲曲諸要素之間關(guān)系的基本類型，將對讀懂戲曲藝術(shù)起到事半功倍的作用。本章將以主題項目“數(shù)解傳統(tǒng)戲曲”開展學(xué)習(xí)，通過體驗探索戲曲要素中蘊含的數(shù)據(jù)結(jié)構(gòu)類型，理解基本數(shù)據(jù)結(jié)構(gòu)的概念。編寫程序?qū)崿F(xiàn)數(shù)據(jù)結(jié)構(gòu)的基本操作，進一步理解抽象數(shù)據(jù)類型對于數(shù)據(jù)處理的重要意義，深入體會數(shù)據(jù)結(jié)構(gòu)的實際應(yīng)用。學(xué)情分析此節(jié)課針對的對象是高二年級的學(xué)生。學(xué)生學(xué)習(xí)過信息技術(shù)基礎(chǔ)知識，對計算機、網(wǎng)絡(luò)、物聯(lián)網(wǎng)等技術(shù)有基本了解:已經(jīng)學(xué)習(xí)了Python語言的基本概念，并掌握了基本的結(jié)構(gòu)和算法;對現(xiàn)代生活中的信息系統(tǒng)有所觀察和積累。圍繞主題“數(shù)解傳統(tǒng)戲曲”，從日常生活與學(xué)習(xí)中的現(xiàn)象出發(fā)，探索基本數(shù)據(jù)結(jié)構(gòu)類型的本質(zhì)，并在此基礎(chǔ)上總結(jié)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用規(guī)律，利用規(guī)律創(chuàng)新使用數(shù)據(jù)結(jié)構(gòu)，完成項目報告。教學(xué)目標1.了解二叉樹的概念和特點，并能結(jié)合實例進行分析。2.了解二叉樹的基本操作方法，感受二叉樹組織數(shù)據(jù)的高效性。教學(xué)重點與難點教學(xué)重點:了解二叉樹的概念和特點，并能結(jié)合實例進行分析。教學(xué)難點:了解二叉樹的基本操作方法，感受二叉樹組織數(shù)據(jù)的高效性。教學(xué)方法與教學(xué)手段案例分析法、講授法、任務(wù)驅(qū)動法。教學(xué)過程問題導(dǎo)入體驗探索行當分支，支支精彩“生、旦、凈、丑”是京劇的四個角色行當（圖3.5.1）（參見教材P95），每個行當又有若干分支，各有固定的扮演人物和表演特色。例如，“生”可分為老生、小生、武生等；“旦”可分為青衣、花旦、老旦、武旦等；“凈”可分為正凈、副凈、武凈等；“丑”可分為文丑、武丑等。思考：能否利用線性結(jié)構(gòu)表示行當間的關(guān)系？說明原因，并用分支圖表示行當間的關(guān)系。二叉樹的概念線性表、棧、隊列和字符串均屬于線性結(jié)構(gòu)，用來表達數(shù)據(jù)元素之間一對一的關(guān)系。然而，日常生活中很多數(shù)據(jù)元素之間的關(guān)系往往不是簡單的線性關(guān)系，而是更為復(fù)雜的結(jié)構(gòu)，如人類社會中的族譜、各種社會組織機構(gòu)、交通道路和通信網(wǎng)絡(luò)等。思考活動數(shù)的分類在數(shù)學(xué)中，數(shù)可以分為實數(shù)和虛數(shù)，實數(shù)可分為有理數(shù)和無理數(shù)，有理數(shù)又可分為整數(shù)和分數(shù)......思考：1.如圖3.5.2（參見教材P96）所示的數(shù)的分類的分支圖有什么特點？2.該分支圖與本節(jié)體驗探索中的行當分支圖有何異同？如圖3.5.2（參見教材P96）所示的結(jié)構(gòu)稱為樹形結(jié)構(gòu)。樹形結(jié)構(gòu)的基本術(shù)語樹形結(jié)構(gòu)的節(jié)點包含數(shù)據(jù)元素的值及指向其子樹的分支，節(jié)點擁有的分支數(shù)稱為節(jié)點的度。在圖3.5.3（參見教材P96）中共有6個節(jié)點，它們是A、B、C、D、E、F，其中，A節(jié)點共有2個分支，故A節(jié)點的度為2；B節(jié)點共有2個分支，故B節(jié)點的度為2；C節(jié)點只有1個分支，故C節(jié)點的度為1。樹形結(jié)構(gòu)中，節(jié)點的度的最大值稱為樹的度。圖3.5.3所示的樹的度為2。度為0的節(jié)點稱為終端節(jié)點或葉節(jié)點。例如，在圖3.5.4中，節(jié)點H、I、E、J、G均為終端節(jié)點。度不為0的節(jié)點稱為非終端節(jié)點或分支節(jié)點，除根節(jié)點以外的分支節(jié)點也稱為內(nèi)部節(jié)點。例如，在圖3.5.4（參見教材P97）中，節(jié)點A、B、C、D、F均為非終端節(jié)點，其中B、C、D、F均為內(nèi)部節(jié)點。二叉樹的定義二叉樹是n（n≥0且為整數(shù)）個節(jié)點的有限集，n=0時為空樹。在任意一棵非空二叉樹中有且僅有一個特定的稱為根的節(jié)點。當n＞1時，除根節(jié)點外的所有節(jié)點可分為兩個互不相交的有限集，分別稱為根的左子樹和右子樹，左子樹和右子樹也是二叉樹，如圖3.5.5（參見教材P97）所示。某節(jié)點的子樹的根稱為該節(jié)點的孩子，該節(jié)點稱為孩子的雙親，同一雙親的孩子之間互稱兄弟。例如，在圖3.5.5（參見教材P97）中，A是B、C的雙親，B、C是A的孩子，B、C互為兄弟。節(jié)點的層次從根開始定義，根為第一層，根的孩子為第二層，以此類推。若某節(jié)點在第L層，則其孩子就在第L+1層。二叉樹中節(jié)點的最大層數(shù)稱為二叉樹的深度或高度，圖3.5.6（參見教材P98）中樹的深度為3。二叉樹的特點二叉樹具有如下特點：二叉樹中不存在度大于2的節(jié)點。在二叉樹中，每個節(jié)點最多有兩棵子樹，沒有子樹或只有一棵子樹都是允許的。二叉樹的子樹有左右之分，且次序不能顛倒。若二叉樹只有一棵子樹，也需要明確它是左子樹還是右子樹。根據(jù)二叉樹的定義可知，二叉樹的子樹也是二叉樹。由此可以推出，非空二叉樹存在4種基本形態(tài)，如圖3.5.7（參見教材P98）所示，只有一個根節(jié)點（a）、根節(jié)點只有左子樹（b）、根節(jié)點只有右子樹（c）、根節(jié)點既有左子樹又有右子樹（d）。在一棵二叉樹中，若每一個分支節(jié)點都存在左、右子樹，且所有的葉節(jié)點均在同一層上，這棵二叉樹稱為滿二叉樹，如圖3.5.8（參見教材P98）所示。對于如圖3.5.8（參見教材P98）所示的滿二叉樹，可將所有節(jié)點按照“從上到下、同層從左到右”的次序從1開始連續(xù)編號，如圖3.5.9（參見教材P98）所示。按從大到小的順序連續(xù)刪除該滿二叉樹的若干節(jié)點后剩下的二叉樹稱為完全二叉樹，如圖3.5.10（參見教材P98）所示。實踐活動了解二叉樹的結(jié)構(gòu)圖3.5.11中，二叉樹的根是哪個節(jié)點？哪些節(jié)點是葉節(jié)點？二叉樹的深度是多少？哪些節(jié)點有子樹？節(jié)點B的子樹有幾棵？節(jié)點E的雙親節(jié)點、孩子節(jié)點、兄弟節(jié)點分別是哪些節(jié)點？二叉樹的基本操作二叉樹的基本操作包括構(gòu)造空二叉樹、查找二叉樹中的某個節(jié)點、刪除二叉樹中的某個節(jié)點和遍歷二叉樹等，而二叉樹的很多操作都以遍歷二叉樹為前提和基礎(chǔ)。思考活動游覽動物園某動物園有9個館舍，館舍之間的道路有8條，動物園的出入口在長頸鹿館處，如圖3.5.12（參見教材P99）所示。思考：如何規(guī)劃一條能將每個館舍都游遍且每個館舍僅游覽一次的路線？二叉樹的遍歷指從根節(jié)點出發(fā)，按照某種次序依次訪問二叉樹中的所有節(jié)點，使得每個節(jié)點僅被訪問一次。根據(jù)前面的學(xué)習(xí)可知，一棵非空二叉樹由根節(jié)點、左子樹和右子樹構(gòu)成，因此，遍歷二叉樹需要完成三項工作：訪問根節(jié)點、遍歷左子樹和遍歷右子樹。如果規(guī)定先遍歷左子樹，再遍歷右子樹，則二叉樹的遍歷方法有三種，分別稱為先根序遍歷、中根序遍歷和后根序遍歷。下面，以圖3.5.13（參見教材P100）中的表達式二叉樹為例進行說明。實踐活動解決游覽動物園館舍問題學(xué)習(xí)二叉樹的遍歷后，我們就可解決上文中提出的“如何規(guī)劃一條能將每個館舍都游遍且每個館舍僅游覽一次的路線”的問題了。將動物園的館舍抽象為節(jié)點，節(jié)點之間的路徑抽象為邊，請用二叉樹表示動物園的館舍分布圖。用、☆和△三種符號分別標記出先根序、中根序和后根序遍歷時各節(jié)點的訪問順序，如圖3.5.17（參見教材P102）所示。請按照符號提示，寫出遍歷動物園館舍的三種訪問序列。項目實施總結(jié)表達一、項目活動1.根據(jù)圖3.5.18（參見教材P102）中的提示，補充完善項目主題內(nèi)容與基本數(shù)據(jù)結(jié)構(gòu)的對應(yīng)關(guān)系。2.總結(jié)二叉樹的定義、基本術(shù)語、遍歷方式及生活中的應(yīng)用實例，并繪制思維導(dǎo)圖。二、項目檢查1.分析二叉樹的特點、應(yīng)用范圍，總結(jié)線性結(jié)構(gòu)與非線性結(jié)構(gòu)的區(qū)別，并繪制數(shù)據(jù)結(jié)構(gòu)思維導(dǎo)圖。2.完成階段性項目學(xué)習(xí)報告并上傳至班級共享空間。總結(jié)評價1.總結(jié)本章的核心概念與關(guān)鍵能力。2.根據(jù)自己的掌握情況填寫下表。學(xué)習(xí)內(nèi)容掌握程度線性表的基本概念□不了解□了解□理解棧的基本概念□不了解□了解□理解隊列的基本概念□不了解□了解□理解字符串的基本概念□不了解□了解□理解二叉樹的基本概念□不了解□了解□理解線性表、棧、隊列、字符串和二叉樹的基本操作□不了解□了解□理解編程實現(xiàn)線性表、棧、隊列和字符串的基本操作□不了解□了解□理解結(jié)合實際發(fā)現(xiàn)現(xiàn)實生活中的數(shù)據(jù)結(jié)構(gòu)□不了解□了解□理解在生活中運用數(shù)據(jù)結(jié)構(gòu)□不了解□了解□理解課后作業(yè)1.根據(jù)定義，找出圖3.5.19中的二叉樹2.某二叉樹有3個節(jié)點，兩位同學(xué)就這棵二叉樹的形態(tài)產(chǎn)生了爭執(zhí)，一位同學(xué)認為該二叉樹的形態(tài)如圖3.5.20（a），另一位同學(xué)則認為該二叉樹的形態(tài)如圖3.5.20（b）。