04-树4 是否同一棵二叉搜索树

　　课上例题，重点是标记变量的使用。

#include <stdio.h>
#include <stdlib.h>

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

Tree NewNode(int V)
{
    Tree T;
    T = (Tree)malloc(sizeof(struct TreeNode));
    T->v = V;
    T->Left = NULL;
    T->Right = NULL;
    T->flag = 0;
    return T;    
}

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 MakeTree(int N)
{
    Tree T;
    int i, V;
    scanf("%d", &V);
    T = NewNode(V);  //head node constructed
    for(i = 1; i < N; i++){
        scanf("%d", &V);
        T = Insert(T, V);
    }
    return T;
}

int check(Tree T, int V)
{
    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;
    }else{  
    //与树中标记为0（还未被访问的结点）比较
    //只能等于这个值
        if(V == T->v){
            T->flag = 1;
            return 1;
        }
        else 
            return 0;
    }
}

int Judge(Tree T, int N)
{
    int i, V, Seqflag = 0;
    //Seqflag用于判断此序列是否与树一致，控制读取和输出用
    scanf("%d", &V);
    if(V != T->v)  //judge the root node
    //    return 0;
        Seqflag = 1;
    else
        T->flag = 1;
    for(i = 1; i < N; i++){
        scanf("%d", &V);
        if(!check(T, V) && (!Seqflag))
    //        return 0;
            Seqflag = 1;
    }
    if(Seqflag)
        return 0;
    else
        return 1;
}

void ResetT(Tree T)
{
    if(T->Left)
        ResetT(T->Left);
    if(T->Right)
        ResetT(T->Right);
    T->flag = 0;
}

void FreeTree(Tree T)
{
    if(T->Left)
        FreeTree(T->Left);
    if(T->Right)
        FreeTree(T->Right);
    free(T);
}

int main(int argc, char const *argv[])
{
    int N, L, i;
    Tree T;
    scanf("%d", &N);
    while(N){
        scanf("%d", &L);
        T = MakeTree(N);
        for(i = 0; i < L; i++){
            if(Judge(T, N))
                printf("Yes
");
            else
                printf("No
");
            ResetT(T);
        }
        FreeTree(T);
        scanf("%d", &N);
    }
    return 0;
}