高中信息技術(shù)學(xué)科二叉樹遍歷題型的教學(xué)思考

高中信息技術(shù)學(xué)科二叉樹遍歷題型的教學(xué)思考摘要：《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》是浙江省高中信息技術(shù)課程的新教材，“數(shù)據(jù)結(jié)構(gòu)”對(duì)于高中生來講，屬于較難的知識(shí)模塊，其中“數(shù)據(jù)結(jié)構(gòu)”中的二叉樹的遍歷（前序遍歷、中序遍歷、后序遍歷）對(duì)于學(xué)生來講較難理解掌握，而提供前序遍歷和中序遍歷或后序遍歷與中序遍歷，求另一種遍歷這類題型對(duì)于二叉樹的遍歷學(xué)習(xí)有較大幫助。關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷數(shù)據(jù)結(jié)構(gòu)(DataStructure)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。常見的數(shù)據(jù)結(jié)構(gòu)有數(shù)組，鏈表，隊(duì)列，棧，樹，圖等。其中樹，尤其是二叉樹的遍歷是高中信息技術(shù)教學(xué)中的一個(gè)重點(diǎn)和難點(diǎn)。二叉樹是一種特殊的樹，是一個(gè)具有n個(gè)節(jié)點(diǎn)的有限集合，它的所有節(jié)點(diǎn)的度都小于或等于2。當(dāng)n等于0時(shí)，二叉樹是一棵空樹；當(dāng)n不等于0時(shí)，它是一棵由根節(jié)點(diǎn)和兩顆互不相交的，分別稱作這個(gè)根節(jié)點(diǎn)的左子樹和右子樹的二叉樹。1遍歷所謂遍歷是指對(duì)樹中所有結(jié)點(diǎn)的信息的訪問，即依次對(duì)樹中每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。樹的遍歷是樹的一種重要的運(yùn)算，從二叉樹的根節(jié)點(diǎn)出發(fā)，節(jié)點(diǎn)的遍歷分為三個(gè)主要步驟：對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行訪問操作、遍歷左邊子節(jié)點(diǎn)、遍歷右邊子節(jié)點(diǎn)。根據(jù)對(duì)根節(jié)點(diǎn)、左子樹、右子樹訪問的順序可分為前序遍歷、中序遍歷和后序遍歷。前序遍歷：訪問順序?yàn)橄仍L問根節(jié)點(diǎn)（N），再訪問左子樹（L），最后訪問右子樹(R),順序?yàn)镹LR。以一顆滿二叉樹層次遍歷順序?yàn)锳BCDEFG為例，1、先訪問根節(jié)點(diǎn)A；2、然后訪問左子樹BDE,左子樹再遍歷，先根節(jié)點(diǎn)B，然后訪問左節(jié)點(diǎn)D，最后訪問右節(jié)點(diǎn)E；3、訪問右子樹CFG，先訪問根節(jié)點(diǎn)C，再訪問左節(jié)點(diǎn)F，最后訪問右節(jié)點(diǎn)G。綜上前序遍歷結(jié)果為ABDECFG。中序遍歷：訪問順序?yàn)橄仍L問左子樹（L），再訪問根節(jié)點(diǎn)（N），最后訪問右子樹(R),順序?yàn)長(zhǎng)NR。以一顆滿二叉樹層次遍歷順序?yàn)锳BCDEFG為例，1、先訪問左子樹BDE，左子樹再遍歷，先左節(jié)點(diǎn)D，再訪問根節(jié)點(diǎn)B，最后訪問右節(jié)點(diǎn)E。左子樹的訪問順序?yàn)镈BE；2、然后訪問根節(jié)點(diǎn)A；3訪問右子樹CFG，先訪問左節(jié)點(diǎn)F，然后訪問根節(jié)點(diǎn)C，最后訪問右節(jié)點(diǎn)G，右子樹的訪問順序?yàn)镕CG;綜上中序遍歷結(jié)果為DBEAFCG。后序遍歷：訪問順序?yàn)橄仍L問左子樹（L），再訪問右子樹(R)，最后訪問根節(jié)點(diǎn)（N），順序?yàn)長(zhǎng)RN。以一顆滿二叉樹層次遍歷順序?yàn)锳BCDEFG為例，1、先訪問左子樹BDE，左子樹再遍歷，先左節(jié)點(diǎn)D，再訪問右節(jié)點(diǎn)E，最后訪問根節(jié)點(diǎn)B，左子樹的訪問順序?yàn)镈EB；2、訪問右子樹CFG，先訪問左節(jié)點(diǎn)F，然后訪問右節(jié)點(diǎn)G，最后訪問根節(jié)點(diǎn)C。訪問順序?yàn)镕GC；3、最后訪問根節(jié)點(diǎn)A。綜上后序遍歷結(jié)果為DEBFGCA。2遍歷的結(jié)合前序遍歷，中序遍歷，后序遍歷學(xué)生運(yùn)用遞歸的思想能掌握，但前序遍歷和中序遍歷結(jié)合在一起，讓推算后序遍歷；或者中序遍歷和后序遍歷結(jié)合在一起，讓推算前序遍歷。這類題型無疑將遍歷的難點(diǎn)一下子提升，學(xué)生往往無從下手。以下將采用分析法來破解此類題型。舉例：某二叉樹的中序遍歷序列為cbdeagihjf，后序遍歷結(jié)果為cedbijhgfa，問前序遍歷結(jié)果。對(duì)于此類題型，我們可以用分析法來處理:1）結(jié)合中序遍歷和后序遍歷的原理，對(duì)中序遍歷和后序遍歷進(jìn)行分析，中序遍歷的順序?yàn)樽笞訕洌↙）—>根（N）—>右子樹（R），后序遍歷順序?yàn)樽笞訕洌↙）—>右子樹（R）—>根（N），對(duì)于同樣一棵樹，盡管訪問順序不一樣，但是樹仍舊為那棵樹，因此我們可以從后序遍歷首先找到這棵樹的根節(jié)點(diǎn)，本例根節(jié)點(diǎn)即a;2）找到此棵樹的根節(jié)點(diǎn)a后，根據(jù)中序遍歷的原理：訪問順序?yàn)樽笞訕洌↙）—>根（N）—>右子樹（R），即根將整個(gè)訪問順序分為左右兩部分，左側(cè)部分為左子樹，即cbde；右側(cè)部分為右子樹，即gihjf。3）根據(jù)中序遍歷找到左子樹cbde后，結(jié)合后序遍歷左子樹訪問順序?yàn)閏edb,然后對(duì)這個(gè)子樹重復(fù)上述1）2）兩個(gè)步驟；根據(jù)后序遍歷，子樹根節(jié)點(diǎn)為b，然后根據(jù)中序遍歷b左側(cè)為左節(jié)點(diǎn)c，根節(jié)點(diǎn)b右側(cè)子樹為de，de作為一棵子樹，結(jié)合后序遍歷順序ed，可知子樹根節(jié)點(diǎn)為d,再結(jié)合中序遍歷de,得到右孩子為e。4）根據(jù)中序遍歷找到右子樹gihjf后，結(jié)合后序遍歷子樹的訪問順序?yàn)閕jhgf，可知f為該右子樹的根節(jié)點(diǎn)，然后對(duì)這個(gè)子樹重復(fù)上述1）2）兩個(gè)步驟；根據(jù)中序遍歷gihjf，結(jié)合根節(jié)點(diǎn)f,可知該樹只有左子樹gihj，沒有右子樹。再結(jié)合后序遍歷對(duì)gihj的訪問順序ijhg來看，g為左子樹的根節(jié)點(diǎn)，根據(jù)中序遍歷gihj來看，只有右子樹ihj,再結(jié)合后序遍歷ijh可知h為子樹根節(jié)點(diǎn)，根據(jù)中序ihj可知，i為左節(jié)點(diǎn)，j為右節(jié)點(diǎn)。5）根據(jù)以上分析畫出樹的示意圖，根據(jù)前序遍歷的訪問順序?yàn)橄仍L問根節(jié)點(diǎn)（N），再訪問左子樹（L），最后訪問右子樹(R)，得到前序遍歷順序?yàn)閍bcdefghij。3小結(jié)通過以上分析法我們可以