二叉樹(shù)的遍歷

二叉樹(shù)的三種遍歷方式：先序遍歷、中序遍歷、后序遍歷先序：

始終執(zhí)行以下步驟，

1、訪問(wèn)根節(jié)點(diǎn)

2、遍歷左子樹(shù)

3、遍歷右子樹(shù)中序：

始終執(zhí)行以下步驟，

1、遍歷左子樹(shù)

2、訪問(wèn)根節(jié)點(diǎn)

3、遍歷右子樹(shù)后序：

始終執(zhí)行以下步驟，

1、遍歷左子樹(shù)

2、遍歷右子樹(shù)

3、訪問(wèn)根節(jié)點(diǎn)“始終”：為什么要說(shuō)“始終”執(zhí)行呢？因?yàn)槎鏄?shù)的每一個(gè)子樹(shù)又可以看成是一個(gè)新的二叉樹(shù)，遍歷步驟、方式都保持一樣，所以應(yīng)該“始終”執(zhí)行同樣的操作，我們也應(yīng)該始終把它看成一棵新的二叉樹(shù)。一些技巧：

1、先序遍歷第一個(gè)元素一定是根節(jié)點(diǎn)

2、中序遍歷中，任何一個(gè)元素的前一個(gè)元素一定在二叉樹(shù)中它的左邊，比如D在G前面，則D在G左邊

3、后序遍歷最后一個(gè)元素一定是根節(jié)點(diǎn)

4、先、中、后意思是說(shuō)訪問(wèn)根節(jié)點(diǎn)的先后順序，而且始終從左往右，從上往下AABC先序遍歷為：ABC中序遍歷為：BAC后序遍歷為：BCAAABCDEFG先序遍歷為：ABDECFG中序遍歷為：DBEAFCG后序遍歷為：AEBFGCAaabecdf前序遍歷：abcdef中序遍歷：cbdaef后序遍歷：cdbfeaAABCDEFG先序遍歷為：ABDGCEF中序遍歷為：DGBAECF后序遍歷為：GDBEFCA前序遍歷結(jié)果為abdehicfg中序遍歷結(jié)果為dbheiafcg后序遍歷結(jié)果為dhiebfgcaFCFCEADBGHP前序遍歷結(jié)果為FCADBEGHP中序遍歷結(jié)果為ACBDFEHGP后序遍歷結(jié)果為ABDCHPGEF前序遍歷為：—＋a*b—cd/ef中序遍歷為：a＋b*c—d—e/f后序遍歷為：abcd—*＋ef/—前序遍歷結(jié)果為ABDHEICFG中序遍歷結(jié)果為HDBEIACGF后序遍歷結(jié)果為HDIEBGFCA由先序序列ABCDEFGH和中序序列CBEDAGHF恢復(fù)二叉樹(shù)：方法： 先序序列ABCDEFGH（注：A是根） 中序序列CBEDAGHFAABCDEFGH以A為根的左、右子樹(shù)先序序列示意圖由左子樹(shù)先序序列：BCDE和左子樹(shù)中序序列：CBED構(gòu)造A的左子樹(shù)同理，由右子樹(shù)先序序列：FGH和右子樹(shù)中序序列GHF構(gòu)造A的右子樹(shù)：AABFCDDEGHABFCDEGH

1.已知某二叉樹(shù)的其前序遍歷序列為1243576，中序遍歷序列為4215736，求后序遍歷序列（4275631）。2、已知二叉樹(shù)前序12453，中序42513。求后序。答案(45231)這樣的題怎么解？我們首先得牢記三種遞歸規(guī)則：1、前根遍歷：根—左—右2、中根遍歷：左—根—右2、后根遍歷：左—右—根從規(guī)則可以看出：前根序列的第一個(gè)值肯定是整個(gè)二叉樹(shù)的根。后根序列的最后一個(gè)值肯定是整個(gè)二叉樹(shù)的根。而知道中根序列和前、后根的一個(gè)序列后，必然中根序列將分以根分為兩個(gè)部分：左子樹(shù)和右子樹(shù)。這樣，在子樹(shù)里面找到做子樹(shù)根的那個(gè)值，繼續(xù)分左右子樹(shù)，這樣下去即可確定二叉樹(shù)的形態(tài)。同時(shí)，我們可以看到，如果只知道前、后根遍歷。不知道中根，則二叉樹(shù)形態(tài)無(wú)法唯一確定。這樣，我們來(lái)解答第一道題：前序?yàn)?243576中序?yàn)?215736.由前序可得1為二叉樹(shù)的根。將中序分為左右兩子樹(shù)。左子樹(shù)為42，右子樹(shù)為5736。左子樹(shù)前序序列中2在4的前面，中序2在4的后面，可知2為這個(gè)左子樹(shù)的根，4為這個(gè)左子樹(shù)的左節(jié)點(diǎn)。右子樹(shù)中序5736，前序3576，可得3為右子樹(shù)的根，以3為根的子樹(shù)左邊為57，右邊為節(jié)點(diǎn)6。57這個(gè)子樹(shù)5為根，7為右節(jié)點(diǎn)。這樣我們就得到了這個(gè)二叉樹(shù)的結(jié)構(gòu)圖形。后序遍歷為4275631。已知二叉樹(shù)后序遍歷序列是dabec，中序遍歷序列debac，它的前序遍歷的序列是:由后序（左子樹(shù)，右子樹(shù)，根節(jié)點(diǎn)）dabec知道根節(jié)點(diǎn)為c,再通過(guò)中序（左子樹(shù)，根節(jié)點(diǎn)，右子樹(shù)）知道右子樹(shù)為空接著由dabe知道其根節(jié)點(diǎn)為e,所以在中序deba中左子樹(shù)為d右子樹(shù)為ba再來(lái)，后序ab,中序ba,b為節(jié)點(diǎn)，a為右子樹(shù)前序遍歷序列為cedbaccedba（2）若某二叉樹(shù)的前序遍歷