給定一棵二叉樹的先序遍歷序列和中序遍歷序列,要求計算該二叉樹的高度。
9 ABDFGHIEC FDHGIBEAC
5
DQE:
本題為恢復二叉樹,給出先序序列及中序序列,在二叉樹的恢復問題中,已知先序和中序或者已知後序和中序即可恢復二叉樹,原理為先序和後序可以獲得根節點,從而分割中序序列得到左子樹及右子樹的中序序列,由此遞歸完成二叉樹的恢復,本題采用指針+引用遞歸恢復,需對指針有一定的理解再閱讀本代碼。
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 struct Tree 7 { 8 char c; 9 Tree *lt,*rt; 10 }; 11 12 Tree *creat(char *&xx,char *zx) 13 { 14 if(*zx=='\0') 15 return NULL; 16 char *x,*y; 17 Tree *r=new Tree; 18 int i=0; 19 while(zx[i]!='\0') 20 { 21 if(*xx==zx[i]) 22 { 23 r->c=zx[i]; 24 zx[i]='\0'; 25 x=zx; 26 y=zx+i+1; 27 xx++; 28 r->lt=creat(xx,x); 29 r->rt=creat(xx,y); 30 break; 31 } 32 i++; 33 } 34 return r; 35 } 36 37 int dev(Tree *r) 38 { 39 if(r==NULL) 40 return 0; 41 int l=dev(r->lt),rr=dev(r->rt); 42 int m=l>rr?l:rr; 43 return m+1; 44 } 45 46 int main() 47 { 48 char xx[55],zx[55],*p; 49 Tree *root; 50 int n; 51 while(scanf("%d",&n)!=EOF) 52 { 53 scanf("%s%s",xx,zx); 54 p=xx; 55 root=creat(p,zx); 56 printf("%d\n",dev(root)); 57 } 58 return 0; 59 } 60 61 /*************************************************** 62 User name: *** 63 Result: Accepted 64 Take time: 0ms 65 Take Memory: 160KB 66 Submit time: 2016-11-03 19:06:10 67 ****************************************************/