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

2/10/2017来源:ASP.NET技巧人气:415

sdut原题链接

数据结构实验之二叉树四:还原二叉树 Time Limit: 1000MS Memory Limit: 65536KB

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

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

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

Example Input 9 ABDFGHIEC FDHGIBEAC

Example Output 5

Hint

Author xam

以下为accepted代码

#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct node { char date; struct node *left; struct node *right; }BinTree; BinTree *root; int len; char st1[54], st2[54]; BinTree * ans(int len, char *st1, char *st2)//建立二叉树函数 { if(len == 0) return NULL; int i; BinTree *root; root = (BinTree *)malloc(sizeof(BinTree)); root->date = st1[0];//寻找根节点,新的根节点为st1的第一个 for(i = 0; i < len; i++)//寻找新的根节点在中序序列st2中的位置 { if(st2[i] == root->date) break; } root->left = ans(i, st1+1, st2);//(左子树的长度,左子树在st1中的开始位置,左子树在st2中的开始位置) root->right = ans(len-i-1, st1+i+1, st2+i+1);//(右子树的长度,右子树在st1中的开始位置,右子树在st2中的开始位置) return root; } int get_hight(BinTree *root)//计算二叉树的深度函数 { int HL, HR, MAXH; if(root) { HL = get_hight(root->left); HR = get_hight(root->right); MAXH = HL>HR? HL: HR; return (MAXH + 1); } else return 0; } int main() { int n, y; while(scanf("%d", &n) != EOF) { scanf("%s %s", st1, st2); root = ans(n, st1, st2);//调用建立二叉树函数 y = get_hight(root);//调用计算二叉树的深度函数 printf("%d\n", y); } return 0; } /*************************************************** User name: jk160630 Result: Accepted Take time: 0ms Take Memory: 116KB Submit time: 2017-02-07 19:21:23 ****************************************************/