编辑代码

#include <stdio.h>
#include <malloc.h>

/*判别：
    如果在查找过程当中，发现查找某个整数，它所经过的路径有
    某个结点之前没有碰到过的（在前面没出现过），那么这个序列
    一定跟T不一致。
    因为如果没有碰到过，那么当前这个整数就不应该插在后面，而是
    在没有碰到过的结点上就应该插入了，而不会往下插。
    所以把一个序列跟一个树是不是一致的判别就转化为了查找这个序列的
    每一个整数在树中的位置，如果在查找过程中发现某个结点之前没有碰
    到过，那么就说明不一致，否则就是一致的。
*/

typedef struct TreeNode *Tree;
struct TreeNode{
    int v;
    Tree Left,Right;
    int flag;
};

Tree MakeTree(int N);
Tree NewNode(int V);
Tree Insert(Tree T,int V);
int check(Tree T,int V);
int Judge(Tree T,int N);
void ResetT(Tree T);
void FreeTree(Tree T);

//释放T的空间
void FreeTree(Tree T){
    if(T->Left){
        FreeTree(T->Left);
    }
    if(T->Right){
        FreeTree(T->Right);
    }
    free(T);
}

//清除T中各结点的flag标记
void ResetT(Tree T){
    if(T->Left){
        ResetT(T->Left);
    }
    if(T->Right){
        ResetT(T->Right);
    }
    T->flag = 0;
}

int Judge(Tree T,int N){
    int i,V;
    /*
       用于当发现不一致时，继续读完序列后面的数，防止
       直接退出时，把后面的序列当下一个序列读进来
       为0：代表目前还一致
       为1：代表已经不一致
    */
    int flag = 0;
    scanf("%d",&V);
    //判断根节点是否一致
    if(V != T->v){
        flag = 1;
    }else{
        T->flag = 1;
    }
    for(i = 1;i < N;i++){
        scanf("%d",&V);
        if( (!flag) && (!check(T,V)) ){
            flag = 1;
        }
    }
    if(flag){
        return 0;
    }else{
        return 1;
    }
}

/*实际上是一个查找函数，目的是在当前T里找整数V
  在查找过程中来发现是不是一致的
*/
int check(Tree T,int V){
    //flag为1，是之前碰到过的结点(被访问过)
    if(T->flag){
        //比根结点的值小，到左边查找
        if(V < T->v){
            return check(T->Left,V);
        }
        //比根结点的值大，到右边查找
        else if(V > T->v){
            return check(T->Right,V);
        }
        //相等，意味着序列中重复出现了相同的元素，则不一致
        else{
            return 0;
        } 
    }
    //flag为0，没被访问过
    else{
        //正好是要找的结点
        if(V == T->v){
            T->flag = 1;
            return 1;
        }
        //当前的flag为0，又不是要找的，即是之前没有
        //碰到过的结点，不一致，return 0
        else{
            return 0;
        }
    }
}


//新结点插入
Tree Insert(Tree T,int V){
    //树为空，创建一个新结点（根结点）
    if(!T){
        T = NewNode(V);
    }
    //非空
    else{
        //要插入的结点的值比根结点大，往右边插入
        if(V > T->v){
           T->Right = Insert(T->Right,V);
        }
        //要插入的结点的值比根结点小，往左边插入
        else{
           T->Left = Insert(T->Left,V);
        }
    }
    return T;
}

//分配一个新结点
Tree NewNode(int V){
    Tree T = (Tree)malloc(sizeof(struct TreeNode));
    T->v = V;
    T->Left = T->Right = NULL;
    T->flag = 0;
    return T;
}

//构建树T
Tree MakeTree(int N){
    Tree T;
    int i,V;

    scanf("%d",&V);
    //创建根节点
    T = NewNode(V);
    //插入N-1个结点
    for(i = 1;i < N;i++){
        scanf("%d",&V);
        T = Insert(T,V);
    }
    return T;
}

int main () {
    int N,L,i;
    Tree T;
    //输入结点个数
    scanf("%d",&N);
    while(N){
        //输入要比较的序列个数
        scanf("%d",&L);
        /*根据输入的第一个序列构造树
          用这个树与其他序列进行比较
        */
        T = MakeTree(N);
        //循环判断序列是否与T构成一样的搜索树，输入一个序列，判断一个序列
        for(i = 0;i < L;i++){
            if(Judge(T,N)){
                printf("Yes\n");
            }else{
                printf("NO\n");
            }
            //清除T中的标记flag，用于下一个序列的比较
            ResetT(T);
        }
        //释放构造的树，用于下一次循环构建新的树
        FreeTree(T);
        scanf("%d",&N);
    }
    return 0;
}