高中信息技術學科二叉樹遍歷題型的教學思考

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