#include<iostream>usingnamespacestd;typedefstructnode{intx;node*lc;node*rc;node(){}node(intxx){x=xx;lc=NULL;rc=NULL;}}*BiTree;//intss[]={1,2,3,0,0,4,0,0,5,6,0,0,7,0,0};intsi=0;//intss[]={1,2,-3,0,0,-4,0,0,5,-6,0,0,7,0,0};intsi=0;//sum=7intss[]={1,2,3,0,0,4,0,0,5,-6,0,0,7,0,0};intsi=0;//sum=16BiTreeTb;BiTreeTc;voidCreat(BiTree&T){intd=ss[si++];if(d==0)T=NULL;else{T=newnode(d);Creat(T->lc);Creat(T->rc);}}voidprint(node*root,intbase){//neadcreatnewstylesetw(x)if(root){print(root->rc,base+1);for(inti=0;i<base;i++)cout<<"*";if(root->x>0)cout<<""<<root->x<<endl;elsecout<<root->x<<endl;print(root->lc,base+1);}elsereturn;}intsum=0;boolflag=false;voidmaxsum(node*root){if(root==NULL)return;if(root->lc){maxsum(root->lc);root->x+=root->lc->x;}if(root->rc){maxsum(root->rc);root->x+=root->rc->x;}if(flag){if(root->x>sum)sum=root->x;}else{sum=root->x;flag=true;}}intsonTree(node*Tb,node*T){if(Tb){if(Tb==T)return1;returnsonTree(Tb->lc,T)+sonTree(Tb->rc,T);}elsereturn0;}inta[20]={0};intb[20]={0};intxx[20]={0};intxi=0;//先序遍历voidDLR(BiTreeT){if(T){//cout<<T->x<<'';xx[xi++]=T->x;DLR(T->lc);DLR(T->rc);}}//中序遍历voidLDR(BiTreeT){if(T){LDR(T->lc);//cout<<T->x<<'';xx[xi++]=T->x;LDR(T->rc);}}//后序遍历voidLRD(BiTreeT){if(T){LRD(T->lc);LRD(T->rc);//cout<<T->x<<'';xx[xi++]=T->x;}}voidcopy(int*xx,int*ab){inti;for(i=0;i<20;i++){ab[i]=xx[i];xx[i]=0;}}voidclear(int*array){for(inti=0;i<20;i++)array[i]=0;}intmatch(int*a,int*b){inti=0,j=0,r=0;intstate=-1;cout<<b[3]<<endl;while(a[i]!=0){j=0;r=i;while(a[r]==b[j]){if(a[r]==b[j])state=1;elsestate=-1;if(b[j]==0)break;j++;r++;}i++;}returnstate;}intsonTree2(node*Tb,node*T){intf1,f2,f3;f1=f2=f3=0;//DLRf1DLR(T);copy(xx,a);xi=0;DLR(Tb);copy(xx,b);f1=match(b,a);if(f1==0)return0;cout<<"--------------------------------------"<<endl;//LDRf2//for(inti=0;i<20;i++){cout<<a[i]<<","<<b[i]<<endl;}xi=0;LDR(T);copy(xx,a);xi=0;LDR(Tb);copy(xx,b);//for(inti=0;i<20;i++){cout<<a[i]<<","<<b[i]<<endl;}f2=match(b,a);if(f2==0)returnf2;//LRDf3xi=0;LRD(T);copy(xx,a);xi=0;LRD(Tb);copy(xx,b);f3=match(b,a);if(f3==0)return0;returnf1&&f2&&f3;//f4/********************11115566前序中序后序都匹配后还有一个特殊情况不是TC->LC->x=TB->LC->xTC->RC->X=TB->RC->X*******************/}intmain(){cout<<"--------test1---------------"<<endl;BiTreeT;Creat(T);//print(T,4);maxsum(T);//cout<<"sum="<<sum<<endl;//print(T,4);cout<<"--------test2Tb---------------"<<endl;si=0;Creat(Tb);//print(Tb,4);cout<<"--------test2Tb,T---------------"<<endl;Tb->rc=T;//print(Tb,4);//cout<<sonTree(Tb,T)<<endl;cout<<"--------test3---------------"<<endl;si=0;Creat(Tc);//print(Tc,4);cout<<"--------test3Tc,T---------------"<<endl;//cout<<sonTree(Tb,Tc)<<endl;cout<<"--------test3Tb---------------"<<endl;//Tb->lc=Tc;//print(Tb,4);//cout<<sonTree(Tb,Tc)<<endl;cout<<"--------test4Tb---------------"<<endl;//cout<<sonTree(Tb,Tc->lc)<<endl;//0cout<<sonTree2(Tb,Tc->lc)<<endl;//1//cout<<sonTree2(Tb,Tc->rc)<<endl;//1must0;return0;}