题目描述
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。
输入
输入数据有多组，每组数据第一行输入1个正整数N(1 <= N <= 50)为树中结点总数，随后2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母(区分大小写)的字符串。输出
输出一个整数，即该二叉树的高度。示例输入
9 ABDFGHIECFDHGIBEAC
示例输出
5
#include <stdio.h>#include<string.h>#include<stdlib.h>typedef char telement;typedef struct BNote{char data;struct BNote *lchild,*rchild;}*BiTree;telement pre[55],ino[55];int i;int Search(char str[51],char m)//查找字符在字符串中的位置；{for(i=0;str[i]!='\0';i++){if(str[i]==m)return i;}return -1;}void CrtBT(BiTree &T,char pre[],char ino[],int ps,int is,int n)//由先序序列中序序列建树；{//ps前序序列的起始位置，is中序序列的起始位置；n为中序序列的长度；if(n==0) T=NULL;else{int k;k=Search(ino,pre[ps]);if(k==-1) T=NULL;else{T=new BNote;if(!T) exit(0);T->data=pre[ps];if(k==is) T->lchild=NULL;elseCrtBT(T->lchild,pre,ino,ps+1,is,k-is);//注意前后序的初始位置的变化，中序序列的长度变化if(k==is+n-1) T->rchild=NULL;elseCrtBT(T->rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);//注意前后序的初始位置的变化，中序序列的长度变化}}}int depth(BiTree T)//树的深度；{int lth,rth;if(!T) return 0;else{lth=depth(T->lchild);rth=depth(T->rchild);if(lth>rth)return lth+1;return rth+1;}}int main(){int n;BiTree T;while(~scanf("%d",&n)){scanf("%s",pre);scanf("%s",ino);CrtBT(T,pre,ino,0,0,n);printf("%d\n",depth(T));}return 0;}
