T16-樹(遍歷與應(yīng)用)

遍歷與應(yīng)用第八章：樹

主講：周翔二叉樹的遍歷遍歷定義：就是按某種次序訪問樹中的結(jié)點，要求樹中每個結(jié)點訪問一次且僅訪問一次。遍歷用途：是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心遍歷方式按訪問結(jié)點的先后次序?qū)⒔Y(jié)點排列起來，分別得到的結(jié)點列表遍歷區(qū)別先序遍歷前序列表最先訪問根中序遍歷中序列表中間訪問根后序遍歷后序列表最后訪問根二叉樹的遍歷——先序遍歷先序遍歷：在遍歷二叉樹時先訪問根結(jié)點，然后訪問左子樹，最后訪問右子樹。ABDFIL第一步：訪問根結(jié)點，輸出A；第二步：訪問左子樹；左子樹是以B為根結(jié)點的二叉樹；先遍歷這棵左子樹的根結(jié)點，輸出B；第三步：訪問B的左子樹，發(fā)現(xiàn)沒有左子樹，則訪問B的右子樹，右子樹是以F為根結(jié)點的二叉樹，先遍歷這棵樹的根結(jié)點，則輸出F；二叉樹的遍歷——先序遍歷先序遍歷：在遍歷二叉樹時先訪問根結(jié)點，然后訪問左子樹，最后訪問右子樹。ABDFIL第四步：訪問F的左子樹，左子樹是以L為根結(jié)點的二叉樹，遍歷這棵樹的根結(jié)點，輸出L；第五步：訪問L的左子樹，L沒有左子樹；則訪問L的右子樹，L沒有右子樹；以L為根結(jié)點的二叉樹訪問完畢，即F的左子樹訪問完畢；第六步：訪問F的右子樹，發(fā)現(xiàn)F沒有右子樹，則以F為根結(jié)點的二叉樹訪問完畢，即B的右子樹訪問完畢，那么以B為根結(jié)點的二叉樹就訪問完畢，即A的左子樹訪問完畢；二叉樹的遍歷——先序遍歷先序遍歷：在遍歷二叉樹時先訪問根結(jié)點，然后訪問左子樹，最后訪問右子樹。ABDFIL第七步：訪問A的右子樹，右子樹是以D為根結(jié)點的二叉樹，先遍歷根結(jié)點，則輸出D；第八步：遍歷D的左子樹，左子樹是以I為根結(jié)點的二叉樹，先遍歷根結(jié)點，則輸出I；第九步：訪問I的左子樹，左子樹不存在；訪問I的右子樹，右子樹不存在；則以I為根結(jié)點的二叉樹訪問完畢，即D的左子樹遍歷完畢；第十步：訪問D的右子樹，D沒有右子樹；則以D為根結(jié)點的二叉樹訪問完畢，即A的右子樹遍歷完畢，整棵樹也遍歷完畢；二叉樹的遍歷——先序遍歷先序遍歷：在遍歷二叉樹時先訪問根結(jié)點，然后訪問左子樹，最后訪問右子樹。ABDFIL先序遍歷結(jié)果：A->B->F->L->D->I二叉樹的遍歷——中序遍歷中序遍歷：中序遍歷就是先訪問樹的左子樹，然后訪問根結(jié)點，最后訪問右子樹。ABDFIL中序遍歷結(jié)果：A有左子樹先訪問左子樹B沒有左子樹輸出BB

然后訪問B的右子樹二叉樹的遍歷——中序遍歷中序遍歷：中序遍歷就是先訪問樹的左子樹，然后訪問根結(jié)點，最后訪問右子樹。ABDFIL中序遍歷結(jié)果：BF有左子樹訪問其左子樹L沒有左子樹輸出LLL也沒有右子樹返回到L的根F二叉樹的遍歷——中序遍歷中序遍歷：中序遍歷就是先訪問樹的左子樹，然后訪問根結(jié)點，最后訪問右子樹。ABDFIL中序遍歷結(jié)果：BLF

輸出(根)F

