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

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

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

输入样例:
9
ABDFGHIEC
FDHGIBEAC
结尾无空行
输出样例:
5
我用的书上的方法写的错误代码

#include<stdio.h>
typedef char datatype;
typedef struct bitnode
{
    datatype data;
    struct bitnode*lchild,*rchild;
}BiTNode,*BiTree;
BiTree Initiate();//二叉树初始化
BiTree Initiate()
{
  BiTNode *bt;
  bt=(BiTNode*)malloc(sizeof(BiTNode));
  bt->lchild=NULL;
  bt->rchild=NULL;
  return bt;
}
void ReBiTree(char preod[],char inod[],int n,BiTree*root);
void ReBiTree(char preod[],char inod[],int n,BiTree*root)
{
    if(n<=0)*root=NULL;
    else
        PreInOd(preod,1,n,inod,1,n,root);
}
void PreInOd(char preod[],int i,int j,char inod[],int k,int h,BiTree *t);
void PreInOd(char preod[],int i,int j,char inod[],int k,int h,BiTree *t)
{
    int m;
    *t=(BiTNode*)malloc(sizeof(BiTNode));
    (*t)->data=preod[i];
    m=k;
    while(inod[m]!=preod[i])
        m++;
    if(m==k)(*t)->lchild=NULL;
    else
        PreInOd(preod,i+1,i+m-k,inod,k,m-1,&((*t)->lchild));
    if(m==h)(*t)->rchild=NULL;
    else
        PreInOd(preod,i+m-k+1,j,inod,m+1,h,&((*t)->rchild));
}
void PrintTree(BiTree t);
void PrintTree(BiTree t)
{
    if(t==NULL)return ;
    PrintTree(t->lchild);
PrintTree(t->rchild);
    printf("%c",t->data);
}
int main()
{
    int n;
    scanf("%d",&n);
    datatype str1[n];
    datatype str2[n];
    scanf("%s%s",str1,str2);
    BiTree t=(BiTree)malloc(sizeof(BiTNode));
    ReBiTree(str1,str2,n,&t);
    printf("1");
    PrintTree(t);

}

正确代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
    char elem;
    struct node *left,*right;
};
typedef struct node * Tree;
char in[55],pre[55];
Tree findTree(char in[],char pre[],int length){//根据中序，先序建树
    if(length==0) return NULL;
    Tree head=(Tree)malloc(sizeof(struct node));
    head->elem=pre[0];
    int i=0;
    for(i=0;i<length;i++){
        if(in[i]==pre[0]) break;//找分界点
    }
    head->left=findTree(in,pre+1,i);//他这是直接用数组的位置表示的开始下标，再用个长度就可以表示结尾位置了
    head->right=findTree(in+i+1,pre+i+1,length-i-1);
    return head;
}
int length(Tree head){
    if(head==NULL) return 0;
    int l=length(head->left);
    int r=length(head->right);
    return l>r?l+1:r+1;
}
int main(){
    int n;
    scanf("%d",&n);
    scanf("%s%s",pre,in);
    Tree head=(Tree)malloc(sizeof(struct node));
    head=findTree(in,pre,n);
    printf("%d\n",length(head));
return 0;
}

