还原二叉树PTA

男娘i 2022-02-04 13:43 266阅读 0赞

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

#### 输入格式: ####

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

#### 输出格式: ####

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

#### 输入样例: ####

9
    ABDFGHIEC
    FDHGIBEAC

#### 输出样例: ####

#### 代码： ####

#include<stdio.h>
    #include<stdlib.h>
    #define MAX 51
    
    typedef char ElementType;
    typedef struct node * BinTree;
    struct node{
        
    	ElementType Data;
    	BinTree zuo; //左子树
    	BinTree you; //右子树
    };
    
    BinTree Recover(ElementType Pre[MAX],ElementType In[MAX],int len); //建立二叉树
    int GetHigh(BinTree T); //计算高度
    
    int main()
    {
        
    	BinTree Tree;
    	ElementType xianxu[MAX],zhongxu[MAX];
    	int N,H;
    	scanf("%d%s%s",&N,xianxu,zhongxu);
    	Tree=Recover(xianxu,zhongxu,N);
    	H=GetHigh(Tree);
    	printf("%d\n",H);
    	return 0;
    }
    BinTree Recover(ElementType Pre[MAX],ElementType In[MAX],int len) //建立二叉树 
    {
        
    	BinTree T;
    	int i;
    	if(!len)return NULL; //如果二叉树不存在，则高度为0 
    	else
    	{
        
    		T=(BinTree)malloc(sizeof(struct node));
    		T->Data=Pre[0]; //根据先序遍历结果确定根结点 
    		for(i=0;i<len;i++) //在中序遍历结果中确定根结点的位置 
    		{
        
    			if(Pre[0]==In[i])break;
    		}
    		T->zuo=Recover(Pre+1,In,i); //由根结点分，分别建立左子树和右子树 
    		T->you=Recover(Pre+1+i,In+i+1,len-i-1);
    	}
    	return T;
    }
    int GetHigh(BinTree T) //计算高度 
    {
        
    	int l,r,max;
    	if(T)
    	{
        
    		l=GetHigh(T->zuo);
    		r=GetHigh(T->you);
    		max=l>r? l:r;
    		return max+1;
    	}
    	else return 0;
    }
    }

![在这里插入图片描述][20190507211224164.gif]

[20190507211224164.gif]: /images/20220204/e49de95f3b0046a29ba17982dc97581b.png