游戏网站模板免费下载,小型电商网站模板,石家庄网站建设方案咨询,地方商城网站题目描述 给定一棵二叉树的先序遍历序列和中序遍历序列#xff0c;要求计算该二叉树的高度。 输入 输入数据有多组#xff0c;每组数据第一行输入1个正整数N(1 N 50)为树中结点总数#xff0c;随后2行先后给出先序和中序遍历序列#xff0c;均是长度为N的不包含重… 题目描述 给定一棵二叉树的先序遍历序列和中序遍历序列要求计算该二叉树的高度。 输入 输入数据有多组每组数据第一行输入1个正整数N(1 N 50)为树中结点总数随后2行先后给出先序和中序遍历序列均是长度为N的不包含重复英文字母(区分大小写)的字符串。 输出 输出一个整数即该二叉树的高度。示例输入 9
ABDFGHIEC
FDHGIBEAC 示例输出 5
#include stdio.h
#includestring.h
#includestdlib.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(i0;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(n0) TNULL;
else
{
int k;
kSearch(ino,pre[ps]);
if(k-1) TNULL;
else
{
Tnew BNote;
if(!T) exit(0);
T-datapre[ps];
if(kis) T-lchildNULL;
else
CrtBT(T-lchild,pre,ino,ps1,is,k-is);//注意前后序的初始位置的变化中序序列的长度变化
if(kisn-1) T-rchildNULL;
else
CrtBT(T-rchild,pre,ino,ps1(k-is),k1,n-(k-is)-1);//注意前后序的初始位置的变化中序序列的长度变化
}
}
}
int depth(BiTree T)//树的深度
{
int lth,rth;
if(!T) return 0;
else
{
lthdepth(T-lchild);
rthdepth(T-rchild);
if(lthrth)
return lth1;
return rth1;
}
}
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;
}
