二叉树的遍历

二叉树的三种遍历方式：先序遍历、中序遍历、后序遍历先序：

始终执行以下步骤，

1、访问根节点

2、遍历左子树

3、遍历右子树中序：

始终执行以下步骤，

1、遍历左子树

2、访问根节点

3、遍历右子树后序：

始终执行以下步骤，

1、遍历左子树

2、遍历右子树

3、访问根节点“始终”：为什么要说“始终”执行呢？因为二叉树的每一个子树又可以看成是一个新的二叉树，遍历步骤、方式都保持一样，所以应该“始终”执行同样的操作，我们也应该始终把它看成一棵新的二叉树。一些技巧：

1、先序遍历第一个元素一定是根节点

2、中序遍历中，任何一个元素的前一个元素一定在二叉树中它的左边，比如D在G前面，则D在G左边

3、后序遍历最后一个元素一定是根节点

4、先、中、后意思是说访问根节点的先后顺序，而且始终从左往右，从上往下AABC先序遍历为：ABC中序遍历为：BAC后序遍历为：BCAAABCDEFG先序遍历为：ABDECFG中序遍历为：DBEAFCG后序遍历为：AEBFGCAaabecdf前序遍历：abcdef中序遍历：cbdaef后序遍历：cdbfeaAABCDEFG先序遍历为：ABDGCEF中序遍历为：DGBAECF后序遍历为：GDBEFCA前序遍历结果为abdehicfg中序遍历结果为dbheiafcg后序遍历结果为dhiebfgcaFCFCEADBGHP前序遍历结果为FCADBEGHP中序遍历结果为ACBDFEHGP后序遍历结果为ABDCHPGEF前序遍历为：—＋a*b—cd/ef中序遍历为：a＋b*c—d—e/f后序遍历为：abcd—*＋ef/—前序遍历结果为ABDHEICFG中序遍历结果为HDBEIACGF后序遍历结果为HDIEBGFCA由先序序列ABCDEFGH和中序序列CBEDAGHF恢复二叉树：方法： 先序序列ABCDEFGH（注：A是根） 中序序列CBEDAGHFAABCDEFGH以A为根的左、右子树先序序列示意图由左子树先序序列：BCDE和左子树中序序列：CBED构造A的左子树同理，由右子树先序序列：FGH和右子树中序序列GHF构造A的右子树：AABFCDDEGHABFCDEGH

1.已知某二叉树的其前序遍历序列为1243576，中序遍历序列为4215736，求后序遍历序列（4275631）。2、已知二叉树前序12453，中序42513。求后序。答案(45231)这样的题怎么解？我们首先得牢记三种递归规则：1、前根遍历：根—左—右2、中根遍历：左—根—右2、后根遍历：左—右—根从规则可以看出：前根序列的第一个值肯定是整个二叉树的根。后根序列的最后一个值肯定是整个二叉树的根。而知道中根序列和前、后根的一个序列后，必然中根序列将分以根分为两个部分：左子树和右子树。这样，在子树里面找到做子树根的那个值，继续分左右子树，这样下去即可确定二叉树的形态。同时，我们可以看到，如果只知道前、后根遍历。不知道中根，则二叉树形态无法唯一确定。这样，我们来解答第一道题：前序为1243576中序为4215736.由前序可得1为二叉树的根。将中序分为左右两子树。左子树为42，右子树为5736。左子树前序序列中2在4的前面，中序2在4的后面，可知2为这个左子树的根，4为这个左子树的左节点。右子树中序5736，前序3576，可得3为右子树的根，以3为根的子树左边为57，右边为节点6。57这个子树5为根，7为右节点。这样我们就得到了这个二叉树的结构图形。后序遍历为4275631。已知二叉树后序遍历序列是dabec，中序遍历序列debac，它的前序遍历的序列是:由后序（左子树，右子树，根节点）dabec知道根节点为c,再通过中序（左子树，根节点，右子树）知道右子树为空接着由dabe知道其根节点为e,所以在中序deba中左子树为d右子树为ba再来，后序ab,中序ba,b为节点，a为右子树前序遍历序列为cedbaccedba（2）若某二叉树的前序遍历