数据结构实验之二叉树四：还原二叉树

PRoblem Description

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

Input

Output

Example Input

9 ABDFGHIECFDHGIBEAC
Example Output
5
 
#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct node{    char data;    struct node *lc,*rc;}bitree;int max;bitree * create(int zlen,char qst[],char zst[]){    if(zlen<=0)        return NULL;    int i;    bitree * t;    t=(bitree *)malloc(sizeof(bitree));    t->data=qst[0];    for(i=0;i<zlen;i++)    {        if(qst[0]==zst[i])            break;    }    t->lc=create(i,qst+1,zst);    t->rc=create(zlen-i-1,qst+i+1,zst+i+1);    return t;}void preshow(int count,bitree *t){    int k;    if(t)    {        if(count==0)            count=1;        k=count;        if(k>max)            max=k;        preshow(++count,t->lc);        preshow(++k,t->rc);    }}int main(){    int zlen;    char qst[51],zst[51];    bitree * tree;    while(scanf("%d",&zlen)!=EOF)    {        max=0;        scanf("%s%s",qst,zst);        zlen=strlen(zst);        tree=create(zlen,qst,zst);        preshow(0,tree);        printf("%d/n",max);    }}