PTA练习题：还原二叉树

小咪咪 2023-02-11 15:26 6阅读 0赞

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

输入格式:

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

输出格式:

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

输入样例:

9  
ABDFGHIEC  
FDHGIBEAC  
输出样例:

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    BinTree SetBinTree(char per[],char od[]);
    int GetIndex(char s[],char c);
    int GetHeight( BinTree BT );
    
    int i = 0;
    
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	getchar();
    	char per[51];
    	char od[51];
    	gets(per);
    	gets(od);
    	BinTree BT = SetBinTree(per,od);
    	printf("%d\n",GetHeight(BT));
    	return 0;
    }
    
    BinTree SetBinTree(char per[],char od[])
    {
    	int x = GetIndex(od,per[i]);
    	if( x == -1)
    	{
    		i--;
    		return NULL;
    	}
    	BinTree T = (BinTree)malloc(sizeof(struct TNode));
    	T->Data = per[i];
    	char od1[51];
    	char od2[51];
    	int count1 = 0;
    	int count2 = 0;
    	for(int j=0;j<x;j++)
    	{
    		od1[count1++] = od[j];
    	}
    	for(int j=x+1;od[j]!='\0';j++)
    	{
    		od2[count2++] = od[j];
    	}
    	i++;
    	T->Left = SetBinTree(per,od1);
    	i++;
    	T->Right = SetBinTree(per,od2);
    	return T;
    }
    int GetIndex(char s[],char c)
    {
    	for(int i=0;s[i]!='\0';i++)
    	{
    		if(s[i] == c)
    		{
    			return i;
    		}
    	}
    	return -1;
    }
    int GetHeight( BinTree BT )
    {
    	if(BT == NULL)
    	{
    		return 0;
    	}
    	return GetHeight(BT->Left)+1>GetHeight(BT->Right)+1? GetHeight(BT->Left)+1:GetHeight(BT->Right)+1;
    }