判断是否为同一颗二叉搜索树（二叉排序树）

ゝ一世哀愁。 2021-11-10 07:44 384阅读 0赞

## 判断方法 ##

**1、分别建立两颗搜索树，通过递归，比较根，左子树，右子树是否相同；**  
**2、不建树的判别方法；**  
**3、只建一棵树，在判别其他序列是否与该树一致；**  
[点击显示例题链接][Link 1]

**首先：看第三种；**

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node  //结构结点
    { 
        int data;
        struct node *lson;
        struct node *rson;
        int flag; //标记变量，用来标记此节点是否查找过；
    } NODE;
    
    NODE *insert(NODE *t,int k) // 与creat函数配合完成二叉排序树的建树过程；
    { 
        if(t==NULL)
        { 
            t=(NODE *)malloc(sizeof(NODE));
            t->data=k;
            t->lson=t->rson=NULL;
            t->flag=0;
        }
        else
        { 
            if(k<t->data)
            { 
                t->lson=insert(t->lson,k);
            }
            else
            { 
                t->rson=insert(t->rson,k);
            }
        }
        return t;
    }
    
    NODE *creat(int N)
    { 
        int k,i;
        NODE *t=NULL;
        for(i=0;i<N;i++)
        { 
            scanf("%d",&k);
            t=insert(t,k);
        }
        return t;
    }
    
    int check(NODE *t,int k) //检查k是否满足：在树t中查找k时，经过的结点的flag都为1；if成立就说明k出现在序列中的位置是正确的；
    { 
        if(t->flag==1)
        { 
            if(k<t->data)
                return check(t->lson,k);
            else if(k>t->data)
                return check(t->rson,k);
            else
                return 0;
        }
        else
        { 
            if(k==t->data)
            { 
                t->flag=1;
                return 1;
            }
            else
                return 0;
        }
    }
    
    int judge(NODE *t,int N)
    { 
        int i,v;
        int F=0;//标记变量；用来标记此序列是否与第一个序列建成的二叉排序树相同；
        scanf("%d",&v);
        if(v!=t->data)//先判断第一个数与根结点是否相同；
        { 
            F=1;
        }
        else
        { 
            t->flag=1;
        }
        for(i=1;i<N;i++)//判断剩下的n-1个数；
        { 
            scanf("%d",&v);
            if((F==0)&&(check(t,v)==0))
                F=1;
        }
        if(F==1)
            return 0;
        else
            return 1;
    }
    
    void Reset(NODE *t)
    { 
        if(t)
        { 
            t->flag=0;
            Reset(t->lson);
            Reset(t->rson);
        }
    }
    
    int main()
    { 
        int N,L,i;
        NODE *T;
        while(~scanf("%d",&N)&&N!=0)
        { 
            scanf("%d",&L);
            T=creat(N);
            for(i=0; i<L; i++)
            { 
                if(judge(T,N)==1)
                    printf("Yes\n");
                else
                    printf("No\n");
                Reset(T);
            }
        }
        return 0;
    }

**第一种，就比第三种好理解多了，代码如下：**

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node
    { 
        int data;
        struct node *lson;
        struct node *rson;
    }NODE;
    
    NODE *insert(NODE *t,int k)
    { 
        if(t==NULL)
        { 
            t=(NODE *)malloc(sizeof(NODE));
            t->data=k;
            t->lson=t->rson=NULL;
        }
        else
        { 
            if(k<t->data)
            { 
                t->lson=insert(t->lson,k);
            }
            else
            { 
                t->rson=insert(t->rson,k);
            }
        }
        return t;
    }
    
    NODE *creat(int N)
    { 
        int k,i;
        NODE *t=NULL;
        for(i=0;i<N;i++)
        { 
            scanf("%d",&k);
            t=insert(t,k);
        }
        return t;
    }
    
    int flag;
    
    void judge(struct node *t1,struct node *t2)
    { 
    
        if(t1&&t2)
        { 
            if(t1->data!=t2->data)
            { 
                flag=0;
            }
            judge(t1->lson,t2->lson);
            judge(t1->rson,t2->rson);
        }
    }
    int main()
    { 
        int n,m;
        while(scanf("%d",&n)!=EOF)
        { 
            if(n==0) break;
            scanf("%d",&m);
            struct node *t1;
            t1=creat(n);
            while(m--)
            { 
                struct node *t2;
                t2=creat(n);
                flag=1;
                judge(t1,t2);
                if(flag)
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }
        return 0;
    }

**第二种方法：不用建树**

#include<stdio.h>
    
    int b1[100],b2[100];
    int s1[100],s2[100];
    int flag;
    void judge(int a[],int b[],int n)
    { 
        int i,j,k;
        int h1,h2;
        int y1,y2;
        y1=0;
        y2=0;
        if(n<=1) //递归结束条件；
            return ;
        for(j=1; j<n; j++)
        { 
            if(a[j]>a[0])
                b1[y1++]=a[j];//把比数组a中第一个数大的放到b1数组里；
            else
                s1[y2++]=a[j];//把比数组a中第一个数小的放到s1数组里；
        }
        h1=0;
        h2=0;
        for(k=1; k<n; k++)
        { 
            if(b[k]>b[0])
                b2[h1++]=b[k];//把比数组b中第一个数大的放到b1数组里；
            else
                s2[h2++]=b[k];//把比数组b中第一个数小的放到s1数组里；
        }
        if(h1!=y1||h2!=y2)
            flag=0; //如果b1,b2里的元素个数不一样，一定不是相同的二叉排序树；
        else
        { 
            for(j=0; j<h1; j++)
            { 
                if(b1[j]!=b2[j]) //比较b1，b2里每一个元素是否相同；
                    flag=0; 
            }
            for(j=0; j<h2; j++)
            { 
                if(s1[j]!=s2[j])//比较s1，s2里每一个元素是否相同；
                    flag=0;
            }
        }
        judge(b1,b2,y1); //递归b1,b2;
        judge(s1,s2,y2); //递归s1,s2;
        return ;
    }
    
    int main()
    { 
        int a[100];
        int c[100];
        int m,n,k,i,j;
        while(~scanf("%d",&n)&&n!=0)
        { 
            flag=1;
            scanf("%d",&m);
            for(i=0; i<n; i++)
                scanf("%d",&a[i]);//把标准序列放在a数组中
            for(i=0; i<m; i++)
            { 
                for(j=0; j<n; j++)
                    scanf("%d",&c[j]);//把要比较的序列放在c数组中
                judge(a,c,n);
                if(flag==1)
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }
        return 0;
    }

[Link 1]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2984/pid/3373