数据结构实验之二叉树四：还原二叉树

数据结构实验之二叉树四：还原二叉树

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

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

输入

输入数据有多组，每组数据第一行输入 1 个正整数 N(1 <= N <= 50) 为树中结点总数，随后 2 行先后给出先序和中序遍历序列，均是长度为 N 的不包含重复英文字母 ( 区分大小写 ) 的字符串。

输出

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

示例输入

9 ABDFGHIEC FDHGIBEAC

示例输出

5

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <queue> using namespace std; typedef struct TNode {     char data;     TNode *Lchild;     TNode *Rchild; } TNode; TNode* restore(char* pre,char* in,  int length) { //先还原二叉树     if(length == 0)     {         return NULL ;     }     TNode* node=new TNode;     node->data=*pre;     int r=0;     for(  ; r< length; r++)     {         if(in[r] == *pre)             break;     }     node->Lchild = restore(pre+1,in,r);     node->Rchild= restore(pre+r+1,in+r+1,length-(r+1));     //cout<<node->data;     return node; }

int Height(TNode *T){//求出树的高度

    int m,n,He;     if(!T) He=0;     else {         m=Height(T->Lchild);         n=Height(T->Rchild);         He=1+(m>n?m:n);     }     return He; }  int main()  {      int n,H;      while(cin>>n)      {          char pre[60],in[60];          cin>>pre>>in;          TNode *Ti;          Ti=restore(pre,in,n);          H=Height(Ti);          cout<<H<<endl;      }  }