//既然表哥们都用前序和后序来判断BST是否相等
//那我换种：用层次遍历序列来判断
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;
vector<int>a,b;
struct node
{
    char data;
    node *lchild,*rchild;
};
void layerorder(node *root,vector<int>&v)
{
    queue<node*>q;
    q.push(root);
    while(!q.empty())
    {
        node *now=q.front();
        q.pop();
        v.push_back(now->data);
        if(now->lchild!=NULL)
            q.push(now->lchild);
        if(now->rchild!=NULL)
            q.push(now->rchild);
    }
}
void insert(node *&root,int x)
{
    if(root==NULL)
    {
        root=new node;
        root->data=x;
        root->lchild=root->rchild=NULL;
    }
    else if(x<root->data)
        insert(root->lchild,x);
    else
        insert(root->rchild,x);
}
int main()
{
    int n;
    string temp,str;
    while(cin>>n&&n)
    {
        cin>>temp;
        node *t=NULL;
        a.clear();
        for(int i=0;i<temp.size();i++)
        {
            insert(t,temp[i]);
        }
        layerorder(t,a);
        for(int i=0;i<n;i++)
        {
            cin>>str;
            node *s=NULL;
            b.clear();
            for(int i=0;i<str.size();i++)
                insert(s,str[i]);
            layerorder(s,b);
            if(a==b)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }

    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//思路为构造二叉排序树，构造完判断两个二叉排序树是否一样
struct TreeNode
{
    int data;
    TreeNode*left;
    TreeNode*right;
    TreeNode(int data):data(data),left(NULL),right(NULL){}
};
TreeNode* Insert(TreeNode*root,int x)
{
    if(root==NULL)
    {
        root=new TreeNode(x);
        return root;
    }
    else if(x<root->data)
        root->left=Insert(root->left,x);
    else if(x>root->data)
        root->right=Insert(root->right,x);
    return root;
}
bool TreeEqual(TreeNode*root1,TreeNode*root2)//判断相等
{ 
    if(root1==NULL&&root2==NULL)
        return true;
    if(root1->data!=root2->data)
        return false;
    return TreeEqual(root1->left,root2->left)&&TreeEqual(root1->right,root2->right);
}
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        TreeNode*root1=NULL;
        string bsTree;//第一个二叉排序树
        cin>>bsTree;
        for(int i=0;i<bsTree.size();i++)
                root1=Insert(root1,bsTree[i]-'0');//建立二叉排序树
        while(n--)//之后的二叉排序树
        {
            TreeNode*root2=NULL;
            string needCheck;
            cin>>needCheck; //需要检查的序列
            for(int i=0;i<needCheck.size();i++)
                root2=Insert(root2,needCheck[i]-'0');//建立二叉排序树
            if(TreeEqual(root1,root2))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }
    return 0;
}

#include<iostream>
#include<string>
using namespace std;

typedef struct Node
{
    int c;
    Node *left,*right;
    Node(int d):c(d),left(NULL),right(NULL){}
}Node;


Node *BuildTree(Node *root,int n)
{
    if(!root)
    {
        root = new Node(n);
    }
    else if(root->c > n)
    {
        root->left = BuildTree(root->left,n); 
    }
    else
    {
        root->right = BuildTree(root->right,n);
    }
    return root;
}

Node *Creat(Node *root,string s)
{
    for(int i = 0;i < s.size();i++)
    {
        root = BuildTree(root,s[i] - '0');
    }
    return root;
}

bool Judge(Node *root1,Node *root2)
{
    if(!root1 && !root2)
    {
        return true;
    }
    else if((!root1 && root2) || (root1 && !root2) || root1->c != root2->c)
    {
        return false;
    }
    else
    {
        return Judge(root1->left,root2->left) && Judge(root1->right,root2->right);
    }
}

int main()
{
    int n;
    while(cin >> n && n)
    {
        string s;
        Node *root1 = NULL;
        cin >> s;
        root1 = Creat(root1,s);
        while(n--)
        {
            Node *root2 = NULL;
            cin >> s;
            root2 = Creat(root2,s);
            if(Judge(root1,root2))
            {
                cout << "YES" << endl;
            }
            else
            {
                cout << "NO" << endl;
            }
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct TreeNode
{
    int data;
    TreeNode* leftchild;
    TreeNode* rightchild;
    TreeNode(int x):data(x),leftchild(NULL),rightchild(NULL){} 
};
TreeNode* Insert(TreeNode* root,int x)//递归建树
{
    if(root==NULL)
    {
        root=new TreeNode(x);
    }
    else if(x< root->data)//插入左子树
    {
        root->leftchild=Insert(root->leftchild,x);
    }
    else if(x>root->data)//插入右子树
    {
        root->rightchild=Insert(root->rightchild,x);
    }
    return root;
}
//前序遍历和中序遍历可以唯一确定一棵二叉树，而对二叉排序树而言，相同元素的二叉排序树中序遍历一定相同，
//而不同元素二叉排序树使用前序遍历就可以发现不相同，所以只需要前序遍历两个二叉树，
bool judge(TreeNode* root1,TreeNode* root2)//判断两二叉搜索树是否相等
{
    if(root1==NULL&&root2==NULL)
        return true;
    else if((root1!=NULL&&root2==NULL)||(root1==NULL&&root2!=NULL))
            return false;
    else if(root1!=NULL&&root2!=NULL)
    {
        if(root1->data==root2->data)
        {
           return judge(root1->leftchild,root2->leftchild)&&judge(root1->rightchild,root2->rightchild);
        }
        else 
            return false;
            
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0)
            break;
        string str;
        cin>>str;
        int l=str.size();
        TreeNode* root1=NULL;//建立空树
        for(int i=0;i<l;i++)
        {
            root1=Insert(root1,str[i]);
        }
        for(int i=0;i<n;i++)//n组测试树
        {
            string str1;
            cin>>str1;
            TreeNode* root2=NULL;
            for(int j=0;j<str1.size();j++)
            {
                root2=Insert(root2,str1[j]);
            }
            if(judge(root1,root2))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }
    return 0;
}

不容易啊
#include <stdio.h>
(737)#include <stdlib.h>
#include <math.h>
(865)#include <string.h>
#include <stdbool.h>
typedef struct ne
{
    char data;
    struct ne *lchild;
    struct ne *rchild;
}nb;
nb *ins(nb *root,char c)
{
    if(!root)
    {
        root=(nb *)malloc(sizeof(nb));
        root->data=c;
        root->lchild=root->rchild=NULL;
        return root;
    }
    else if(c<root->data)
    {
        root->lchild=ins(root->lchild,c);
    }
    else if(c>root->data)
    {
        root->rchild=ins(root->rchild,c);
    }
    return root;
}
bool juu(nb *root1,nb *root2)
{
    if(!root1&&!root2)
        return true;
    else if(root1&&root2&&root1->data==root2->data)
    {
        return juu(root1->rchild,root2->rchild)&&juu(root1->lchild,root2->lchild);
    }

    return false;
}
int main()
{
   int n;
while(scanf("%d",&n)!=EOF)
      {
          if(n==0)
            break;
      getchar();
       char s[11];
       gets(s);
       int len=strlen(s);
       int d[n];
       int i;
       nb *root=NULL;
       for(i=0;i<len;i++)
       {
           root=ins(root,s[i]);

       }
       int j;

       for(i=0;i<n;i++)
       {
            char *s1=(char *)malloc(sizeof(char));
           gets(s1);
           nb *root1=NULL;
           for(j=0;j<len;j++)
       {
           root1=ins(root1,s1[j]);
       }
       d[i]=juu(root,root1);
       free(s1);
       free(root1);
       }
      for(i=0;i<n;i++)
      {
          if(d[i]==1)
            printf("YES\n");
          else
            printf("NO\n");
      }
      }
return 0;
}

• 搜索二叉树构建
• 确定该二叉树前序中序遍历结果
• 比较两个遍历结果是否相同确定二叉树是否相同。

代码如下：

#include<stdio.h>
#include<string.h>
struct Node
{
    char d;
    struct Node * lchild;
    struct Node * rchild;
}tree[100];
int allocate = 0;

struct Node * insert(struct Node * root, char d)
{
    if (root == NULL) 
    {
        struct Node * newNode = &tree[allocate++];
        newNode->d = d;
        newNode->lchild = NULL;
        newNode->rchild = NULL;
        return newNode;        
    }
    if (root->d > d) root->lchild = insert(root->lchild, d);
    else root->rchild = insert(root->rchild, d);
    return root;
}

char * str;
int count;

void preOrder(struct Node * root)
{
    str[count++] = root->d;
    if (root->lchild != NULL) preOrder(root->lchild);
    if (root->rchild != NULL) preOrder(root->rchild);
}

void inOrder(struct Node * root)
{
    if (root->lchild != NULL) inOrder(root->lchild);
    str[count++] = root->d;
    if (root->rchild != NULL) inOrder(root->rchild);
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        if (n == 0) break;
        allocate = 0;
        char str1[20];
        scanf("%s", &str1);
        int len = strlen(str1);
        struct Node * root = NULL;
        int i;
        for (i = 0; i < len; i++) root = insert(root, str1[i]);
        char seq[20];
        str = seq;
        count = 0;
        preOrder(root); inOrder(root); str[count] = 0;
        int temp = allocate;
        for (i = 0; i < n; i++)
        {
            allocate = temp;
            char str2[20];
            scanf("%s", str2);
            int len2 = strlen(str2);
            struct Node * root2 = NULL;
            int j;
            for (j = 0; j < len2; j++) root2 = insert(root2, str2[j]);
            char seq2[20];
            str = seq2;
            count = 0;
            preOrder(root2); inOrder(root2); str[count] = 0;
            if (strcmp(seq, seq2) == 0) printf("YES\n");
            else printf("NO\n");
        }    
    }
    return 0;
}

#include <iostream>
#include <string>

using namespace std;


struct node {
  char val;
  node *left;
  node *right;
  node(int val='0', node* left=nullptr, node* right=nullptr): val(val), left(left), right(right) {}
};

node* insert_bst(node* root, char c) {
  node* newnode;
  if(root == nullptr) {
    newnode = new node(c);
  }
  else if(c > root->val) {
    newnode = insert_bst(root->right, c);
    if(root->right == nullptr) {
      root->right = newnode;
    }
  }
  else {
    newnode = insert_bst(root->left, c);
    if(root->left == nullptr) {
      root->left = newnode;
    }
  }
  return newnode;
}

node* build_bst(string s) {
  if(s.size() == 0) return nullptr;
  node* root = new node(s[0]);
  for(auto c : s.substr(1)) {
    insert_bst(root, c);
  }
  return root;
}

bool identical(node* a, node* b) {
  if(a == nullptr && b == nullptr) {
    return true;
  }
  if(a == nullptr || b == nullptr) {
    return false;
  }
  if(a->val != b->val) {
    return false;
  }
  bool left = identical(a->left, b->left);
  if(!left) return false;
  return identical(a->right, b->right);
}

int main() {
  int n;
  while(cin >> n) {
    if(n == 0) break;
    string ref, s;
    cin >> ref;
    node* refx = build_bst(ref);
    while(n--) {
      cin >> s;
      node* x = build_bst(s);
      if(identical(refx, x)) {
        cout << "YES\n";
      }
      else {
        cout << "NO\n";
      }
    }
  }
  return 0;
}

	

#include<stdio.h>
#include<string.h>
using namespace std;
int node[500];
int now[500];
char line[10];
void insert(int x,int a[],int i){
    if(x<a[i]){
        if(a[2*i]==-1){
            a[2*i]=x;
        }else{
            insert(x,a,2*i);
        }
    }else{
        if(a[2*i+1]==-1){
            a[2*i+1]=x;
        }else{
            insert(x,a,2*i+1);
        }
    }
}
int main(){
    int n;
    for(int i=0;i<500;i++){
        node[i]=-1;
    }
    scanf("%d\n",&n);
    scanf("%s",line);
    int len=strlen(line);
    for(int i=0;i<len;i++){
        int temp=line[i]-'0';
        insert(temp,node,0);
    }
    char new_line[10];
    while(scanf("%s",new_line)!=EOF){
        if(new_line[0]=='0'){
            break;
        }
        for(int i=0;i<500;i++){
            now[i]=-1;
        }
        int len1=strlen(new_line);
        for(int i=0;i<len1;i++){
        int temp=new_line[i]-'0';
        insert(temp,now,0);
        }
        if(len1!=len){
            printf("NO\n");
            continue;
        }
        bool same=true;
        for(int i=1;i<500;i++){
            if(now[i]!=node[i]){
                same=false;
                break;
            }
        }
        if(same){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
}

	

#include<cstdio>
#include<cstring>
int n,root;
int lchild[10];
int rchild[10];
int  root1;
int lchild1[10];
int rchild1[10];
char in[11];
#pragma warning(disable:4996)
void build(int num,int pre) {     if (num < pre) {         if (lchild[pre] == -1)lchild[pre] = num;         else build(num, lchild[pre]);     }     else {         if (rchild[pre] == -1)rchild[pre] = num;         else build(num, rchild[pre]);     }
}
void build1(int num, int pre) {     if (num < pre) {         if (lchild1[pre] == -1)lchild1[pre] = num;         else build1(num, lchild1[pre]);     }     else {         if (rchild1[pre] == -1)rchild1[pre] = num;         else build1(num, rchild1[pre]);     }
}
int main() {     freopen("in.txt", "r", stdin);     while (scanf("%d", &n) != EOF &&n) {         for (int i = 0; i < 10; i++) lchild[i] = rchild[i] = -1;         scanf("%s", in);         root = in[0] - '0';         for (int i = 1; i < strlen(in);i++) {             int node = in[i] - '0';             build(node, root);         }         for (int i = 0; i < n; i++) {             for (int j = 0; j < 10; j++) lchild1[j] = rchild1[j] = -1;             scanf("%s", in);             root1 = in[0] - '0';             for (int j = 1; j < strlen(in); j++) {                 int node = in[j] - '0';                 build1(node, root1);             }             int flag = 1;             for (int j = 0; j < 10; j++) {                 if (lchild[j] != lchild1[j] || rchild[j] != rchild1[j]) {                     flag = 0;                     break;                 }             }             if (flag == 0)printf("NO\n");             else printf("YES\n");         }     }     return 0;
}

两次建树过程，只保存左右孩子数组。比较两个树的数组是否相等即可

#include<stdio.h>
#include<string.h>
struct Node{
 Node *lchild;
 Node *rchild;
 int c;
}Tree[110];
int loc;
Node *creat(){//申请空间 
  Tree[loc].lchild=Tree[loc].rchild=NULL;
  return &Tree[loc++]; 
} 
char str1[30],str2[30];//包括中序在内的两种遍历可以确定唯一棵二叉树，
      //所以可以将前序和中序字符串连接之后进行比较
      
int size1,size2;//保存字符串个数
char *str;//当前正在保存的字符串
int *size;//当前正在保存的字符个数 

void preorder(Node *T){//前序 
 str[(*size)++]=T->c+'0'; 
 if(T->lchild!=NULL)
 {
 preorder(T->lchild);
 }
 if(T->rchild!=NULL)
 {
 preorder(T->rchild);
 }
 }
 void inorder(Node *T){//中序 
 if(T->lchild!=NULL)
 {
 inorder(T->lchild); 
 }
 str[(*size)++]=T->c+'0'; 
 if(T->rchild!=NULL)
 {
 inorder(T->rchild);
 }
 }
 Node *insert(Node *T,int x) {//插入数字
 if(T==NULL)
 {
 T=creat();
 T->c=x;
 return T;
 } 
 else if(x<T->c)
 {
 T->lchild=insert(T->lchild,x);
 }
 else if(x>T->c)
 {
 T->rchild=insert(T->rchild,x);
 }
 return T;
 }
 int main(){
 int n;
 char x[12];
 while(scanf("%d",&n)!=EOF&&n!=0){
 loc=0;//初始化静态空间
 Node *T=NULL;
 scanf("%s",x);
 for(int i=0;x[i]!=0;i++)
 {
 T=insert(T,x[i]-'0');
 }
 size1=0;
 str=str1;
 size=&size1;
 preorder(T);
 inorder(T);
 str1[size1]=0;//结尾添加空字符
 while(n--!=0) {//输入n个其他字符串 
 scanf("%s",x);
 Node *T2=NULL;
 for(int i=0;x[i]!=0;i++)
 {
 T2=insert(T2,x[i]-'0');
 }
 size2=0;
 str=str2;
 size=&size2;
 preorder(T2);
 inorder(T2);
 str2[size2]=0;//结尾添加空字符
 puts(strcmp(str1,str2)==0?"YES":"NO"); 
 }
 }
 return 0;
 }

二叉搜索树即二叉排序树，要判断两棵树是否一致，可用：
（1）判断前序+中序遍历结果是否一致
（2）判断后序+中序遍历结果是否一致
两种方法来判断
又因为二叉排序树中序遍历的结果是所有数递增的结果，所以只需判断前序或后序遍历结果是否一致即可（这里判断的是前序遍历结果）

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct BiNode{
    struct BiNode *lchild, *rchild;
    char e;
}BiNode, *BiTree;

void Insert(BiTree *T, char c)  //构造二叉排序树
{
    if((*T)==NULL)
    {
         (*T) = (BiNode *)malloc(sizeof(BiNode));
         (*T)->e = c;
         (*T)->lchild = NULL;
         (*T)->rchild = NULL;
    }
    else{
        if(c==(*T)->e) return ;
        if(c>(*T)->e) Insert(&(*T)->rchild, c);
        else Insert(&(*T)->lchild, c);
    }
}
string PreOrder(BiTree T)  //将二叉树的前序遍历结果存放在一个字符串中
{
    string str = "";
    if(T!=NULL)
    {
        str+=T->e;
        str+=PreOrder(T->lchild);
        str+=PreOrder(T->rchild);
    }
    return str;
}
bool cmp(BiTree T, BiTree T1)  //比较两个二叉搜索树的前序遍历结果是否一样
{
    string str1 = PreOrder(T);
    string str2 = PreOrder(T1);
    if(str1==str2) return true;
    return false;
}
void Delete(BiTree *T)  //销毁二叉树，释放其申请的空间
{
    if((*T)->lchild==NULL && (*T)->rchild == NULL)
    {
        free(*T);
        *T = NULL;
    }
    else{
        if((*T)->lchild!=NULL)
        {
            Delete(&(*T)->lchild);
        }
        if((*T)->rchild!=NULL)
        {
            Delete(&(*T)->rchild);
        }
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) return 0;
        string str, strtmp;
        cin>>str;
        BiTree T = NULL, T1 = NULL;
        for(int i = 0; i<str.length(); i++)  //对参考字符串构造二叉排序树
            Insert(&T, str[i]);
        for(int i = 0; i<n; i++)
        {
            cin>>strtmp;
            for(int i = 0; i<strtmp.length(); i++)  //对待判断的字符串构造二叉排序树
                Insert(&T1, strtmp[i]);
            if(cmp(T, T1)) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
            Delete(&T1);
            T1 = NULL;
        }
    }
    return 0;
}