学步园

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3791

先建立二叉排序树，然后进行比较。比较时采用递归。

代码：

#include<stdio.h><br /> #include<stdlib.h><br /> #include<string.h><br /> typedef struct node{//树节点数据结构定义；<br /> int data;<br /> struct node *left,*right;<br /> }*BiTree,BTNode;</p> <p>void insert(BiTree &t, BiTree s)//插入节点；<br /> {<br /> if(s==NULL)return;<br /> BiTree p,temp;<br /> if(t==NULL){<br /> t=s;<br /> }<br /> else{<br /> p=t;<br /> while(p!=NULL){<br /> temp=p;<br /> if(s->data<p->data){//往左；<br /> p=p->left;<br /> }<br /> else{//往右；<br /> p=p->right;<br /> }<br /> }<br /> if(s->data<temp->data){//插入到左子树；<br /> temp->left=s;<br /> }<br /> else{//插入到右子树；<br /> temp->right=s;<br /> }<br /> }<br /> }</p> <p>int check(BiTree s,BiTree t){//比较两树是否相同；0表示相同，否则不相同；<br /> if(s==NULL&&t==NULL){<br /> return 0;<br /> }<br /> else if((s==NULL&&t!=NULL)||(s!=NULL&&t==NULL)){<br /> return 1;<br /> }<br /> else{<br /> if(s->data!=t->data){<br /> return 1;<br /> }<br /> else{<br /> return check(s->left,t->left)+check(s->right,t->right);<br /> }<br /> }<br /> }</p> <p>int main(){<br /> int n,len1,len2,i,result;<br /> char s[11],q[11];<br /> while(scanf("%d",&n)!=EOF){<br /> if(n==0)break;<br /> getchar();<br /> scanf("%s",s);<br /> len1=strlen(s);<br /> BiTree t;<br /> t=NULL;<br /> for(i=0;i<len1;i++)//建立示范序列的二叉树；<br /> {<br /> BiTree p;<br /> p=(BiTree)malloc(sizeof(BTNode));<br /> p->data=s[i]-'0';<br /> p->left=NULL;<br /> p->right=NULL;<br /> insert(t,p);<br /> }<br /> while(n--){<br /> scanf("%s",q);<br /> len2=strlen(q);<br /> BiTree r;<br /> r=NULL;<br /> for(i=0;i<len1;i++)//建立示范序列的二叉树；<br /> {<br /> BiTree p;<br /> p=(BiTree)malloc(sizeof(BTNode));<br /> p->data=q[i]-'0';<br /> p->left=NULL;<br /> p->right=NULL;<br /> insert(r,p);<br /> }<br /> result=check(r,t);<br /> if(result==0){<br /> printf("YES/n");<br /> }<br /> else{<br /> printf("NO/n");<br /> }<br /> }</p> <p> }<br /> }<br />