根据后序和中序遍历输出先序遍历

Q1：根据二叉树的先序遍历与后序遍历推测可能的中序遍历

刚刚也在搜这个问题……

我按我做的题目举例吧：后序序列为：bfegcda,中序序列为：badefcg,求前序序列。

这里会用：后序列序列最后一个值即树（或子树）的根。

由后序“bfegcda”知a为根，由中序“badefcg”知a的左子树仅有b一个节点。即图1.

去除序列中的b和a得后序“fegcd”和中序“defcg”，可知，d为a的右子树树根（后序最后一个值）且d的左子树为空（d前面无值），同理再去掉d得到，“fegc”和“efcg”，可知c为d的右子树树根，如图2.

由中序“efcg”知c的右子树为g，左子树为e,f，同理得最后结果树为图3.

于是得出前序列为：

abdcefg

Q2：输入先序遍历和中序遍历，输出后序遍历，打印出二叉树，用递归做，c++版

//先序遍历
#include
usingnamespacestd;
structTreeNode
{
intval;
TreeNode*left,*right;
};
//先序遍历
voidPreorderTraversal(TreeNode*root){
if(!root)return;
cout<val< if(root->left)
PreorderTraversal(root->left);
if(root->right)
PreorderTraversal(root->right);
}
//中序遍历
voidInorderTraversal(TreeNode*root){
if(!root)return;
if(root->left)
InorderTraversal(root->left);
cout<val< if(root->right)
InorderTraversal(root->right);
}
//后序遍历
voidPostorderTraversal(TreeNode*root){
if(!root)return;
if(root->left)
InorderTraversal(root->left);
if(root->right)
InorderTraversal(root->right);
cout<val<}
intmain()
{
...
}

Q3：二叉树根据先序遍历、后序遍历 求中序遍历 pascal代码 附详细解释最好

主要是分治的思想，每次判断一种分割左右子树的方案是否可行，可行的话就递归
{ Problem: travel.Author: zw }
Program zw_travel;
Var
i,j,k,o,p,n,m,ans:longint;
s1,s2:string;
Procedure init;
begin
readln(s1);
readln(s2);
end;
Function check(f,l:string):boolean;
var
i:longint;
begin
if length(f)=0 then
check:=true
else
begin
check:=true;
check:=f[1]=l[length(l)];
for i:=2 to length(f) do
if pos(f[i],l)=0 then check:=false;
end
end;
Function count(f1,l1:string):longint;
var
i,len,t:longint;
lf,ll,rf,rl:string[50];
begin
len:=length(l1); t:=0;
if len<=1 then count:=1、else
begin
for i:=len-1 downto 0 do
begin
lf:=copy(f1,2,i);
ll:=copy(l1,1,i);
rf:=copy(f1,i+2,len-1-i);
rl:=copy(l1,i+1,len-1-i);
if check(lf,ll) and check(rf,rl) then
t:=t+count(lf,ll)*count(rf,rl);
end;
count:=t;
end;
end;
Begin
init;
ans:=count(s1,s2);
writeln(ans);
End.

Q4：数据结构二叉树，已知中序遍历、后序遍历，如何求先序遍历？

Preorder遍历:访问根节点的操作发生在遍历左和右子树之前。

中间顺序遍历:访问根节点的操作发生在左边和右边的子树中。

顺序遍历:访问根节点的操作发生在遍历左边和右边的子树之后。

下面的序列遍历了DBCEFGHA，序列遍历是EDCBAHFG，以及preorder遍历(在线示例)

解决方案:首先，看到后序遍历DBCEFGHA, A是总根节点。

然后发现中间顺序遍历A在EDCBAHFG中的位置，然后在A的左分支上的EDCB，在A的右分支上的HFG;

重复前两个步骤，最后一个从后序遍历，在中间顺序遍历中搜索相应的点，以及左和右分支…

最后，AECDBHGF可以自行验证。

Q5：写出二叉树的先序遍历、中序遍历、后序遍历。

首先 观察这个二叉树
可见是这样的：1.以B为根节点的左子树A根节点以C为根节点的右子树
2.以D为根节点的左子树 B根节点 以E为根节点的右子树
3.以G为根节点的左子树 D根节点 以H为根节点的右子树
4.以K为根节点的左子树 C根节点 以F为根节点的右子树
5.以I为根节点的左子树 F根节点 右子树为空
6.左子树为空 I根节点 以J为根节点的右子树
接下来可以进行遍历了：
前序遍历 是 根 左子树 右子树：
即先是跟节点A 然后遍历 B子树 遍历完B子树后 再遍历C子树 即最后答案为：
ABDGHECKFIJ
中序遍历为 左子树 根 右子树
先遍历 B子树 遍历完了 再是A节点然后是右子树 答案为：
GDHBEAKCIJF
后序遍历是 左子树 右子树 根
答案为：
GHDEBKJIFCA