PTA练习题：还原二叉树-向日葵屋

PTA练习题：还原二叉树

小咪咪 2023-02-11 15:26 22阅读 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;
}