欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj2255——先序中序求后序

程序员文章站 2022-05-19 20:26:14
...

之前写过一个数字的稍作修改便可以AC,对于题目要求以文本结束则结束程序需要输入不为EOF即可。

#include<stdio.h>
#include<string.h>
typedef struct btnode{
    char data;
    struct btnode *left;
    struct btnode *right;
}treenode;
treenode *gettree(int prel,int prer,int inl,int inr,char preorder[],char inorder[]){
    if(prel>prer)
        return NULL;
    treenode *root;     
    root=new treenode;
    root->data=preorder[prel];
    if(prel==prer){
        root->left=NULL;
        root->right=NULL;
        return root;
    }
    int temp;
    for(int i=1;i<=inr;i++)
        if(inorder[i]==preorder[prel]){
            temp=i;
            break;
        }
    root->left=gettree(prel+1,prel+(temp-inl),inl,temp-1,preorder,inorder);
    root->right=gettree(prel+(temp-inl)+1,prer,temp+1,inr,preorder,inorder);
    return root;
}
void postorder(treenode *t){
    if(t!=NULL){
        postorder(t->left);
        postorder(t->right);
        printf("%c",t->data);
    }
}
int main(){
    char preorder[101];
	char inorder[101];	
	while(scanf("%s%s",preorder,inorder)!=EOF){
    	int n=strlen(preorder);
		treenode *tree=gettree(0,n-1,0,n-1,preorder,inorder);
    	postorder(tree);
    	printf("\n");
    }
    return 0;
}