当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 还原二叉树

还原二叉树

2019年05月09日  | 移动技术网IT编程  | 我要评论

女子遭轮奸后称自愿,恩斯特龙f280fx,win10自动更新在哪

7-1 还原二叉树 (25 分)
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式:

输入首先给出正整数n（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为n的不包含重复英文字母（区别大小写）的字符串。

输出格式:

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

输入样例:

9
abdfghiec
fdhgibeac
输出样例:

5

include<stdio.h>

include<stdlib.h>

define max 50

typedef char elemtype;
typedef struct node *bintree;
struct node
{
elemtype data;
bintree left;
bintree right;
};
bintree recover(elemtype pre[],elemtype in[],int len)
{
bintree t;
int i;
if(!len)
return null;
else
{
t=malloc(sizeof(struct node));
t->data=pre[0];
for(i=0;i<len;i++) {
if(pre[0]==in[i])
break;
}
t->left=recover(pre+1,in,i);
t->right=recover(pre+1+i,in+i+1,len-i-1);
}
return t;
}
int gethigh(bintree t)
{
int hl,hr,maxh=0;
if(t){
hl=gethigh(t->left);
hr=gethigh(t->right);
maxh=hl>hr?hl:hr;
return (maxh+1);
}
else
return 0;
}
int main()
{
bintree tree;
elemtype preorder[max+1],inorder[max+1];
int n,h;
scanf("%d",&n);
scanf("%s",preorder);
scanf("%s",inorder);
tree=recover(preorder,inorder,n);
h=gethigh(tree);
printf("%d\n",h);
return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网