HDU – 3791 建立二叉搜索树

题意：

给定一个序列，下面又有n个序列，判断这个序列和其他序列是否为同一个二叉树（同一序列数字各不相同）

思路：

首先讲将一个序列建立成二叉搜索树，然后将其他序列也建立二叉搜索树，两个树进行前序遍历，看他们的结果是否完全相同。

二叉搜索树概念： 左儿子小于父亲节点，父亲节点小于等于右儿子

#include<stdio.h>
#include<iostream>
using namespace std;
struct node
{
    int val;//当前节点的值
    node *lch,*rch;//左右子树结构体指针  指向结构体的指针变量
};
int a[20],b[20],k;
node *insert(node *p,int x)//传进来一个结构体地址 以及要插入的值
{
    if(p==NULL)
    {
        node *q=new node;//新节点，新的建立结构体
        q->val=x;
        q->lch=q->rch=NULL;
        return q;
    }
    else
    {
        if(x<p->val) p->lch=insert(p->lch,x);//递归 直到找到可以插入的位置
        else p->rch=insert(p->rch,x);
        return p;
    }
}
void find(node *p,int a[])
{
    if(p!=NULL)
    {
        a[k++]=p->val;
        find(p->lch,a);
        find(p->rch,a);
    }
}
int main()
{
    int n;
    char c[20];
    while(~scanf("%d",&n)&&n)
    {
        scanf("%s",c);
        node *p=NULL;//建立二叉树
        for(int i=0; c[i]!='\0'; i++)
            p=insert(p,c[i]-'0');//可能不断更新祖先的地址
        k=0;
        find(p,a);//前序递归遍历
        while(n--)
        {
            int x,h=k;
            node *q=NULL;
            scanf("%s",c);
            for(int i=0;c[i]!='\0'; i++)
                q=insert(q,c[i]-'0');
            k=0;
            find(q,b);
            int f=0;
            for(int i=0; i<k; i++)
                if(a[i]!=b[i])
                    f=1;
            if(f)
                printf("NO\n");
            else
                printf("YES\n");
        }
    }
    return 0;
}