数据结构实验之二叉树八：（中序后序）求二叉树的深度

Description

已知一颗二叉树的中序遍历序列和后序遍历序列，求二叉树的深度。

Input

输入数据有多组，输入T，代表有T组数据。每组数据包括两个长度小于50的字符串，第一个字符串表示二叉树的中序遍历，第二个表示二叉树的后序遍历。

Output

输出二叉树的深度。

Sample

Input

2
dbgeafc
dgebfca
lnixu
linux

Output

4
3

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 typedef struct node
  5 {
  6     char data;
  7     struct node *left;
  8     struct node *right;
  9 }tree;
 10 char str1[100],str2[100];
 11 tree *root,*link[54];
 12  
 13  
 14 //str1为前序,str2为中序 求层序
 15 tree *get_build(int len,char *str1,char *str2)
 16 {
 17     if(len==0)
 18         return NULL;
 19     int i;
 20     tree *root;
 21     root=(tree *)malloc(sizeof(tree));
 22     root->data=str1[0];
 23     for(i=0;i<len;i++)
 24     {
 25         if(str2[i]==root->data)
 26             break;
 27     }
 28     root->left=get_build(i,str1+1,str2);
 29     root->right=get_build(len-i-1,str1+i+1,str2+i+1);
 30     return root;
 31 }
 32  
 33 int high(tree *root)//求二叉树的高度
 34 {
 35     int n,m;
 36     if(root==NULL)
 37         return 0;
 38     else
 39     {
 40         n=high(root->left);
 41         m=high(root->right);
 42         if(n>m)
 43             return n+1;
 44         else
 45             return m+1;
 46     }
 47 }
 48  
 49  
 50 void ans(tree *root)//层序遍历序列
 51 {
 52     if (root)
 53     {
 54         int i=0,j=0;
 55         link[j++]=root;
 56         while(i<j)
 57         {
 58             if(link[i])
 59             {
 60                 link[j++]=link[i]->left;
 61                 link[j++]=link[i]->right;
 62                 printf("%c",link[i]->data);
 63             }
 64             i++;
 65         }
 66     }
 67 }
 68  
 69  
 70 void post(tree *root)//后序遍历序列
 71 {
 72     if (root)
 73     {
 74         post(root->left);
 75         post(root->right);
 76         printf("%c",root->data);
 77     }
 78  
 79 }
 80  
 81  //str1中序遍历 ,str2后序遍历 求先序遍历
 82 tree *creat(int len,char *str1,char *str2)
 83 {
 84     if(len==0)
 85         return NULL;
 86     int i;
 87     tree *root;
 88     root = (tree *)malloc(sizeof(tree));
 89     root->data=str2[len-1];
 90     //printf("%c",root->data);
 91     for(i=0; i<len; i++)
 92     {
 93         if(str1[i]==str2[len-1])
 94             break;
 95     }
 96     root->left =creat(i,str1,str2);
 97     root->right = creat(len-i-1,str1+i+1,str2+i);
 98     return root;
 99 }
100  
101  
102  
103  
104 int main()
105 {
106     int t,len;
107     scanf("%d",&t);
108     while(t--)
109     {
110         //memset(str1,0,sizeof(str1));
111         //memset(str2,0,sizeof(str2));
112         scanf("%s %s",str1,str2);
113         len=strlen(str1);
114         //root=get_build(t,str1,str2);
115         //post(root);
116         //printf("
");
117         //ans(root);
118         //printf("
");
119         root=creat(len,str1,str2);
120         printf("%d
",high(root));
121         //printf("
");
122     }
123  
124     return 0;
125 }