Pascal二叉树后序中序转前序

二叉树后序中序求先序 用PASCAL~

在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理。
这就是二叉树的遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结
点仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。遍历一般按照从
左到右的顺序，共有3 种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。
一先序遍历的操作定义如下：
若二叉树为空，则空操作，否则
①访问根结点
②先序遍历左子树
③先序遍历右子树
先序遍历右图结果为：124753689
procedure preorder(bt:tree); //先序遍历根结点为bt 的二叉树的递归算法
begin
if btnil then begin
write(bt^.data);
preorder(bt^.lchild);
preorder(bt^.rchild);
end;
end;
二中序遍历的操作定义如下：
若二叉树为空，则空操作，否则
①中序遍历左子树
②访问根结点
③中序遍历右子树
中序遍历右图结果为：742513869
procedure inorder(bt:tree); //中序遍历根结点为bt 的二叉树的递归算法
begin
if btnil then begin
preorder(bt^.lchild);
write(bt^.data);
preorder(bt^.rchild);
end;
end;
三后序遍历的操作定义如下：
若二叉树为空，则空操作，否则
①后序遍历左子树
②后序遍历右子树
③访问根结点
后序遍历右图结果为：745289631
procedure postorder(bt:tree); //后序遍历根结点为bt 的二叉树的递归算法
begin
if btnil then begin
preorder(bt^.lchild);
preorder(bt^.rchild);
write(bt^.data);
end;
end;
当然，我们还可以把递归过程改成用栈实现的非递归过程，以先序遍历为例，其它的留给作者完成。
Procedure preorder(bt:tree); //先序遍历bt 所指的二叉树
Var stack:array[1..n] of tree; //栈
top:integer; //栈顶指针
P:tree;
begin
top:=0;
While not ((bt=nil)and(top=0)) do
Begin
While btnil do begin //非叶结点
Write(bt^.data); //访问根
top:=top+1; //右子树压栈
stack[top]:=bt^.rchild
bt:=bt^.lchild; //遍历左子树
end;
If top0 then begin //栈中所有元素出栈，遍历完毕
bt:=stack[top];
top:=top-1;
End;
End;
End;

首先知道：
先序：根左右；后序，左右根；中序，左根右。
看过程：是递归调用的：
if length(s2)=1 then write(s2)｛如果当前后序遍历只有一个就直接输出该位置｝
else begin
k:=pos(s2[length(s2)],s1);｛后序排序的最后一个是当前序列的根，寻找根在中序排序中的位置，则中序排序被跟分成前面后面两节，前面那节是左子树，后面是右子树｝
write(s1[k]);｛先序是先输出根｝
if k>1 then solve(copy(s1,1,k-1),copy(s2,1,k-1));｛如果左子树存在就递归调用｝
if k<length(s1)
then
solve(copy(s1,k+1,length(s1)-k),copy(s2,k,length(s2)-k));｛如果存在右子树递归调用｝
end;

solve(copy(s1,1,k-1),copy(s2,1,k-1))本句话的意思是，s1序列从第1个到第k-1个是左子树，s2前面同样的长度也是左子树，所以，相当于把这个问题又分成了个新的和先一样的问题，已知中序和后序，求先序，那不就是可以递归了，只不过长度改变了，变成原来的左子树。
其实意思很简单，就是每次都找到根输出，然后遍历左子树，遍历右子树，然后对左子树同样，先输出根，再访问左子树，右子树，。。。递归调用。
那么每次就是要找到根是哪个就可以，所以我门根据： 先序：根左右；后序，左右根；中序，左根右。特点知道怎么找根，然后递归调用。
同理可以知道
solve(copy(s1,k+1,length(s1)-k),copy(s2,k,length(s2)-k));
是在访问递归调用右子树。

var st1,st2,pre:string;

procedure solve(mid,post:string);
var i:integer;
begin
if (mid='') or (post='') then exit;
pre:=pre+post[length(post)];
i:=pos(post[length(post)],mid);
solve(copy(mid,1,i-1),copy(post,1,i-1));
solve(copy(mid,i+1,length(mid)-i),copy(post,i,length(post)-i));
end;

begin
readln(st1);//中序
readln(st2);//后序
solve(st1,st2);
writeln(pre);//前序
end.

有必要怀疑你是常训班上的，这张图是前序中序转后序，改一下细节吧

---

