大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
描述
输入某二叉树的前序遍历和中序遍历的结果，请输出后序遍历序列。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，重建二叉树并返回后序遍历序列
输入
输入某二叉树的前序遍历和中序遍历的结果
输出
输出后序遍历序列
输入样例 1
1 2 4 7 3 5 6 8
4 7 2 1 5 3 8 6
输出样例 1
7 4 2 5 8 6 3 1
题意：
前序遍历即先访问根节点，然后是左子树，右子树
中序遍历为先访问左子树，然后是根节点，右子树
所以通过前序遍历不断地找到根节点，然后中序遍历找到其左子树和右子树
![已知前序遍历和中序遍历求二叉树[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
![已知前序遍历和中序遍历求二叉树[通俗易懂]](https://img-blog.csdn.net/20180917181639672)
![已知前序遍历和中序遍历求二叉树[通俗易懂]](https://img-blog.csdn.net/20180917181703154)
![已知前序遍历和中序遍历求二叉树[通俗易懂]](https://img-blog.csdn.net/2018091718171837)
![已知前序遍历和中序遍历求二叉树[通俗易懂]](https://img-blog.csdn.net/20180917181733547)
![已知前序遍历和中序遍历求二叉树[通俗易懂]](https://img-blog.csdn.net/20180917181745625)
![已知前序遍历和中序遍历求二叉树[通俗易懂]](https://img-blog.csdn.net/20180917181808614)
最后就可以得到这棵二叉树，后序遍历即为 7 4 2 5 8 6 3 1
实现代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node* BinTree;
struct node{
int date;
BinTree left;
BinTree right;
};
BinTree Build(int pre[] ,int in[] ,int size)
{
if(size<=0)return NULL;
//先在中序中找到根节点
int i;
for(i=0;i<size;i++)
{
if(in[i]==pre[0])break;
}
BinTree tree=(BinTree)malloc(sizeof(struct node));
tree->date=pre[0];
tree->left=Build(pre+1,in,i);
tree->right=Build(pre+i+1,in+i+1,size-1-i);
return tree;
}
void postorder(BinTree T) //后序遍历
{
if(T==NULL)return;
else{
postorder(T->left);
postorder(T->right);
printf("%d ",T->date);
}
}
int main()
{
char pree[800],inn[800];
gets(pree);
gets(inn);
int size=strlen(pree);
int pre[800],in[800];
int precount=0;
int i;
for(i=0;i<size;i++)
{
if(i==0)
{
pre[precount]=pree[i]-'0';
}
else
{
if(pree[i]>='0'&&pree[i]<='9')
{
//此if-else 用来转换多位数为int类型
if(pree[i-1]==' ') //如果前一个元素为空格
{
precount++;
pre[precount]=pree[i]-'0';
}
else //如果前一个元素不是空格，那么说明与前一个元素一同构成的数 例如：10
{
pre[precount]=pre[precount]*10+(pree[i]-'0');
}
}
}
}
int incount=0;
for(i=0;i<size;i++)
{
if(i==0)
{
in[incount]=inn[i]-'0';
}
else
{
if(inn[i]>='0'&&inn[i]<='9')
{
if(inn[i-1]==' ')
{
incount++;
in[incount]=inn[i]-'0';
}
else
{
in[incount]=in[incount]*10+(inn[i]-'0');
}
}
}
}
//如果前序遍历的结点数与中序遍历的结点数相同且不为0，那么可以找到对应二叉树
if(precount==incount&&precount!=0)
{
BinTree T;
T=Build(pre,in,precount+1);
postorder(T);
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/195213.html原文链接：https://javaforall.net
