【HBU数据结构月考】7-2 还原二叉树 (30 分) 输出高度
- 2019 年 12 月 3 日
- 筆記
版权声明：本文为博主原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/shiliang97/article/details/103317279
7-2 还原二叉树 (30 分)
给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。
输入格式:
输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。
输出格式:
输出为一个整数，即该二叉树的高度。
输入样例:
9 ABDFGHIEC FDHGIBEAC
输出样例:
5
输出高度，两个函数一个生成树，一个判断树的深度。就行了
函数1：生成树
申请内存，然后存数据，递归连成树。
背下来，背下来，背下来！！！！
Tree* creat(int root,int beg ,int len){ Tree * T; int i; if(len<=0) T=NULL; else{ T=(struct Tree*)malloc(sizeof(Tree)); T->data=v1[root]; for(i=0;v1[root]!=v2[beg+i];i++); T->left=creat(root+1,beg,i); T->right=creat(root+i+1,beg+i+1,len-i-1); }return T; }
函数2：判断树的深度
递归去求深度。背下来，背下来，背下来！！！！！！
int getHight(Tree* T){ if(T){ int m=getHight(T->left); int n=getHight(T->right); if(m<n)return n+1; return m+1; }return 0; }
#include<iostream> using namespace std; struct Tree{ char data; struct Tree *left,*right; }; char v1[100000]; char v2[100000]; Tree* creat(int root,int beg ,int len){ Tree * T; int i; if(len<=0) T=NULL; else{ T=(struct Tree*)malloc(sizeof(Tree)); T->data=v1[root]; for(i=0;v1[root]!=v2[beg+i];i++); T->left=creat(root+1,beg,i); T->right=creat(root+i+1,beg+i+1,len-i-1); }return T; } int getHight(Tree* T){ if(T){ int m=getHight(T->left); int n=getHight(T->right); if(m<n)return n+1; return m+1; }return 0; } int main(){ int n; cin>>n; for(int i=0;i<n;i++)cin>>v1[i]; for(int i=0;i<n;i++)cin>>v2[i]; Tree * T=creat(0,0,n); cout<<getHight(T); return 0; }