唉，我能看懂，就是写不出来，思路也清楚
不知道哪里出错了

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
    char elem;
    struct node *left,*right;
};
typedef struct node * Tree;
char in[55],pre[55];
Tree PreInOd(char pre[],int i,int j,char in[],int k,int h);//书上的函数哦
Tree PreInOd(char pre[],int i,int j,char in[],int k,int h)
{
    if((j-i)<=0)return NULL;

      Tree head=(Tree)malloc(sizeof(struct node));
    head->elem=pre[0];
    int m=k;
    printf("hahah");
    while(in[m]!=pre[i])
        m++;
        printf("laa");

      head->left=PreInOd(pre,i+1,i+m-k,in,k,m-1);

        head->right=PreInOd(pre,i+m-k+1,j,in,m+1,h);
    return head;


}
/*Tree findTree(char in[],char pre[],int length){
    if(length==0) return NULL;
    Tree head=(Tree)malloc(sizeof(struct node));
    head->elem=pre[0];
    int i=0;
    for(i=0;i<length;i++){
        if(in[i]==pre[0]) break;
    }
    head->left=findTree(in,pre+1,i);
    head->right=findTree(in+i+1,pre+i+1,length-i-1);
    return head;
}*/
int length(Tree head){
    if(head==NULL) return 0;
    int l=length(head->left);
    int r=length(head->right);
    return l>r?l+1:r+1;
}
void printTree(Tree t);
void printTree(Tree t)
{
   if(t==NULL)return ;
    printf("%c",t->elem);
    printTree(t->left);
    printTree(t->right);
}
int main(){
    int n;
    scanf("%d",&n);
    scanf("%s%s",pre,in);
    Tree head=(Tree)malloc(sizeof(struct node));
//    head=findTree(in,pre,n);
head=PreInOd(pre,1,n,in,1,n);
    printTree(head);
    printf("\n");
    printf("%d\n",length(head));
return 0;
}

耶！写出来了，就是在递归调用的时候它的起始应该是从0开始，但我写的都是从1开始，改了就OK了

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
    char elem;
    struct node *left,*right;
};
typedef struct node * Tree;
char in[55],pre[55];
Tree PreInOd(char pre[],int i,int j,char in[],int k,int h);
Tree PreInOd(char pre[],int i,int j,char in[],int k,int h)
{
    if((j-i)<0)return NULL;

      Tree head=(Tree)malloc(sizeof(struct node));
    head->elem=pre[i];
    int m=k;

    while(in[m]!=pre[i])
       {
          m++;
       }




      head->left=PreInOd(pre,i+1,i+m-k,in,k,m-1);

        head->right=PreInOd(pre,i+m-k+1,j,in,m+1,h);
    return head;


}

int length(Tree head){
    if(head==NULL) return 0;
    int l=length(head->left);
    int r=length(head->right);
    return l>r?l+1:r+1;
}
void printTree(Tree t);
void printTree(Tree t)
{
   if(t==NULL)return ;
    printf("%c",t->elem);
    printTree(t->left);
    printTree(t->right);
}
int main(){
    int n;
    scanf("%d",&n);
    scanf("%s%s",pre,in);
    Tree head=(Tree)malloc(sizeof(struct node));
//    head=findTree(in,pre,n);
head=PreInOd(pre,0,n,in,0,n);
    printTree(head);
    printf("\n");
    printf("%d\n",length(head));
return 0;
}

还有一种方法就是不用建树，直接用那个求树高递归，它本来求树高的程序如下

int length(Tree head){
    if(head==NULL) return 0;
    int l=length(head->left);
    int r=length(head->right);
    return l>r?l+1:r+1;
}

这个是直接在已建好树的情况下去递归求树高，还可以直接递归

#include <stdio.h>

int max(int a,int b){
    return a>b?a:b;
}

int Depth(char* pre,char* in,int n);//求给定先序和中序序列对应的树的高度

int main()
{
    int n;//声明变量存储树的节点个数.
    scanf("%d",&n);
    char pre[n+1],in[n+1];  //声明字符数组分别存储先序和中序遍历序列
    scanf("%s",pre);//读入先序序列
    scanf("%s",in);//读入中序序列
    printf("%d",Depth(pre,in,n));//输出先序和中序序列对应的树的高度
    return 0;
}

int Depth(char* pre,char* in,int n)   //pre:先序序列;   in:中序序列;    n:节点个数;
{
    int left,right,i;
    if(n == 0)    //若没有结点，为空树
    {
        return 0;
    }
    for(i = 0; i < n; i++)
    {
        if(in[i] == pre[0])  //找到根结点在中序的位置
        {
            break;
        }
    }
    left = Depth(pre+1,in,i);  //左子树的深度
    right = Depth(pre+i+1,in+i+1,n-i-1);   //右子树的深度
    return max(left,right)+1;  //返回左右子树深度的较大值中的较大值+根结点
}