给出一棵二叉树的前序和中序遍历的结果,还原这棵二叉树并输出其后序遍历的结果。
先序遍历结果为=‘根节点’+‘左子树的前序遍历’+‘右子树的前序遍历’,中序遍历结果为=‘左子树的中序遍历’+‘根节点’+‘右子树的中序遍历’然后我们可以递归处理左子树的先序遍历和中序遍历。
设计要求:给出一棵二叉树的前序和中序遍历的结果,求它的后序遍历序列
期末考试题,求大神帮忙
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
3条回答 默认 最新
- quentain 2015-12-31 01:42关注
解析:
首先分析:给出先序遍历的二叉树的结果,我们知道先序是:根 左 右;中序是:左 根 右;
那么我们很容易就知道在先序遍历中可以确定二叉树的根所在的位置,其次再在中序遍历中找出根的左边和右边,这样不断的递归就会将原来的二叉树构建
出来,之后再进行后续遍历:左 右 根;
伪代码如下:
/*
思想:根据二叉树的先序序列和中序序列恢复二叉树的递归思想是:先根据先序序列的第一个结点建立根结点,然后在中序序列中找到
该结点,从而划分出根节点的左、右子树的中序序列。接下来再在先序序列中确定左、右子树的先序序列,并有左子树的先序序列与
中序序列继续递归建立左子树,由右子树的先序序列与中序序列继续递归建立右子树。
为了能够将恢复的二叉树传回给主调函数,在函数Per_In_order中使用了二级指针**p.
在下面的算法中,二叉树的先序遍历序列和中序遍历序列分别存放在一维数组pred和ind中。算法如下:
/
void Pre_In_order(char pred[],char ind[],int i,int j,int k,int h,BSTree **p){
//i、j和k、h分别为当前子树先序序列和中序序列的下、上界
int m;
*p=(BSTree)malloc(sizeof(BSTree));//在主调函数空间申请一个结点
(*p)->data=pred[i]; //根据pred数组生成二叉树的根结点
m=k; //m指向ind数组所存储的中序序列中第一个结点
while(ind[m]!=pred[i]) //找到根结点在中序序列所在的位置
m++;
if(m==k) //根结点是中序序列的第一个结点时则无左子树
(*p)->lchild=NULL;
else
Pre_In_order(pred,ind,i+1,i+m-k,k,m-1,&(*p)->lchild);
//根据根结点所划分出中序序列的两个部分继续构造左右子树
if(m==h) //根结点是中序序列的最后一个根结点时则无右子树
(*p)->rchild=NULL;
else
Pre_In_order(pred,ind,i+m-k+1,j,m+1,h,&(*p)->rchild);
//根据根结点所划分出中序序列的两个部分继续构造左右两颗子树。
}
//2.接下来后续遍历二叉树的递归算法:
void Postorder(BSTree *p){
if(p!=NULL){
Postorder(P->lchild); //后序遍历左子树
Postorder(P->rchild); //后序遍历右子树
printf("%3c",p->data); //访问根结点
}
}解决 无用评论 打赏 举报
悬赏问题
- ¥15 运筹学排序问题中的在线排序
- ¥15 关于docker部署flink集成hadoop的yarn,请教个问题 flink启动yarn-session.sh连不上hadoop,这个整了好几天一直不行,求帮忙看一下怎么解决
- ¥30 求一段fortran代码用IVF编译运行的结果
- ¥15 深度学习根据CNN网络模型,搭建BP模型并训练MNIST数据集
- ¥15 C++ 头文件/宏冲突问题解决
- ¥15 用comsol模拟大气湍流通过底部加热(温度不同)的腔体
- ¥50 安卓adb backup备份子用户应用数据失败
- ¥20 有人能用聚类分析帮我分析一下文本内容嘛
- ¥30 python代码,帮调试,帮帮忙吧
- ¥15 #MATLAB仿真#车辆换道路径规划