輸出F后，A的整個左子樹遍歷完畢返回根結(jié)點A二叉樹的遍歷——中序遍歷中序遍歷：中序遍歷就是先訪問樹的左子樹，然后訪問根結(jié)點，最后訪問右子樹。ABDFIL中序遍歷結(jié)果：BLFA二叉樹的遍歷——中序遍歷中序遍歷：中序遍歷就是先訪問樹的左子樹，然后訪問根結(jié)點，最后訪問右子樹。ABDFIL中序遍歷結(jié)果：BLFD有左子樹先訪問左子樹I無左子樹輸出IAII無左右子樹返回(根)D二叉樹的遍歷——中序遍歷中序遍歷：中序遍歷就是先訪問樹的左子樹，然后訪問根結(jié)點，最后訪問右子樹。ABDFIL中序遍歷結(jié)果：BLFAI

輸出DDD無右子樹則A的右子樹遍歷完畢二叉樹的遍歷——后序遍歷后序遍歷：后序遍歷就是先訪問樹的左子樹，然后訪問樹的右子樹，最后訪問根結(jié)點。ABDFIL后序遍歷結(jié)果：LFBIDA二叉樹的遍歷對下圖中的二叉樹進行前序、中序、后序遍歷得到的列表分別為：ABDEFGHIJ先序列表:ABEFIJDGH中序列表:EBIFJAGDH后序列表:EIJFBGHDA二叉樹的遍歷對下圖中的二叉樹進行前序、中序、后序遍歷得到的列表分別為：先序列表:ABDFGCEH中序列表:BFDGACEH后序列表:FGDBHECAABCEDHFG二叉樹的應(yīng)用最早提出遍歷問題是對存儲在計算機中的表達式求值。例如：(a+b×c)-d/e前綴：-+a×bc/de中綴：a+b×c-d/e后綴：abc×+de/--+/a×debc二叉樹的應(yīng)用——遞歸思想的應(yīng)用遍歷算法的分析：從遞歸的角度看，三種算法是完全相同的，或說這三種算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過3次。AFEDCBG第1次經(jīng)過時訪問＝先序遍歷第2次經(jīng)過時訪問＝中序遍歷第3次經(jīng)過時訪問＝后序遍歷二叉樹的應(yīng)用——遞歸思想的應(yīng)用輸出葉結(jié)點：假設(shè)結(jié)點中存儲的數(shù)據(jù)元素為整數(shù)，并要求按先序輸出如果是空樹，則葉子結(jié)點個數(shù)為0；否則，為左子樹的葉子結(jié)點個數(shù)+右子樹的葉子結(jié)點個數(shù)二叉樹的應(yīng)用——遞歸思想的應(yīng)用求二叉樹的葉子結(jié)點的個數(shù)算法思想如下：（1）二叉樹的葉子結(jié)點個數(shù)是左子樹葉子結(jié)點和右子樹葉子結(jié)點個數(shù)之和；（2）左子樹又可視為一棵獨立的二叉樹，它的葉子結(jié)點個數(shù)是其左子樹和右子樹葉子結(jié)點數(shù)之和；（3）右子樹也可視為一棵獨立的二叉樹，它的葉子結(jié)點個數(shù)是其左子樹和右子樹葉子結(jié)點數(shù)之和；…….二叉樹的應(yīng)用——遞歸思想的應(yīng)用求二叉樹的高度在一棵二叉樹中，根結(jié)點是樹中的第一層，求其左子樹與右子樹的高度，比較左右子樹的高度，取較大的值加上根結(jié)點的高度1就是整棵樹的高度。二叉樹的應(yīng)用——遞歸思想的應(yīng)用求二叉樹的高度若樹為空樹，則高度為0若樹非空，高度應(yīng)為其左、右子樹高度的最大值加1二叉樹的應(yīng)用——非遞歸遍歷以中序遍歷為例來講解樹的非遞歸遍歷中序非遞歸遍歷，依然是先訪問左子樹，然后訪問根結(jié)點，最后訪問右子樹。在遍歷過程中需要用棧來處理數(shù)據(jù)。接下來就用圖解來講解樹的中序非遞歸遍歷。二叉樹的應(yīng)用——非遞歸遍歷（1）首先訪問根結(jié)點A，A有左子樹，則A結(jié)點入棧。二叉樹的應(yīng)用——非遞歸遍歷（2）A結(jié)點入棧后，指針下移，訪問A結(jié)點的左子樹，其左子樹是以B為根結(jié)點的二叉樹。訪問結(jié)點B，判斷B是否有左子樹。B沒有左子樹，輸出B。二叉樹的應(yīng)用——非遞歸遍歷（3）訪問B結(jié)點后，判斷B是否有右子樹，有，使指針下移，指向結(jié)點F，訪問F結(jié)點，判斷F結(jié)點是否有左子樹，有，則F結(jié)點入棧。二叉樹的應(yīng)用——非遞歸遍歷（4）F結(jié)點入棧后，指針下移，遍歷其左子樹；其左子樹是以L為根結(jié)點的二叉樹，訪問L結(jié)點，L沒有左子樹，則訪問L，將其輸出。二叉樹的應(yīng)用——非遞歸遍歷（5）輸出L結(jié)點后，要訪問其右子樹，L沒有右子樹，則表示L結(jié)點訪問完畢；根據(jù)棧頂指針回退到F結(jié)點，訪問F，將其輸出。二叉樹的應(yīng)用——非遞歸遍歷（6）訪問完棧頂元素結(jié)點后，要訪問其右子樹，F(xiàn)沒有右子樹，則根據(jù)棧頂指針指示再次回退，結(jié)果回退到結(jié)點A，訪問A結(jié)點，將其輸出。二叉樹的應(yīng)用——非遞歸遍歷（7）訪問完棧頂元素結(jié)點A之后，訪問其右子樹，即遍歷D結(jié)點，因為D結(jié)點有左子樹，D結(jié)點入棧。二叉樹的應(yīng)用——非遞歸遍歷（8）D結(jié)點入棧后，訪問其左子樹，左子樹是以I為根結(jié)點的二叉樹，而I沒有左子樹，則訪問I結(jié)點，將其輸出。二叉樹的應(yīng)用——非遞歸遍歷（9）結(jié)點I也沒有右子樹，則根據(jù)棧頂指示，回退到結(jié)點D，訪問D結(jié)點，將其輸出。（10）訪問D結(jié)點后，訪問其右子樹，D沒有右子樹，且此時棧已為空，表示樹已經(jīng)遍歷完畢。那么遍歷輸出結(jié)果為“BLFAID”。二叉樹的應(yīng)用——非遞歸遍歷利用棧的前序遍歷的非遞歸算法abcdecdcc退棧訪問a右進c左進b退棧訪問b右進d左進空退棧訪問d右進空左進空退棧訪問c右進空左進e退棧訪問e右進空左進空e結(jié)束ba根進a樹的遍歷遍歷方式遍歷區(qū)別先序遍歷最先訪問根中序遍歷中間訪問根后序遍歷最后訪問根層序遍歷樹的遍歷對T進行前序遍歷：先訪問樹根n，然后依次前序遍歷T1，T2，…，Tk，即前序遍歷T1，然后前序遍歷T2，…，最后前序遍歷Tk。對T進行中序遍歷：先中序遍歷T1，然后訪問樹根n，接著中序遍歷T2，…，Tk。對T進行后序遍歷：先依次對T1，T2，…，Tk進行后序遍歷，最后訪問樹根n。nT1T2…Tk樹的遍歷對下圖中的樹進行前序遍歷、中序遍歷、后序遍歷得到的列表分別為：ABCDEFGHIJ前序列表:ABEFIJCDGH中序列表:EBIFJACGDH后序列表:EIJFBCGHDA補充：層序遍歷對樹中結(jié)點按層序遍歷是指先訪問樹根，然后從左到右地依次訪問所有層數(shù)為1的結(jié)