⼆叉树遍历问题：前、中、后遍历顺序知⼆求⼀
⼆叉树遍历问题：前、中、后遍历顺序知⼆求⼀
⼆叉树是每个结点（node）拥有⼦结点不超过两个的树。⼆叉树的遍历（Traversal）是指沿某条路线，依次对树的每个结点做且仅做⼀次访问的过程。其主要⽅式有前序遍历（或称先序遍历）(Preorder Traversal）、中序遍历（Inorder Traversal）、后序遍历（Postorder Traversal）。前序遍历指对每个结点，先访问其根结点，再访问其左侧⼦结点，最后访问其右侧⼦结点；中序遍历指对每个结点，先访问其左侧⼦结点，再访问其根结点，最后访问其右侧⼦结点；后序遍历指对每个结点，先访问其左侧⼦结点，再访问其右侧⼦结点，最后访问其根结点。以下讨论以D、L、R分别代指根结点、左侧⼦结点、右侧⼦结点。
根据⼆叉树的两种遍历顺序求第三种遍历顺序实际上是求树的形态。对于⼀棵确定的⼆叉树，其三种遍历⽅式是唯⼀的。因此只要确定了树的形态，就可以确定各种遍历顺序。⼆叉树遍历过程是⼀种递归过程。如对左侧⼦结点的访问，即为对左侧⼦树的遍历。即⼆叉树遍历通式图1-1所⽰。据此，可由三种遍历⽅式的特点确定根结点，再不断将剩余结点划分为左⼦树与右⼦树，并最终确定树的形态，得到未知的遍历顺序。
下⾯以图1-2中所⽰的⼀棵⽐较⼀般的简单⼆叉树为例，说明前、中、后遍历顺序知⼆求⼀的详细过程。
1.由前序遍历、中序遍历求后序遍历
二叉树前序中序后序图解由前序遍历（DLR）的规则可知，⾸个访问对象必为树根（即⾸个根结点），后若⼲项为对左⼦树的访问，再后若⼲项直⾄最后是对右⼦树的访问。
例如：已知对某⼆叉树前序遍历顺序为：ABDEGHCFI，中序遍历顺序为DBGEHACIF，求后序遍历顺序。
解：由前序遍历顺序可确定第⼀层根结点为A，记为D1=A。由中序遍历顺序可确定第⼀层的左⼦树中序遍历为L1=(DBGEH)in，右⼦树中序遍历为R1=(CIF)in。配合前序遍历，可知第⼀层的左⼦树前序遍历为L1=(BDEGH)pre，右⼦树前序遍历为R1=(CFI)pre。再根据对L1中序、前序遍历的结果，易知D2=B，同理可得各个结点左、右两⼦树的组成，再不断迭代即可得到整个树的结构。
由后序遍历、中序遍历求前序遍历的过程与之类似。
2.由前序遍历、后序遍历求中序遍历
由前序遍历的规则，可知⾸个访问对象必为树根，第⼆个访问对象必为树根左⼦树的树根。同理，对于后序访问，最后⼀个访问对象为树根，⽽倒数第⼆个访问对象为右⼦树的树根。可据此将所有访问对象不断划分成各个左、右⼦树，最终得到⼆叉树结构。
例如：已知对某⼆叉树前序遍历顺序为：ABDEGHCFI，后序遍历顺序为DGHEBIFCA，求中序访问顺序。
解：由前序遍历顺序可确定第⼀层根结点为A，记为D1=A；左⼦树根结点为B，记为D L=B。由后序遍历顺序可确定第⼀层根结点为A；右⼦树根结点为C，记为D R=C。依此可根据前序遍历的顺序得到对左、右⼦树的前序遍历顺序，即L1=(BDEGH)pre，R1=(CFI)pre；可根据后序遍历顺序得到对左、右⼦树后序遍历顺序，即L1=(DGHEB)post，R1=(IFC)post。再不断迭代可得到整个树的可能结构。
有⼀种特殊情况需要说明：当前序遍历第⼆个访问对象与后序遍历倒数第⼆个访问对象相同时，可认为是该结点左⼦树树根与右⼦树树根相同，也就是说该结点仅有⼀个⼦结点。在前序访问和后序访问中，此时这个⼦结点可以认为是该结点的左结点，也可认为是该结点的右结点，这不会影响它在前序访问和后序访问中被访问的顺序，但是会影响该结点在中序访问中被访问的顺序。因此，若⼆叉树中某结点仅有⼀个⼦结点时，不能由前序遍历和后序遍历得出中序遍历的访问顺序。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。