二叉排序树

淩亂°似流年 2022-09-25 06:22 7阅读 0赞

![Center][]

注意： 建立好二叉排序树之后，只需判断两个二叉排序树的前序遍历是否相同即可。

<pre name="code" class="cpp">#include<bits/stdc++.h>
    using namespace std;
    
    typedef struct node
    {
        char data;
        struct node * lchild;
        struct node * rchild;
    }node,*Tree;
    
    char a[1001],b[1001],st1[1001],st2[1001];
    int i,j;
    Tree creat(Tree &t,char x)
    {
        if(t==NULL)
        {
            t=new(node);
            t->data=x;
            t->lchild=NULL;
            t->rchild=NULL;
        }
        else
        {
            if(x<t->data)
            {
                t->lchild=creat(t->lchild,x);
            }
            else
            {
                t->rchild=creat(t->rchild,x);
            }
        }
        return t;
    }
    
    void xian(Tree &t)
    {
    
        if(t!=NULL)
        {
            a[i++]=t->data;
            xian(t->lchild);
            xian(t->rchild);
        }
    }
    
    void xiannext(Tree &t)
    {
    
        if(t!=NULL)
        {
            b[j++]=t->data;
            xiannext(t->lchild);
            xiannext(t->rchild);
        }
    }
    
    int main()
    {
        int n;
        Tree t1,t2;
        while(cin>>n&&(n!=0))
        {
            cin>>st1;
            t1=NULL;
            for( i=0;st1[i]!='\0';i++)
            {
                t1=creat(t1,st1[i]);
            }
            i=0;
            xian(t1);
            a[i]='\0';
            while(n--)
            {
                cin>>st2;
                t2=NULL;
                for( j=0;st2[j]!='\0';j++)
                {
                     t2=creat(t2,st2[j]);
                }
                j=0;
                xiannext(t2);
                b[j]='\0';
                if(strcmp(a,b))
                {
                    cout<<"NO"<<endl;
                }
                else
                {
                    cout<<"YES"<<endl;
                }
    
            }
        }
    
    }

[Center]: /images/20220718/ac095bcec534455298b60ad56180da3c.png