同一棵树判定
是否是同一棵查找树
0x00 题目描述
输入输出样例：
第一行两个数字 第一个是每组序列的长度（如果为0则输入结束） 第二个是要比较的序列个数。
第二行是用来对比的树的序列
后面几组都是待比较的序列
0x01 解题思路
主要考虑关键的对比思路
方法一： 将对比序列和待对比序列都建树比较 递归的实现
freetree也是递归实现的 很有特点
#include <stdio.h>
#include <stdlib.h>
typedef struct tnode* tree;
struct tnode{
int v;
tree left;
tree right;
int flag;
};
tree createnode(int v){
tree ret=(tree)malloc(sizeof(struct tnode));
ret->flag=0;
ret->v=v;
ret->left=NULL;
ret->right=NULL;
return ret;
}
tree insert(tree t,int v){
tree ret=t;
if(!ret){
ret=createnode(v);
}else{
if(v>ret->v){
ret->right=insert(ret->right,v);
}else if(v<ret->v){
ret->left=insert(ret->left,v);
}else{
printf("已有节点！");
}
}
return ret;
}
tree maketree(int l){
tree ret=NULL;
int i;
int inputv;
for(i=0;i<l;i++){
scanf("%d",&inputv);
ret=insert(ret,inputv);
}
return ret;
}
int check(tree a,tree b){
int ret=1;
if(a&&b){
if(a->v=b->v){
ret=check(a->left,b->left);
if(ret==0) return ret;
ret=check(a->right,b->right);
return ret;
}else{
return 0;
}
}else if(!a&&!b){
return 1;
}else{
return 0;
}
}
void freetree(tree t){
if(t->left){
freetree(t->left);
}
if(t->right){
freetree(t->right);
}
if(!t->left&&!t->right){
free(t);
}
return;
};
int main(void){
int n,l;
scanf("%d",&n);
while(n){
scanf("%d",&l);
tree t=NULL;
t=maketree(n);
int i;
for(i=0;i<l;i++){
tree test=maketree(n);
printf("%s",check(t,test)?"yes\n":"no\n");
freetree(test);
}
freetree(t);
scanf("%d",&n);
}
return 0;
}
方法二：不建树，只比较序列的关系：
同样采用递归的方法实现，一个序列第一个元素是根节点，然后按照与该元素的大小关系又可以分为左子序列和右子序列。递归这个过程，就可以对每个结点进行对比 ```c int check(list a,list b){//默认a b两个是长度相等序列 不然没有判断必要,且元素都不等
if(a[0]==b[0]){
int i=0;
list al=createList();
list ar=createList();
list bl=createList();
list br=createList();
for(i=1;i<a.length;i++){
if(a[i]<a[0]) add(al,a[i]);
else add(ar,a[i]);
if(b[i]<b[0]) add(bl,b[i]);
else add(br,b[i]);
}
return check(al,bl)&&check(ar,br);
}else{
return 0;
} } ``` ##### 方法三：建一棵树，与序列比较
用第一行的数据建二叉树，然后把其余的对比序列的每一个元素在该二叉树里进行查找，如果在查找路径上有没有被访问过的节点（前面的元素查找过程中没有访问）说明位置对不上，也就是不是同一棵二叉搜索树
