二叉樹的遍歷

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

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

1、訪問根節(jié)點

2、遍歷左子樹

3、遍歷右子樹中序：

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

1、遍歷左子樹

2、訪問根節(jié)點

3、遍歷右子樹后序：

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

1、遍歷左子樹

2、遍歷右子樹

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

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

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

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

4、先、中、后意思是說訪問根節(jié)點的先后順序，而且始終從左往右，從上往下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ù)二叉樹：方法： 先序序列ABCDEFGH（注：A是根） 中序序列CBEDAGHFAABCDEFGH以A為根的左、右子樹先序序列示意圖由左子樹先序序列：BCDE和左子樹中序序列：CBED構(gòu)造A的左子樹同理，由右子樹先序序列：FGH和右子樹中序序列GHF構(gòu)造A的右子樹：AABFCDDEGHABFCDEGH

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