已知前序遍历和中序遍历求二叉树
描述
输入某二叉树的前序遍历和中序遍历的结果,请输出后序遍历序列。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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
题意:
前序遍历即先访问根节点,然后是左子树,右子树
中序遍历为先访问左子树,然后是根节点,右子树
所以通过前序遍历不断地找到根节点,然后中序遍历找到其左子树和右子树
最后就可以得到这棵二叉树,后序遍历即为 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; }