二叉搜索树

前序遍历和中序遍历可以唯一确定一棵二叉树，而对二叉排序树而言，相同元素的二叉排序树中序遍历一定相同，而不同元素二叉排序树使用前序遍历就可以发现不相同，所以只需要前序遍历两个二叉树，比较一下就可以判断，下面是代码：

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
struct node
{
    char val;
    node *lchild, *rchild;
    node(int v):val(v), lchild(NULL), rchild(NULL){}
};
bool flag;
node *insert(node *root, int x) //依次插入每个值
{
    if (root == NULL) //节点为空时，插入此节点
    {
        root = new node(x);
        return root;
    }
    if (root->val > x)                         //如果这个值小于左儿子
        root->lchild = insert(root->lchild, x); //递归向下寻找相应的位置，回溯赋值，构建链表
    else                                        //同理
        root->rchild = insert(root->rchild, x);
    return root;
}
void check(node *root, node *judge) //传入标准树和判断树的地址
{
    if (root != NULL && judge != NULL) //如果两个地址都不为空，即此节点两棵树都有值，只需判断值是否相同
    {
        if (root->val != judge->val)      //判断此节点的值是否和标准树一致
            flag = false;
        check(root->lchild, judge->lchild); //前序遍历
        check(root->rchild, judge->rchild);
    }
    else if (root != NULL || judge != NULL) //如果两颗树中，只有一棵树在这个节点有值，那么这两棵树肯定不一致
        flag = false;
}
int main()
{
    int n;
    while (~scanf("%d", &n) && n)
    {
        node *root = NULL; //标准树地址为空
        string s;
        cin >> s;
        for (int i = 0, len = s.length(); i < len; i++) //构建一颗标准树
            root = insert(root, s[i]);
        for (int i = 0; i < n; i++) //n组数据
        {
            flag = true;       //标记
            node *judge = NULL; //判断树地址为空
            cin >> s;
            for (int i = 0, len = s.length(); i < len; i++) //构建判断树
                judge = insert(judge, s[i]);
            check(root, judge); //中序遍历，检查两棵树是否一致
            if (flag)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
}