江洲区15739981400： 已知二叉树中序和后序遍历怎么求前序遍历遍历啊? - ？
宗圣寿排毒： 自己写个stack 我给你写的前后中写法吧. 前MyStack<TreeNode *> stack;while(true){while (lpCurNode){if (lpfun!=NULL){(this->*lpfun)(lpCurNode);stack.Push(lpCurNode);}lpCurNode=lpCurNode->m_lpLeft;}if (!stack.Pop(lpCurNode))...

江洲区15739981400： 二叉树的已知后序中序求先序算法 - ？
宗圣寿排毒： /* 树中已知中序和后序求先序.如中序为:bdac 后序为:dbca则程序可以求出先序为:abdc .此种题型为数据结构常考题型. 算法思想:后序遍历树的规则为左右中,则说明最后一个元素必为树的根节点,比如上例 中的a就为根节点,由于...

江洲区15739981400： 已知二叉树的后序和中序怎么求前序 - ？
宗圣寿排毒： 根据所给两条序列找出根结点,再根据此两序列画出示意图,自然可以写出前序序列

江洲区15739981400： 已知二叉树的后序遍历序列和中序遍历序列,怎样求其前序遍历序列! - ？
宗圣寿排毒： 首先理解概念: 前序遍历:访问根结点的操作发生在遍历其左右子树之前. 中序遍历:访问根结点的操作发生在遍历其左右子树之中(间). 后序遍历:访问根结点的操作发生在遍历其左右子树之后. eg:后序遍历为DBCEFGHA,中序遍历为EDCBAHFG,求前序遍历(网上例子) 解:首先 看后序遍历DBCEFGHA,A为总根节点然后 寻找中序遍历EDCBAHFG中A位置,则EDCB在A的左枝,HFG在A的右枝;重复前两步,从后序遍历最后一位找,在中序遍历寻找对应点,得出左右分枝...最后得到AECDBHGF,再自己验证即可...

江洲区15739981400： 二叉树先知道后序和中序,求先序 - ？
宗圣寿排毒： 后序DABEC 中序DEBAC 由后序最后一个字母知:整个树的开始结点为C; 由中序C的位置知:C前面的为结点C的左子树;C后面的为结点C的右子树; 所以经过第一次推理,C为根结点,DEBA为其左子树; 然后去掉C,考虑下面的左子树; 后序DABE 中序DEBA 由后序最后一个字母知:整个左子树的开始结点为E; 由中序E的位置知:E前面的为结点E的左子树;E后面的为结点E的右子树; 所以经过第一次推理,E为开始结点,D为E的左结点.BA为E的右结点. 然后去掉DE,考虑下面E的右子树; 后序AB 中序BA 易知:B为根结点,A为其右结点. 所以整个树为:C(E(D,B(,A))); 先序:CEDBA

江洲区15739981400： 输入两个字符串,分别是一颗二叉树的中序和后序,编程输出其先序.(Pascal) - ？
宗圣寿排毒： program qiuqianxu; var s1,s2,s:string; procedure sou(s1,s2:string); var t,k,l:longint; c:char; begin c:=s2[length(s2)]; {后序排列的尾是先序排列的头} for t:=1 to length(s1) do if s1[t]=c then break; write(c); if t>1 then sou(copy(s1,1,t-1),copy(s2,1,t-1)); ...

江洲区15739981400： 已知二叉树的中、后遍历序列,推导出前序遍历. - ？
宗圣寿排毒： 1、确定树的根.树根是当前树中所有元素在后序遍历中最后出现的元素.2、求解树的子树.找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树.若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点.3、递归求解树.将左子树和右子树分别看成一棵二叉树,重复1、2、3步,直到所有的节点完成定位.

江洲区15739981400： 跪求知道二叉树的中序遍历和后续遍历求前序遍历程序.必须是pascal的.好的程序一定给采纳.跪求! - ？
宗圣寿排毒： 程序: vars1,s2:string; procedure solve(s1,s2:string); vark:integer; beginif length(s2)=1 then write(s2)else begink:=pos(s2[length(s2)],s1);write(s1[k]);if k>1 then solve(copy(s1,1,k-1),copy(s2,1,k-1));if k<length(s1)thensolve(copy(s1,k+1,...

江洲区15739981400： 由二叉树的后序遍历和中序遍历,怎么推出它的前序遍历? - ？
宗圣寿排毒： 这个简单啊,都能口算了,从后序中得c为根节点 然后到中序中找,c右边没有所以没有右孩子 在后序中a为最后,所以a是左孩子的根节点 在中序中d在其左边be在其右边 所以分别为其左子树和右子树 e为b的右子树 前序:cadbe

江洲区15739981400： pascal二叉树 - ？
宗圣寿排毒： 我来告诉你啊.前序的顺序是:根,左,右 中序的顺序是:左,根,右 后序的顺序是:左,右,根 如果你要求中序,那么我出个例子 前序ABCDE 后序CEBDA 中序就是:CBAED 推断过程就是:第一步,确定根A(因为后序的最后一个字母和...