已知后序遍历和中序遍历求二叉树-白红宇

已知后序遍历和中序遍历求二叉树

阅读量：4046 次

发布时间：2019-05-25

本文共 1493 字，大约阅读时间需要 4 分钟。

描述

输入某二叉树的后序遍历和中序遍历的结果，请输出前序遍历序列。假设输入的后序遍历和中序遍历的结果中都不含重复的数字。例如输入后序遍历序列{7,1,4,2,5,8,6,3,1}和中序遍历序列{4,7,2,1,5,3,8,6}，重建二叉树并返回后序遍历序列

输入

输入某二叉树的后序遍历和中序遍历的结果

输出

输出前序遍历序列

输入样例 1

7 4 2 5 8 6 3 1
4 7 2 1 5 3 8 6

输出样例 1

1 2 4 7 3 5 6 8

参考题目详解：

实现代码：

#include
   
    #include
    
      #include
     
      typedef struct node* BinTree; struct node{	int date;	BinTree left;	BinTree right;};BinTree Build(int post[] ,int in[],int size){	if(size<=0)return NULL;	//先在中序中找到根节点	int i=0;	for(i=0;i
      
       date=post[size-1];	tree->left=Build(post,in,i);	tree->right=Build(post+i,in+i+1,size-1-i);	return tree;} void preorder(BinTree T)  //前序遍历{	if(T==NULL)return;	else{	    printf("%d ",T->date);		preorder(T->left);		preorder(T->right);	}	} int main(){	char postt[800],inn[800];  	gets(postt);	gets(inn);  	int size=strlen(postt);  	int post[800],in[800];	int postcount=0; 	int i;	for(i=0;i
       
        ='0'&&postt[i]<='9')			{				//此if-else 用来转换多位数为int类型 				if(postt[i-1]==' ')  //如果前一个元素为空格 				{					postcount++;				    post[postcount]=postt[i]-'0';				}								else  //如果前一个元素不是空格，那么说明与前一个元素一同构成的数  例如：10 				{					post[postcount]=post[postcount]*10+(postt[i]-'0');				}			}					}			}	int incount=0;	for(i=0;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(postcount==incount&&postcount!=0) { BinTree T; T=Build(post,in,postcount+1); preorder(T); } return 0;}