|
二叉樹的遍歷： D：訪問根結(jié)點(diǎn),，L：遍歷根結(jié)點(diǎn)的左子樹,，R：遍歷根結(jié)點(diǎn)的右子樹。 給定一棵二叉樹的前序遍歷序列和中序遍歷序列可以惟一確定一棵二叉樹,。 二叉樹的深度優(yōu)先遍歷的非遞歸的通用做法是采用棧,，廣度優(yōu)先遍歷的非遞歸的通用做法是采用隊(duì)列。 深度優(yōu)先遍歷二叉樹,。 1. 中序遍歷（LDR）的遞歸算法： 若二叉樹為空,，則算法結(jié)束；否則： 中序遍歷根結(jié)點(diǎn)的左子樹,； 訪問根結(jié)點(diǎn),； 中序遍歷根結(jié)點(diǎn)的右子樹。 2. 前序遍歷（DLR）的遞歸算法： 若二叉樹為空,，則算法結(jié)束,，否則： 訪問根結(jié)點(diǎn)； 前序遍歷根結(jié)點(diǎn)的左子樹,； 前序遍歷根結(jié)點(diǎn)的右子樹,。 3. 后序遍歷（LRD）的遞歸算法： 若二叉樹為空，則算法結(jié)束,，否則： 后序遍歷根結(jié)點(diǎn)的左子樹,； 后序遍歷根結(jié)點(diǎn)的右子樹； 訪問根結(jié)點(diǎn),。
廣度優(yōu)先遍歷二叉樹,。 廣度優(yōu)先周游二叉樹(層序遍歷)是用隊(duì)列來實(shí)現(xiàn)的，從二叉樹的第一層（根結(jié)點(diǎn)）開始,，自上至下逐層遍歷,；在同一層中,，按照從左到右的順序?qū)Y(jié)點(diǎn)逐一訪問。 按照從根結(jié)點(diǎn)至葉結(jié)點(diǎn),、從左子樹至右子樹的次序訪問二叉樹的結(jié)點(diǎn)。算法： 1初始化一個(gè)隊(duì)列,，并把根結(jié)點(diǎn)入列隊(duì),； 2當(dāng)隊(duì)列為非空時(shí)，循環(huán)執(zhí)行步驟3到步驟5,，否則執(zhí)行6,； 3出隊(duì)列取得一個(gè)結(jié)點(diǎn)，訪問該結(jié)點(diǎn),； 4若該結(jié)點(diǎn)的左子樹為非空,，則將該結(jié)點(diǎn)的左子樹入隊(duì)列； 5若該結(jié)點(diǎn)的右子樹為非空,，則將該結(jié)點(diǎn)的右子樹入隊(duì)列,； 6結(jié)束。
非遞歸深度優(yōu)先遍歷二叉樹,。 棧是實(shí)現(xiàn)遞歸的最常用的結(jié)構(gòu),，利用一個(gè)棧來記下尚待遍歷的結(jié)點(diǎn)或子樹，以備以后訪問,，可以將遞歸的深度優(yōu)先遍歷改為非遞歸的算法,。 1. 非遞歸前序遍歷：遇到一個(gè)結(jié)點(diǎn)，就訪問該結(jié)點(diǎn),，并把此結(jié)點(diǎn)推入棧中,，然后下降去遍歷它的左子樹。遍歷完它的左子樹后,，從棧頂托出這個(gè)結(jié)點(diǎn),，并按照它的右鏈接指示的地址再去遍歷該結(jié)點(diǎn)的右子樹結(jié)構(gòu)。 2. 非遞歸中序遍歷：遇到一個(gè)結(jié)點(diǎn),，就把它推入棧中,，并去遍歷它的左子樹。遍歷完左子樹后,，從棧頂托出這個(gè)結(jié)點(diǎn)并訪問之,，然后按照它的右鏈接指示的地址再去遍歷該結(jié)點(diǎn)的右子樹。 3. 非遞歸后序遍歷：遇到一個(gè)結(jié)點(diǎn),，把它推入棧中,，遍歷它的左子樹。遍歷結(jié)束后,，還不能馬上訪問處于棧頂?shù)脑摻Y(jié)點(diǎn),，而是要再按照它的右鏈接結(jié)構(gòu)指示的地址去遍歷該結(jié)點(diǎn)的右子樹,。遍歷遍右子樹后才能從棧頂托出該結(jié)點(diǎn)并訪問之。另外,，需要給棧中的每個(gè)元素加上一個(gè)特征位,，以便當(dāng)從棧頂托出一個(gè)結(jié)點(diǎn)時(shí)區(qū)別是從棧頂元素左邊回來的(則要繼續(xù)遍歷右子樹)，還是從右邊回來的(該結(jié)點(diǎn)的左,、右子樹均已周游),。特征為Left表示已進(jìn)入該結(jié)點(diǎn)的左子樹，將從左邊回來,；特征為Right表示已進(jìn)入該結(jié)點(diǎn)的右子樹,，將從右邊回來。 4. 簡潔的非遞歸前序遍歷：遇到一個(gè)結(jié)點(diǎn),，就訪問該結(jié)點(diǎn),，并把此結(jié)點(diǎn)的非空右結(jié)點(diǎn)推入棧中，然后下降去遍歷它的左子樹,。遍歷完左子樹后,，從棧頂托出一個(gè)結(jié)點(diǎn)，并按照它的右鏈接指示的地址再去遍歷該結(jié)點(diǎn)的右子樹結(jié)構(gòu),。 ---------------------------------------------------------------------- 圖的深度優(yōu)先搜索法是樹的先根遍歷的推廣,，它的基本思想是：從圖G的某個(gè)頂點(diǎn)v0出發(fā)，訪問v0,，然后選擇一個(gè)與v0相鄰且沒被訪問過的頂點(diǎn)vi訪問,，再從vi出發(fā)選擇一個(gè)與vi相鄰且未被訪問的頂點(diǎn)vj進(jìn)行訪問，依次繼續(xù),。如果當(dāng)前被訪問過的頂點(diǎn)的所有鄰接頂點(diǎn)都已被訪問,，則退回到已被訪問的頂點(diǎn)序列中最后一個(gè)擁有未被訪問的相鄰頂點(diǎn)的頂點(diǎn)w，從w出發(fā)按同樣的方法向前遍歷,，直到圖中所有頂點(diǎn)都被訪問,。 |
|
|
