遍歷二叉樹與線索二叉樹ppt課件

1、指按某條搜索路線遍訪每個結(jié)點且指按某條搜索路線遍訪每個結(jié)點且不重復(fù)又稱周游）。不重復(fù)又稱周游）。它是樹結(jié)構(gòu)插入、刪除、修改、查找它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。算的基礎(chǔ)和核心。對每個結(jié)點的查看通常都是對每個結(jié)點的查看通常都是“先左后先左后右右”。（無論是先序、中序還是后序）。（無論是先序、中序還是后序）先序遍歷的結(jié)果是：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：后序遍歷的結(jié)果是： A B CD E口訣：口訣：DLR先序遍歷，即先根再左、右先序遍歷，即先根再左、右LDR中序遍歷，即先左再

2、根后右中序遍歷，即先左再根后右LRD后序遍歷，即先左、右再根后序遍歷，即先左、右再根層次遍歷：層次遍歷：ABCDEabadefgff n個結(jié)點個結(jié)點. . . . . 例例2 2：畫出所有中序遍歷序列和后序遍歷序列一致的：畫出所有中序遍歷序列和后序遍歷序列一致的 二叉樹的所有形態(tài)二叉樹的所有形態(tài). .分析：中序遍歷分析：中序遍歷: LDR-LD: LDR-LD 后序遍歷后序遍歷: LRD-LD . .: LRD-LD . .右子樹右子樹 return(0); return(0); （1） 從前面的三種遍歷算法可以知道：如果將從前面的三種遍歷算法可以知道：如果將printf語句抹去，從遞歸的角度

3、看，這三種算法是完全相同語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同。是訪問結(jié)點的時機不同。從虛線的出發(fā)點到終點的路從虛線的出發(fā)點到終點的路徑徑上，每個結(jié)點經(jīng)過上，每個結(jié)點經(jīng)過3 3次。次。AFEDCBG第第1 1次經(jīng)過時訪問，是先序遍歷次經(jīng)過時訪問，是先序遍歷第第2 2次經(jīng)過時訪問，是中序遍歷次經(jīng)過時訪問，是中序遍歷第第3 3次經(jīng)過時訪問，是后序遍歷次經(jīng)過時訪問，是后序遍歷 任何一棵二叉樹都可以將它的外部輪廓用一條線任何一棵二叉樹都可以將它的外部輪廓用一條線繪制出來，我們將它稱為

4、二叉樹的包線，這條包線繪制出來，我們將它稱為二叉樹的包線，這條包線對于理解二叉樹的遞歸遍歷很有用。如圖：對于理解二叉樹的遞歸遍歷很有用。如圖：+*A*/EDCB先序遍歷結(jié)果：先序遍歷結(jié)果：+ * * / A B C D E前綴表示法前綴表示法（波蘭式）（波蘭式）中序遍歷結(jié)果：中序遍歷結(jié)果：A / B * C * D + E中綴表示法中綴表示法后序遍歷結(jié)果：后序遍歷結(jié)果：A B / C * D * E +后綴表示法后綴表示法（逆波蘭式）（逆波蘭式）層次遍歷結(jié)果：層次遍歷結(jié)果：+ +* *E E* *D/CABD/CAB這就是線索二叉樹這就是線索二叉樹Threaded Binary TreeThr

5、eaded Binary Tree）二叉樹中容易找到結(jié)點的左右孩子信息，但該結(jié)二叉樹中容易找到結(jié)點的左右孩子信息，但該結(jié)點在某一序列中的直接前驅(qū)和直接后繼只能在某種遍點在某一序列中的直接前驅(qū)和直接后繼只能在某種遍歷過程中動態(tài)獲得。歷過程中動態(tài)獲得。先依遍歷規(guī)則把每個結(jié)點某一序列中對應(yīng)的前驅(qū)先依遍歷規(guī)則把每個結(jié)點某一序列中對應(yīng)的前驅(qū)和后繼線索預(yù)存起來，這叫做和后繼線索預(yù)存起來，這叫做“線索化線索化”。意義：從任一結(jié)點出發(fā)都能快速找到其某一序列意義：從任一結(jié)點出發(fā)都能快速找到其某一序列中前驅(qū)和后繼，且不必借助堆棧。中前驅(qū)和后繼，且不必借助堆棧。 每個結(jié)點增加兩個域：每個結(jié)點增加兩個域：fwd和和b

6、wd；如何預(yù)存這類信息？有兩種解決方法：如何預(yù)存這類信息？有兩種解決方法： 與原有的左右孩子指針域與原有的左右孩子指針域“復(fù)用復(fù)用”，充分利用那，充分利用那n+1n+1個空鏈域。個空鏈域。規(guī)規(guī) 定：定：1 1若結(jié)點有左子樹，則若結(jié)點有左子樹，則lchildlchild指向其左指向其左孩子；否則，孩子；否則，lchildlchild指向其直接前驅(qū)指向其直接前驅(qū)( (即即線索線索) )；2 2若結(jié)點有右子樹，則若結(jié)點有右子樹，則rchildrchild指向其右指向其右孩子；否則，孩子；否則，rchildrchild指向其直接后繼指向其直接后繼( (即線索即線索) ) 。datalchildrchi

7、ldfwdbwddatalchildrchild缺點：空間效缺點：空間效率太低！率太低！如何判斷是孩如何判斷是孩子指針還是線子指針還是線索指針？索指針？如何區(qū)如何區(qū)別？別？約定約定: 當當Tag域為域為0時時,表示孩子情況表示孩子情況;當當Tag域為域為1時時,表示線索情況表示線索情況.前驅(qū)前驅(qū)(后繼后繼)左左(右右)孩子孩子問：增加了前驅(qū)和后繼等線索有什么好處？問：增加了前驅(qū)和后繼等線索有什么好處？能方便找出當前結(jié)點的前驅(qū)和后繼，不用能方便找出當前結(jié)點的前驅(qū)和后繼，不用堆棧遞歸也能遍歷整棵樹。堆棧遞歸也能遍歷整棵樹。各各1bit1bit線索鏈表：線索鏈表：線線 索：索：線索二叉樹：線索二叉樹：線線 索索 化：化：用含用含TagTag的結(jié)點樣式所構(gòu)成的二叉鏈表。的結(jié)點樣式所構(gòu)成的二叉鏈表。指向結(jié)點前驅(qū)和后繼的指針。指向結(jié)點前驅(qū)和后繼的指針。加上線索的二叉樹。加上線索的二叉樹。對二叉樹以某種次序遍歷使其變?yōu)榫€索二對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程。叉樹的過程。線索化過程就是在遍歷過程中修改空指針的過程：課本線索化過程就是在遍歷過程中修改空指針的過程：課本P127P127圖圖6.86.8 將空的將空的l