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

题目描述

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

输入

输入数据有多组，每组数据第一行输入1个正整数N(1 <= N <= 50)为树中结点总数，随后2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母(区分大小写)的字符串。

输出

 输出一个整数，即该二叉树的高度。

示例输入

9 ABDFGHIEC FDHGIBEAC

示例输出

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;           else             CrtBT(T->lchild,pre,ino,ps+1,is,k-is);//注意前后序的初始位置的变化，中序序列的长度变化           if(k==is+n-1) T->rchild=NULL;           else             CrtBT(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; }