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

2022-11-02 15:21:23

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

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic

Problem Description

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

Input

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

Output

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

Example Input

9

ABDFGHIEC

FDHGIBEAC

Example Output

5

DQE：

本题为恢复二叉树，给出先序序列及中序序列，在二叉树的恢复问题中，已知先序和中序或者已知后序和中序即可恢复二叉树，原理为先序和后序可以获得根节点，从而分割中序序列得到左子树及右子树的中序序列，由此递归完成二叉树的恢复，本题采用指针+引用递归恢复，需对指针有一定的理解再阅读本代码。

 #include <iostream>

 #include <cstdio>

 using namespace std;

 struct Tree

 {

     char c;

     Tree *lt,*rt;

 };

 Tree *creat(char *&xx,char *zx)

 {

     if(*zx=='\0')

         return NULL;

     char *x,*y;

     Tree *r=new Tree;

     int i=;

     while(zx[i]!='\0')

     {

         if(*xx==zx[i])

         {

             r->c=zx[i];

             zx[i]='\0';

             x=zx;

             y=zx+i+;

             xx++;

             r->lt=creat(xx,x);

             r->rt=creat(xx,y);

             break;

         }

         i++;

     }

     return r;

 }

 int dev(Tree *r)

 {

     if(r==NULL)

         return ;

     int l=dev(r->lt),rr=dev(r->rt);

     int m=l>rr?l:rr;

     return m+;

 }

 int main()

 {

     char xx[],zx[],*p;

     Tree *root;

     int n;

     while(scanf("%d",&n)!=EOF)

     {

         scanf("%s%s",xx,zx);

         p=xx;

         root=creat(p,zx);

         printf("%d\n",dev(root));

     }

     return ;

 }

 /***************************************************

 User name: ***

 Result: Accepted

 Take time: 0ms

 Take Memory: 160KB

 Submit time: 2016-11-03 19:06:10

 ****************************************************/

码农公寓