刚才又复习了一下预习了树的遍历，正好再来看看两种遍历方法组合成树的方法； 如果可以生成完整的树，也可以求出另一个导线序列。 借这个博客正好记录一下方法，为了以后不忘记，还得再找文章新学习
三种遍历对应的遍历方法：前序：遍历根节点，按顺序遍历根节点的左子树和右子树
中序)首先遍历左侧的子树，然后依次遍历根节点及其右侧的子树
后序)首先遍历根节点的左右子树，最后成为根节点
1、了解求解前相横移、中相横移、后相横移问题的思想。 在前序遍历中，根节点必须出现在开头，通过该点可以得到每个子树的根节点。
中顺序扫描中，根节点的左右子树一定在根节点的左右，我们可以从这个点快速得到树的左右子树。
其可以针对一棵子树，节点可以从前一遍历中的位置快速得到根节点，接着通过中的遍历得到其左侧子树和右侧子树，我们将继续执行后续遍历
坐代码吧：
输入(前序后序) 6
1 2 3 4 5 6
3 2 4 1 6 5
代码# include bits/stdc.h # definellonglong # define endl 'n ' usingnamespacestd； int n，px[105]、qx[105]、zx[105]； //qx存储器前相横移排列，zx存储器中相横移//px存储器各数字表示前相横移中的位置int hx[105]，cnt； //hx从后开始按顺序收纳遍历数组，cnt在存储当前存储的位置voidss(intl，int r ) if(l==r )//只保留1个节点)//的情况下，只需将直接输出变更为对应的数组即可coutzx[l] '； 返回； (}int xh=1e5，wz； //查找当前子树的根节点for (inti=l； i=r； I () if ) px[zx[I]xh ) ) {xh=px[zx[i]]； wz=i； () ) ) /之后遍历if(wz-1=L ) ss ) l，wz-1 )； //搜索根节点的左子树(判断为先存在) if ) wz1=r ) ss ) wz1，r )； //搜索根节点的右部分树(首先确定其存在) hx[ cnt]=zx[wz]； //找到左右子树后，其馀的根节点也加入到后面的序列中coutzx[wz] '； }int main () IOs :3360 sync _ with _ stdio (false )； CIN.Tie(0； cout.tie(0； cinn； for(intI=1； i=n； I ) {cinqx[i]； px[qx[i]]=i； }for(intI=1； i=n； I ) cinzx[i]； ss(1，n )； //coutendl； //for(intI=1； i=n； //couthx[i]endl； 返回0； }获得输出：
2、已知通过后相横移、中相横移求解前相横移的思想。 在后相遍历中，根节点必须出现在最后面，从此点可以得到每个子树的根节点。
中顺序扫描中，根节点的左右子树一定在根节点的左右，我们可以从这个点快速得到树的左右子树。
那这种情况跟上面的那种就很像了，对于一个子树，我们可以通过每个节点在后序遍历中的位置快速得到其根节点，然后通过中序遍历得到其左子树和右子树
直接坐上代码吧：
输入(先中后序) 6
3 2 4 1 6 5
3 4 2 6 5 1
代码//方法代码与上面的相同，所以不写注释。 # include bits/stdc.h # definellonglong # define endl 'n ' usingnamespacestd； int n，px[105]、hx[105]、zx[105]； int qx[105]，cnt； voidss(intl，int r ) if ) l==r ) {qx[ cnt]=zx[l]； coutzx[l] '； 返回； (}int xh=0，wz； for(intI=L； i=r； I () if ) px[zx[I]xh ) ) {xh=px[zx[i]]； wz=i； () ) ) /前序是先根节点，接着是左子树右子树的) qx[ cnt]=zx[wz]； coutzx[wz] '； if(wz-1=L ) ss ) l，wz-1 )； if(wz1=r ) ss ) wz1，r )； }int main () IOs :3360 sync _ with _ stdio (false )； CIN.Tie(0； cout.tie(0； cinn； for(intI=1； i=n； I ) cinzx[i]； for(intI=1； i=n； I ) {cinhx[i]； px[hx[i]]=i； (ss ) 1，n )； //coutendl； //for(intI=1； i=n； //coutqx[i]endl； 返回0； }获得输出：
3、通过前相横移、后相横移求解中相横移还不到55555。 以后有缘再说吧~