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

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